Embedding: Why&How
We are interested in finding an embedding for the IDS on which we could observe nice distance metrics in a Euclidean space where computation on vectors is cheaply available..
Now a quick/naive idea would be simply treating the IDS as a sequence and invoke a neural model for sequences. This approach exposes the following drawbacks:
While IDS itself is in its plain form a flat sentence, it is in fact NOT a flat sequence, because it represents a tree that is composed by sub-parts
Sibling/children nodes in a IDS tree have relative relationships; these nodes are ordered and not commutative. Meaning ⿱口耳 and ⿱耳口 are different. For a particular IDC such as ⿱, its first child is specified as in the top, and the second in the bottom, by definition.
Not leveraging compositional structure is not itself necessarily a bad idea, Unfortunately I believe for such a simple task, invoking a large model is just introducing excessive burden of unnessary carbon footprints to our mother earth. but generalizing to long sequence to certain extent is difficult. Or at least not easy if we only wish to afford a lightweight model.
While the rationale should now be clear, let us state explicitly:
A sequence model for the task we are considering is sub-optimal; we would like a model that operates on trees; not just any tree, but trees that has ordered children/sibling nodes.
So here I propose to use of tweaked version of the Tree LSTM to learn embeddings for IDS. But before that, let us first look at a normal sequence,
Figure 1: A example sequence
Let us now denote a recurrent unit function \(f\) which is parameterized by a neural
network (RNN or LSTM cell), and further denote \(E\) the embedding function that converts a
token into a token embedding, implemented as a look-up table. The
function \(f\) takes hidden states and
input and outputs a new state \(H\).
For node a,\[
H(a) = f(\text{hidden_state}=E(\text{START}), \text{input}=E(a))
\]
Because a is the first token in the sequence, we need to
introduce an extra token START. And then for token
b, the process continues by using \(H(a)\) as the hidden_state.
\[ H(b) = f(\text{hidden_state}=H(a), \text{input}=E(b)) \]
and then
\[ H(c) = f(\text{hidden_state}=H(b), \text{input}=E(c)) \]
By this point, \(H(c)\) is the embedding of the sequence.
Now let us move to a tree and explain what the Child-sum Tree LSTM
(Tai, Socher, and Manning 2015Tai, Kai Sheng, Richard Socher, and Christopher D Manning. 2015.) works.
Here let us assume that while a and b are both
the children of c, there is an order that a
precedates b.
Figure 1: A example tree
The hidden state of a and b are
straightforward: \[ H(a) =
f(\text{hidden_state}=E(\text{START}), \text{input}=E(a)) \] and
\[ H(b) =
f(\text{hidden_state}=E(\text{START}), \text{input}=E(b)) \], the
tricky part is how we aggregate the children node for the parent. The
child-sum Tree LSTM, as the name suggests, aggregates the hiddent states
of children nodes by summing it up, so \[
H(c) = f(\text{hidden_state}=H(a) + H(b), \text{input}=E(c))
\]
Readers may already notice now that the sum operation considers no information regarding the order of the children nodes. One may come up with some ideas ressembling familiar works, such as adding some position encodings or adding a weight to the children nodes.
\(H(c) = f(\text{hidden_state}=W_1 * H(a) + W_2 * H(b), \text{input}=E(c))\). This is also the follow up called N-ary Tree LSTM from the paper.
Here in my tweak, let us just use another network to process the children nodes as a sequence.
We can think of the original Child-sum Tree LSTM performing a sequence processing from left to right (from leaves to root) and uses sums for children/sibling nodes (from top to bottom), while in our case, we retain the left-ro-right recurrent model and add another recurrent model to process the children/sibling nodes from top to bottom. Denote the new recurrent function as \(g\), we have: \[ H_g(a) = g(\text{hidden_state}=E(\text{START}), \text{input}=H(a)) \] \[ H_g(b) = g(\text{hidden_state}=H_g(a), \text{input}=H(b)) \] and finally we arrive at \[ H_f(c) = f(\text{hidden_state}=H_g(b), \text{input}=E(c)) \]
Rigid methods like manual structure comparison (simply retrieving glyphs sharing the same left-part) or tree editing distances may sound appealing, but they require tedious parameter tuning and often yield limited results. This approach has its drawbacks.
I will refer to this model as Cross Tree LSTM. The term “cross” signifies that the old child-sum Tree LSTM focuses only on the horizontal direction, disregarding the order of children nodes. In our approach, we introduce an additional LSTM to handle the vertical direction. Thus, we have two LSTMs—one for the vertical direction and one for the horizontal direction—making it a ‘cross’.