2018 Research Directions

Questions are welcome.

- (Learned) Memory
- Composability
- Sample Efficiency
- Interpretability

- Memory → Datastructures?
- Composability → Function composition?
- Sample Efficiency → High-level language bias?
- Interpretability → Existing languages?

- A bunch of programming language stuff
- Implementations (VMs, parsers, type inferencers)
- Logical + imperative language hybrids
- Formal logic, linear logic

- Program synthesis research
- (Computational) game theory research
- Cheap robots
- Vaporware robots

- Represent game rules using a DSL
- Synthesize or evolve programs
- 2015: use array language → difficulty
- 2016-2017: use Datalog → progress
- 2018: this is called Inductive Logic Programming!
- Task can be solved by beam search!

- a.k.a. first-order predicate calculus
- Basically Datalog±
- Extends zero-order / ground / propositional logic with predicates.

```
mortal(A) :- man(A)
man(Socrates)
```

Leads to the result (conclusion / interpretation):
```
mortal(Socrates)
```

- Tick-Tac-Toe
- Checkers
- Chess
- etc...

```
% X1 != X2 || Y1 != Y2
ne2(X1, Y1, X2, Y2) :- ne(X1, X2), any(Y1), any(Y2)
ne2(X1, Y1, X2, Y2) :- ne(Y1, Y2), any(X1), any(X2)
% Copy all squares which weren't played on.
next_board(X, Y, P) :-
board(X, Y, P),
move(X1, Y1),
ne2(X, Y, X1, Y1),
board(X1, Y1, Blank)
% Allow the player to play on a blank square.
next_board(X, Y, P) :-
move(X, Y),
board(X, Y, Blank),
player(P)
```

```
% Forward is player dependent.
step(Start, End) :- player(0), inc(Start, End)
step(Start, End) :- player(1), inc(End, Start)
three_adjacent(A, B, C) :- inc(A, B), inc(B, C)
three_adjacent(A, B, C) :- three_adjacent(C, B, A)
% "Bouncing" off the edge of the board.
step(7, 7) :- player(0)
step(0, 0) :- player(1)
three_adjacent(1, 0, 1)
three_adjacent(6, 7, 6)
% Copy all pieces which weren't moved or jumped.
next_board(X, Y, P) :-
board(X, Y, P),
move(X1, Y1, X2, Y2),
ne2(X, Y, X1, Y1),
ne2(X, Y, X2, Y2),
jumped(X3, Y3),
ne2(X, Y, X3, Y3)
jumped(X, Y) :-
move(X1, Y1, X2, Y2),
step(Y1, Y),
step(Y, Y2),
three_adjacent(X1, X, X2)
jumped(-1, -1) :-
move(X1, Y1, X2, Y2),
step(Y1, Y2),
three_adjacent(X1, X2, X3)
next_board(X, Y, Blank) :- jumped(X, Y), ne(X, -1)
next_board(X, Y, P) :-
player(P),
move(X1, Y1, X, Y)
```

```
% The chess games state is stored in two predicates:
% player(C: 0 | 1)
% and
% board(X: [0-7], Y: [0-7], P: [0-6], C: 0 | 1)
% where:
% P represents a piece.
% 0 -> blank
% 1 -> pawn
% 2 -> rook
% 3 -> knight
% 4 -> bishop
% 5 -> queen
% 6 -> king
% C represents a color / player.
% The input move is
% move(StartX, StartY, OutX, OutY)
% The output is
% next_board(X: [0-7], Y: [0-7], P: [0-6], C: 0 | 1)
% next_player(C: 0 | 1)
% Castling and en-passant aren't handled in this version.
next_board(X, Y, P, C) :-
move_output(X, Y, P, C)
move_output(X, Y, P, C) :-
% Must be C's turn
player(C),
move(StartX, StartY, X, Y),
% C must be moving their piece, from StartX, StartY
board(StartX, StartY, P, C),
% Need to move to blank or opponent's piece
valid_end(X, Y, C),
% Piece needs to move this way
valid_move_for_piece_player(StartX, StartY, X, Y, P, C)
% Put a blank where the piece was moved from.
next_board(X1, Y1, 0, 0) :-
move_output(X2, Y2, P, C),
move(X1, Y1, X3, Y3)
% Copy all pieces that weren't moved or at the end of a move.
next_board(X1, Y1, P1, C1) :-
% Get the piece.
board(X1, Y1, P1, C1),
% A move must have been made.
move_output(X2, Y2, P2, C2),
% The move must not have been made to the same space.
ne2(X1, Y1, X2, Y2),
% Must not have moved from X1, Y1.
move(X3, Y3, X4, Y4),
ne2(X1, Y1, X3, Y3)
% Players can move to blank spaces.
valid_end(X, Y, C) :-
player(C),
board(X, Y, 0, C2)
% Players can move to their opponent's spaces.
valid_end(X, Y, C) :-
ne(C, C2),
board(X, Y, Q, C2)
% Forward is increasing for player 0, decreasing for player 1
step(Start, End, 0) :- inc(Start, End)
step(Start, End, 1) :- inc(End, Start)
% As long as there's a blank, pawns can move one step forward.
valid_move_for_piece_player(X, StartY, X, Y, 1, C) :-
% There's C's pawn
board(X, StartY, 1, C),
% It steps from StepY to Y
step(StartY, Y, C),
% And there's a blank space at Y
board(X, Y, 0, Q)
% Player 0's pawns can move from Y=1 to Y=3 if there's two blank spaces in front of them.
valid_move_for_piece_player(X, 1, X, 3, 1, 0) :-
% 0's pawn is at X, 1
board(X, 1, 1, 0),
% X, 2 is blank
board(X, 2, 0, Q1),
% X, 3 is blank
board(X, 3, 0, Q2)
% Player 1's pawns can move from Y=6 to Y=4 if there's two blank spaces in front of them.
valid_move_for_piece_player(X, 6, X, 4, 1, 1) :-
% 1's pawn is at X, 6
board(X, 6, 1, 1),
% X, 5 is blank
board(X, 5, 0, Q1),
% X, 4 is blank
board(X, 4, 0, Q2)
adjacent(X, Y) :- inc(X, Y)
adjacent(X, Y) :- inc(Y, X)
% Pawns capture by stepping forward diagonally onto an opponent's piece
valid_move_for_piece_player(StartX, StartY, X, Y, 1, C) :-
% It steps from StepY to Y
step(StartY, Y, C),
% It changes by X one step (either direction)
adjacent(StartX, X),
% The opponent has a piece at X, Y
next_player(C2),
board(X, Y, P, C2),
% And that "piece" is not a blank space.
ne(P, 0)
valid_move_for_piece_player(StartX, StartY, X, Y, P, C) :-
% Don't care about player, but need it to come from somewhere (first order restriction).
player(C),
valid_move_for_piece(StartX, StartY, X, Y, P)
triple(Start, Mid, End) :-
inc(Start, Mid),
inc(Mid, End)
momentum(Start, Mid, End) :- triple(Start, Mid, End)
momentum(Start, Mid, End) :- triple(End, Mid, Start)
momentum(X, X, X) :- any(X)
cardinal_step(StartX, Y, X, Y) :-
adjacent(StartX, X), any(Y)
cardinal_step(X, StartY, X, Y) :-
adjacent(StartY, Y), any(X)
momentum_2d(StartX, StartY, MidX, MidY, X, Y) :-
momentum(StartX, MidX, X),
momentum(StartY, MidY, Y)
pass_through_space(StartX, StartY, MidX, MidY, X, Y) :-
momentum_2d(StartX, StartY, MidX, MidY, X, Y),
board(MidX, MidY, 0, C)
% Can move to any cardinal adjacent space.
rook_motion(StartX, StartY, StartX, StartY, X, Y) :-
cardinal_step(StartX, StartY, X, Y)
% Can continue a cardinal motion after passing through a blank space.
rook_motion(OriginalX, OriginalY, StartX, StartY, X, Y) :-
rook_motion(OriginalX, OriginalY, PrevX, PrevY, StartX, StartY),
pass_through_space(PrevX, PrevY, StartX, StartY, X, Y)
% Rooks move in a rook motion.
valid_move_for_piece(StartX, StartY, X, Y, 2) :-
rook_motion(StartX, StartY, PrevX, PrevY, X, Y)
% This shape:
% *-*-*-*
% | | | |
% *-*-*-*
% | | |#|
% *-*-*-*
% |k|-|/|
% *-*-*-*
knight_shape(StartX, StartY, X, Y) :-
% "Right" 2
triple(StartX, MidX, X),
% "Forward" 1
inc(StartY, Y)
% This shape (mirror across X = Y):
% *-*-*-*
% |/|#| |
% *-*-*-*
% ||| | |
% *-*-*-*
% |k| | |
% *-*-*-*
knight_shape(StartX, StartY, X, Y) :- knight_shape(StartY, StartX, Y, X)
% This shape (invert X axis):
% *-*-*-*
% | | | |
% *-*-*-*
% |#| | |
% *-*-*-*
% |\|-|k|
% *-*-*-*
knight_shape(StartX, StartY, X, Y) :- knight_shape(X, StartY, StartX, Y)
% This shape (invert Y axis):
% *-*-*-*
% |k|-|\|
% *-*-*-*
% | | |#|
% *-*-*-*
% | | | |
% *-*-*-*
knight_shape(StartX, StartY, X, Y) :- knight_shape(StartX, Y, X, StartY)
% All other knight shapes result from composition of the above.
% Knight can always move in a knight shape.
valid_move_for_piece(StartX, StartY, X, Y, 3) :-
% Move in a knight shape
knight_shape(StartX, StartY, X, Y)
diagonal_step(StartX, StartY, X, Y) :-
adjacent(StartX, X),
adjacent(StartY, Y)
% Can move to any diagonal adjacent space.
bishop_motion(StartX, StartY, StartX, StartY, X, Y) :-
diagonal_step(StartX, StartY, X, Y)
% Can continue a diagonal motion after passing through a blank space.
bishop_motion(OriginalX, OriginalY, StartX, StartY, X, Y) :-
bishop_motion(OriginalX, OriginalY, PrevX, PrevY, StartX, StartY),
pass_through_space(PrevX, PrevY, StartX, StartY, X, Y)
% Bishops move in a bishop motion.
valid_move_for_piece(StartX, StartY, X, Y, 4) :-
bishop_motion(StartX, StartY, PrevX, PrevY, X, Y)
% Queens can move in a bishop motion.
valid_move_for_piece(StartX, StartY, X, Y, 5) :-
bishop_motion(StartX, StartY, PrevX, PrevY, X, Y)
% Queens can move in a rook motion.
valid_move_for_piece(StartX, StartY, X, Y, 5) :-
rook_motion(StartX, StartY, PrevX, PrevY, X, Y)
% Kings can move to any cardinal adjacent space.
valid_move_for_piece(StartX, StartY, X, Y, 6) :-
cardinal_step(StartX, StartY, X, Y)
% Kings can move to any diagonal adjacent space.
valid_move_for_piece(StartX, StartY, X, Y, 6) :-
diagonal_step(StartX, StartY, X, Y)
```

- Niche success in pharmaceutical prediction
- Closely related to statistical relational learning, where relations are often used to represent a family of graphical models
- Markov Logic Networks (UW)
- Probabilistic Soft Logic (UCSC)
- Recent attempts to make "deep" ILP
- TensorLog (CMU)
- δILP (DeepMind)

- No feature learning (Beam Search, Evolutionary Strategies, Inverse Entailment, Conflict Driven Clause Learning, Meta Interpretation)

Or

- Significant enumeration
- Top theory → relaxed FOL program → graphical model / differentiable graph
- "One-hot" encoding of predicates over discrete variables

- ConstraintNetworks
- Match-Refute Diagrams
- Relational goal learning

- Similar to Relation Networks
- Constraint + Dataflow factorization
- Continuous (inequality) constraints
- Continuous variables
- "Regularization" encouraging convergence to discrete programs
- Should solve the memory cost at
**test**time.

- Allelic representation without local optima → guaranteed convergence with Evolutionary Strategies
- Can be translated into first order logic, but has guaranteed performance properties
- Basically a control flow graph operating a symbolic non-deterministic register machine
- Maybe guide mutation with Inverse Entailment?
- Maybe emulate beam search?
- Maybe try actual genetic algorithms instead?

- Learn predicate features using (semi) supervised learning
- Use predicates to describe goals in an RL system
- Use beam search to quickly find plausible goals from rewarded / unrewarded actions