Collection Of Variable Length Sequences and Descriptions: A Search Problem

Question

I have a tough problem and need some advice:

Suppose I have a collection of variable length sequences, many of which are unique -- imagine the moves to a chess game, eg

1. d4 Nf6
2. c4 g6
3. Nc3 Bg7
4. e4 d6
5. Nf3 O-O
6. Be2 c5
7. O-O Bg4

...

and for each item in this collection, I have another collection of descriptions generated by humans (think comments - comment_1: "cool game", comment_2: "awesome sacrifice")

The goal is to mine the associations between the comments and the sequences to tag the sequences with human readable labels for search purposes.

I've thought about topic modeling for label generation + clustering/grouping the sequences, but I cannot figure out how to do something like cluster the games. I have millions of examples of the sequences if that helps. Any idea how I can measure the distance/similarity between sequences like this? Some kind of embedding? I've thought about trying a word2vec / doc2vec approach, but haven't tested yet.

Ideally I'd be able to input an unseen sequence and suggest labels/human-readable description for this sequence as well.

Answer 1

While an RNN using one-hot encoded moves is possible, I would suggest that your model needs to understand chess (or similar complex games) at a deeper level to be able to associate comments to positions.

I would encode the position itself (eg a layered representation like in Alpha-Zero paper), and pass those through a conv-RNN to model the temporal relationship between positions corresponding to annotations. (Maybe you can find a pretrained model for evaluation as a baseline).

I read a fair amount of chess commentary, and one thing that is common is that there are cases of single move as well as comments about several moves at a time (think opening lines, or forced continuations), which are fairly discrete (my 'move 10 sacrifice' and my 'move 15 blunder' are not related by a hidden state). This leads me to think that instead of an RNN model, you are really trying to first Partition then Embed moves in a comment space - which then leads to a model that is first an RNN which may learn likely partitions of moves to be commented on, then another model, perhaps conditional autoencoder, is trained jointly on (position | comment) subsequences (you should still have plenty of features to work with at this point, so no worry about a weak signal).

The 'search' functionality here points not at a pure deep learning model, since you want to find specific instances of positions, rather than a typical position with that comment (ie sampling a latent space). This leads me to think that you create an explicit data-structure to map points in your final embedding space to their positions. So if you wanted to search 'Nice Sacrifice', model would find closest points in 'comment space' and return those games using something like cosine distance, or this last step is clustering of the (position | comment) space.

Either way, interesting problem, try the simpler thing first.

Answer 2

I don't know a ton about chess notation but it looks like you can encode these moves as pairs of categories in some way. Then every move is a time step in your (input) sequence. What you could try to do is use a seq2seq model to map your input sequence (the game progression) to the output sentence. I do think that modeling your inputs as a recurrent unit will be very possible, but predicting raw text output might be difficult to extract properly just because the signal is so thin and difficult to capture. You could look into classifying these comments into a few categories and turning it into a RNN classification problem, which might lead to better results.