Multi-Intent Detection in User Provided Annotations for Programming by Examples Systems

- This kind of ambiguity can happen when the output substring of all the I/O pairs can be extracted by applying the same DSL operator on corresponding input annotations and have the same length. For example, in Table 3, example 1, following substring or continuous sequence in output “123” and “535” are extracted from the similar continuous sequence in input and also are of the same length, hence it is not clear that whether the user wants to extract everything after second “_” or just three characters. In terms of DSL, mostly this kind of ambiguity can be possible because of the outputs generated by constant length-based operators like substring with constant positions vs pattern-based operators like split, substring with a pattern. Formally, we can define this property as, given an example (($I_{1},O_{1}),(I_{2},O_{2}),...,(I_{l},O_{l})$) satisfies this property when the continues sequence of string in an output matches to the same continuous sequence of string in input and have the same number of characters across that sequence in all the output samples. $I_{l}$ denotes the $l^{th}$ input sample, and $O_{l}$ denotes the corresponding output sample, and $l$ denotes the total I/O samples in one example.

- This kind of ambiguity can happen when the output substring of all the I/O pairs can be extracted by applying the same DSL operator on corresponding input annotations and extracted output string always starts or ends on the same position in the input string. For example, in Table 3, example 2, following substring or continuous sequence in output “Kumar” and “Williams” are extracted from the similar continuous sequence in input and also starts from the same position in input i.e. 5, hence it is not clear that whether the user always wants to extract substring started from position 5 in input, or the user have some other desired intent (extract something after space character). In terms of DSL, mostly this kind of ambiguity can be possible because of the operators which allow constant positions to detect a position of substring vs operators which uses regex or split-based operation to extract substring. Formally, we can define this property as, given an example (($I_{1},O_{1}),(I_{2},O_{2}),...,(I_{l},O_{l})$), it satisfies this property when the continuous sequence of string in an output matches to the same continuous sequence of string in the corresponding input and it has a start or end always at the same position.

This kind of ambiguity can happen when the output substring of all the I/O pairs can be extracted by applying the same DSL operator on corresponding input annotations and extracted output substring across annotations have the same string value. For example, in Table 3, example 3, following substring or continuous sequence in output “11” and “11” are extracted from the similar continuous sequence in input and also have the same string value i.e. 11, hence it is not clear that whether the user always wants to have constant value 11 in output or the user want to extract this value from the input string. In terms of DSL, mostly this kind of ambiguity can be possible because of the operators which allow constant positions to detect a position of substring vs operators like split/substring which allow values to be extracted from the string itself. Formally, we can define this property as, given an example (($I_{1},O_{1}),(I_{2},O_{2}),....,(I_{l},O_{l})$) satisfies this property when the continues sequence of string in an output matches to same continuous sequence of string in input and have same value.

This kind of ambiguity can happen when the output substring of all the I/O pairs can be extracted by applying the same DSL operator on corresponding input and extracted output substring across I/O pairs is of the same type. For example, in Table 3, example 4, following substring or continuous sequence in output “123” and “53” are extracted from the similar continuous sequence in input and also have the same value type, hence it is not clear that whether the user always wants to extract the same data type value or something else. Mostly, three types of tokens, Alphabet Tokens which consists of all uppercase and lowercase English alphabets, Numeric Tokens which consists of digits from 0 to 9 and Special-Character Tokens which consists of all printable special characters on the keyboard, are possible. Hence, we say that an example satisfies a similar token type if all its continuous substring in outputs are either all Alphabet Tokens or all Numeric Tokens or all Special-Character Tokens. In terms of DSL, mostly this kind of ambiguity can be possible because of the operators which allow a specific set of regex positions to detect a position of substring vs operators like split/substring which allows values to be extracted from string itself. Formally, we can define this property as, given an example satisfies this property when the continues sequence of string in an output matches to same continuous sequence of string in input and have same value type.

This kind of ambiguity can happen when the output substring of all the I/O pairs can be extracted by applying the same DSL operator on corresponding input annotations and have multiple instances of that output substring is possible in input. For example, in Table 3, example 5, following substring or continuous sequence in output “1” and “2” can be extracted from two similar positions from the input. Those positions can be defined by any low-level operators like constant positions, regex, or high-level operators like split, etc. In this case, that common substring is possible at two constant positions in input i.e. positions 3 and 9. Hence it is not clear that whether the user wants to extract a substring from position 3 or 9. This is DSL independent ambiguity, which can happen because the user provided the samples in the way that it internally it generating such kind of ambiguity. Formally, we can define this property as, given an example satisfies this property when the continues sequence of string in an output matches to multiple instance of continuous sequence of string in input.

This module is used for encoding the raw I/O strings (see Figure 3) and consists of two sub-modules:

• •

  Character Level Embedding Layer - This layer maps each character of the I/O pairs in each example to a 128-dimensional learning space. Given an input ($i_{1},..,i_{n}$) and an output string ($o_{1},..,o_{m}$) consisting of a sequence of characters of length $n$ and $m$ respectively, this layer outputs a list of character embedding. Here, n refers to the maximum length of input among all the examples in the dataset. The input strings which are smaller than the maximum length are appended with ¡pad¿ tokens to make their length equal to $n$. The ¡pad¿ tokens specify that the current character does not signify the original string but marks the end of it or is used to make all sequences of the same length so that the deep learning tensor computations are easier. A similar procedure is followed with the output strings, where the maximum length of output among all the examples in the dataset is $m$. Each character $i_{t}$ and $o_{s}$ in the input and output sequence is mapped to the 128-dimensional raw embedding $e_{i_{t}}$ and $e_{o_{s}}$ respectively via a randomly initialized and trainable embedding matrix, where $t\in\{1,..n\}$ and $s\in\{1,..m\}$.

• •

  Input Encoder - This layer uses LSTM representations (hochreiter1997long, ) applied on the embedding $e_{i_{t}}$ of the inputs of each example as shown in Equation 1. This layer helps to learn the sequential dependencies of the characters of the inputs. It takes the input embedding of each character $e_{i_{t}}$ and passes them through a LSTM layer consisting of n separate LSTM cells with a hidden vector size of 512 as shown in Equation 1.

  (1)

  $$\footnotesize\overrightarrow{h_{i_{t}}}=LSTM(e_{i_{t}},\overrightarrow{h_{i_{t-1}}}),t\in({1...n})$$

Hence, the Common Encoder takes I/O pair as input and produces two output representations, the raw 128-dimensional embedding of each character in the output sample and the LSTM encoded embedding of the Input sample in the I/O pair. These embeddings will be generated for each I/O pairs in an example. The outputs of the Common Encoder are then utilized by next Modules.

These modules are designed for the detection of each ambiguity property. We have 5 such modules (one for each ambiguity) with a similar structure, which process the inputs obtained from the common encoder. Each Task-Specific Module contains an Additive Attention Output Encoder, Concatenation Layer, Convolution Neural Networks & Pooling Layer, and Softmax Layer as classification layer. The weights across all these 5 task-specific modules are not shared with each other.

• •

  Attention Output Encoder - In our architecture, we use additive attention mechanism (bahdanau2014neural, ) to selectively impart more importance to the part of the input which has more influence on the output characters and hence obtain better output sample encoding. Specifically, this layer computes the additive attention $a_{e_{o_{s}}}$ of a single embedded output character $e_{o_{s}}$ with respect to the encoding of all the input characters $h_{i_{1..n}}$ as shown in the equations 2 and 3. For this, we pass the output from the Input Encoder to the Attention Output Encoder which first computes the attention weights $\alpha_{s_{1..n}}$ as shown in eq. 2 and the corresponding attention vector $a_{e_{o_{s}}}$ as shown in eq. 3 for each output character $O_{s}$ with respect to all input characters in the I/O pair. Here, $W_{a}$ and $U_{a}$ are the learnable weight matrices. $W_{a}$ corresponds to the output embeddings vector $e_{o_{s}}$ and $U_{a}$ corresponds to the input encodings matrix $h_{i_{1..n}}$. $V_{a}$ is the learnable vector. The attention output $a_{e_{o_{s}}}$ is concatenated with the output embedding $e_{o_{s}}$ to give $c_{o_{s}}$ as shown in equation 4 and is passed through an LSTM layer with hidden vector size 512 as shown in eq. 5.

  (2)

  $$\footnotesize\alpha_{s_{1..n}}={V_{a}}tanh({W_{a}}{e_{o_{s}}}+{U_{a}}h_{i_{1..n}}),s\in({1..m})$$

  (3)

  $$\footnotesize a_{e_{o_{s}}}=\Sigma_{t}\alpha_{s_{t}}h_{i_{t}},t\in({1..n}),s\in({1..m})$$

  (4)

  $$\footnotesize{c_{o_{s}}}=[a_{e_{o_{s}}},e_{o_{s}}],s\in({1..m})$$

  (5)

  $$\footnotesize\overrightarrow{h_{o_{s}}}=LSTM(c_{o_{s}},\overrightarrow{h_{o_{s-1}}}),s\in({1..m})$$

  The Attention Output Encoder outputs $m$ different LSTM encodings $h_{O_{1..m}}$ for each output string of length $m$ in $l$ I/O pairs, which further passed to the next Layer.

• •

  Concatenation Layer - For this, we concatenate the $l$ encodings corresponding to $l$ I/O pairs for each example. Detecting ambiguity is possible only by analyzing all the I/O pairs in a given example and not just one I/O pair. These encodings are obtained from the Attention Output Encoder in a row-wise manner as shown in equation 6. Here, $h_{1_{o_{s}}}$ refers to the attention-encoded output of the $s^{th}$ character of the Output $O_{1}$ from the first I/O pair. Similarly, $h_{l_{o_{s}}}$ refers to the attention-encoded output of the $s^{th}$ character of the Output $O_{l}$ from the $l^{th}$ I/O pair.

  (6)

  $$\footnotesize q_{s}=concat(h_{1_{o_{s}}},h_{2_{o_{s}}},...,h_{l_{o_{s}}}),s\in({1..m})$$

  (7)

  $$\footnotesize Q=[q_{1},q_{2},....,q_{m-1},q_{m}]$$

  The output of the Concatenation Layer is a matrix $Q$ as shown in eq. 7. There are a total of $m$ different rows in the matrix corresponding to the $m$ characters of the Outputs in an I/O pair. More specifically, each row of the matrix represents the character-level concatenation of the output encodings from $l$ different examples. This matrix is then passed into the next layer.

• •

  Convolution Neural Network and Pooling Layers - Convolution Neural Networks (CNNs) are used for finding local dependencies in features. In our architecture, CNNs help us to capture the dependencies between adjacent characters and subsequent encoded Outputs of the I/O pairs. The input to the CNN layer is the matrix $Q$ for each example that we obtain from the Concatenation Layer. In this layer, we apply 2-dimensional convolution operations with 512 output channels where each channel contains a kernel of dimension (2, $l$*512) on the input from the concatenation layer. We then applying MaxPooling on the outputs of the CNNs across each channel to obtain a single vector $r$ of size 512 dimensions for the I/O pairs in an example as seen in eq. 8. This 512 size vector is then passed into the next Layer.

  (8)

  $$\footnotesize r=MaxPool2D(Conv2D(Q))$$

• •

  Classification Layer - Classification Layer is a fully-connected dense layer with 2 neurons corresponding to either the positive or negative class for each ambiguous property classification to give the classification logits $u$. This is shown in equation 9 where $W_{f}$ and $b_{f}$ are the weight matrix and the bias vector respectively.

  (9)

  $$\footnotesize u=W_{f}r+b_{f}$$

  Classification logits from the Classification Layer are then passed through the Softmax Layer.

• •

  Softmax Layer - This layer applies the softmax activation function on the classification logits to obtain a probability distribution $p$ over the prediction classes (ambiguous properties) as shown in equation 10. Here, $z$ is used for indexing a single class among the positive and the negative classes.

  (10)

  $$\footnotesize p=\frac{exp(u_{z})}{\Sigma_{z}exp(u_{z})},z\in({0,1})$$

The proposed multitask learning framework uses Cross-Entropy loss between the original and predicted labels as the objective function for all the five task-specific modules. Equation 11 denotes the loss from the $k^{th}$ task-specific module. We use $k$ to index the task-specific modules. $p_{k}$ is the predicted probability distribution for the $k^{th}$ task-specific module. $y_{k}$ is the original probability distribution for the $k^{th}$ task-specific module. We obtain the final loss $L$ by taking a weighted sum of the individual losses $L_{k}$ of each of the task-specific modules as shown in equation 12. Here $w_{k}$ is the weight corresponding to the $k$th Loss $L_{k}$.

For each output substring in an example, we chose a length from a range of 2-9 characters. We limit the output substrings to a maximum of 4 for each sample. Each output substring will contain a mixture of lowercase, uppercase English alphabets, and digits from 0-9. We add random strings on the front and the back of each output substring to construct the input string. Similarly, we do this for other output substrings, and finally, combine the I/O substrings to make it a single I/O pair. We repeat the above process by fixing the output substrings size across the samples in a single example and combine those I/O pairs to make a single example. In our case, we use a set of three I/O pairs in a single example. We illustrate the process of creating I/O pairs through the following example. In the first step, we first assume an output substring of length three for sample-1 is “abc”, for sample-2 is “klp” and for sample-3 is “12j”. In the second step, we add random I/O strings before and after the first output substring for sample-1 “dfg1#abc#2311”, sample-2 “era#klp#hj1”, and sample-3 “h2ral#12j#klj23jk”. In the third step, we create a new output substring that can follow this similar length property or not. We then repeat the second step, for example, let us assume that the second output substring is of varied length, let’s say “hjuk”, “puefhkj”, and “jf16hsk”. Now, either we append this directly to the input with some delimiter or first add some other random string before or after this string. In this case, we append this directly using delimiter “@”, so final input strings become “dfg1#abc#2311@hjuk”, “era#klp#hj1@puefhkj” and “h2ral#12j#klj23jk@jf16hsk”. We can combine the output substrings using any character or directly. In this example, we are combining it directly which leads to the following output samples corresponding to the input samples - ‘abchjuk”, “klppuefhkj” and “12jjf16hsk”. We can repeat the same process by generating more output substrings for an example.

The process of example generation for this ambiguity will remain almost the same as the “Similar Length Ambiguity” property. The only change is that instead of fixing output substring length across samples, we will fix the output substring’s position in the input string.

- In this case, the process differs with respect to output substring value. The output substring value across the I/O pairs within the same example will remain the same. This property inherently also satisfies the Similar Length Ambiguity.

In this case, the process differs with respect to output substring type. That is, the output substring’s token-type across the I/O pairs within same example will remain the same. In our work, we define two types of token-types viz. alphabets and numerals. More specifically, the two categories of similar token types are when, either the output strings contain only the uppercase and lowercase alphabets or only digits from 0-9.

In this case, the output substring exists (or repeats itself) at multiple positions in the input.

In this setup, we remove the CNN and the MaxPool layers from the proposed model architecture and only pass the concatenated output encodings to the classification layer.

In this setup, we remove the Attention Mechanism from the proposed model. We retain the same output encoder but set the attention weights for each output characters over all input characters is equal to 1 while calculating the attention vector.

In this, we replace all LSTM layers and cells with GRU (cho2014learning, ) cells in the proposed architecture. We retain the same overall architecture and keep the GRU hidden size equal to 512.

In Table 4, we compare the results of the proposed framework with two different loss functions, Cross-Entropy, and Focal Loss. Also, we provide a quantitative analysis highlighting the importance of each layer. For this, we first remove the layer from the task-specific modules and then report the performance of the same. We show the property-wise performance in Table 4. From the result table, we can see that overall Cross-Entropy is performing better than the Focal Loss. The model has trained with 26,667 examples corresponding to each ambiguous property for 100 epochs with a batch size of 5 per epoch. We set the weights of each loss corresponding to five different ambiguity tasks equally to 1. We report the results on the 6,667 examples test set.

The main model, denoted by our, performs better than the other variations of the proposed framework when using the same loss metric. We can also observe that by removing the attention layer from the main model, the performance of the model got decreased by 10-20% for most of the cases, which highlights the need for an attention layer. A similar kind of pattern can be observed when we remove the CNN layer from the main model. In some cases, performance got dropped to around 50%. Also, we can observe that removing the CNN layer makes the model more worse as compared to removing the attention layer. This shows that the CNN part of the architecture plays an important role in ambiguity detection. Also, we can see a significant drop in performance in most of the cases, if we replace the LSTM units with GRU units. The reason for the same is that LSTM units are able to capture context better than GRU because a sufficient number of samples are provided to our model to learn the context. When a sufficient number of samples are available for training, we can expect the LSTM model to learn the context better than GRU (gruber2020gru, ). Hence, this analysis shows the importance of different layers in our proposed framework.

Combining all these layers, makes the system perform almost 100 percent accurately on the test set, which shows that these ambiguities can be easily learned if we define the architecture which can capture context, interrelationships, and attention of output on input. In some cases, we observe that other variations are also giving perfect results which highlight that for those properties simpler network can also be generalizable on unseen test data.