{"id":721234,"date":"2021-01-26T22:23:26","date_gmt":"2021-01-27T06:23:26","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-blog-post&p=721234"},"modified":"2021-01-28T02:48:32","modified_gmt":"2021-01-28T10:48:32","slug":"neurips-2020-ai-programming-going-from-copying-and-pasting-to-inference-synthesis","status":"publish","type":"msr-blog-post","link":"https:\/\/www.microsoft.com\/en-us\/research\/articles\/neurips-2020-ai-programming-going-from-copying-and-pasting-to-inference-synthesis\/","title":{"rendered":"NeurIPS 2020 | AI Programming: Going from Copying and Pasting to Inference Synthesis"},"content":{"rendered":"

Editor\u2019s note: AI programming is one of the great expectations that people have for artificial intelligence. Although current AI programming technology has benefitted many ordinary users who do not know how to program, it still has a long way to go to reach human-level. One weakness is that existing AI can only memorize, copy and paste mechanically, which renders it difficult to flexibly deal with people\u2019s needs. The new neural model LANE (Learning Analytical Expressions) proposed by Microsoft Research Asia can simulate humans\u2019 abstract way of thinking, thereby achieving compositional generalization capability in AI programming.<\/p>\n

Let\u2019s begin with AI Programming<\/h2>\n

Allowing AI to learn to write programs is a common hope that people have, where you can describe what you want using natural language, and AI would be able to automatically generate the corresponding program. Existing AI programming technology is not yet able to do this, but related technology, in more general forms, has already benefitted a large number of users without programming abilities in various fields. For example, Microsoft demonstrated a new feature in Excel at its Ignite 2019 Conference that enables Excel to automatically understand and perform intelligent data analysis when a user asks a question, and then to present the results in visual charts (as shown in Figure 1) [1]. The technical support behind this super practical function is a series of AI programming technologies that convert natural language into data analysis programs. Another example is the intelligent dialogue service developed by Microsoft\u2019s Sematic Machines team, built precisely on program synthesis [2].<\/p>\n

\"\"

Figure 1: Conversational data analysis in Excel based on AI programming technology<\/p><\/div>\n

The AI programming technology discussed in this article refers to using a natural language sentence as the input and obtaining a corresponding machine interpretable\/executable program as the output. Here program is usually written by a known DSL (Domain Specific Language).\u00a0 Researchers in the field of natural language processing may be more familiar with another term for this task: semantic parsing.<\/p>\n

However, even with such restrictions, existing AI programming technology still does not always deliver satisfactory results. One major weakness is that the AI technology seems to have only learned how to memorize, copy and paste mechanically using the known code base but cannot generate truly suitable programs to flexibly serve people\u2019s needs.<\/p>\n

\"\"

Figure 2: The current state of AI programming<\/p><\/div>\n

Take the comic in Figure 2 as an example (adapted from [3]). When a user\u2019s requirements are relatively simple and the AI programming robot is able to find a program that can fulfill the requirements in a large code base, the results are generally good. However, if the user\u2019s requirements are relatively complex, the robot needs to have a certain level of reasoning capabilities (i.e., the required program does not exist in known code bases, and composing needs to be carried out on parts of existing programs). In such cases, the results are usually unsatisfactory.<\/p>\n

The research work covered in this article uses this as a starting point and aims at exploring how AI programming can be made to go beyond copying and pasting and learn human-like reasoning capabilities, so as to more effective in synthesizing programs.<\/p>\n

Compositional generalization is the key to creating humanoid AI<\/h2>\n

The core to the problem discussed in the previous section of the article can be attributed to the issue of achieving \u201ccompositional generalization\u201d capability in AI systems. Put more plainly, the issue is whether the AI system has the ability to draw inferences, where it\u2019s able to decompose known complex objects (i.e. the \u201cprogram\u201d discussed in this article) into a composition of multiple known simple objects, then understand\/generate unknown combination of these known simple objects accordingly.<\/p>\n

Humans have a natural ability to carry out compositional generalization. For example, take a person who has never been exposed to the concept of a platypus. He only needs to look at a photo of a platypus to identify it, and afterwards, he would be able to understand certain complex phrases with a picture in mind, such as, \u201cThree platypuses are sitting side by side holding eggs,\u201d or \u201cTwo platypuses have started digging by the shore after catching small fish in the river,\u201d and so on. This is very different from deep learning, which requires a great amount of annotated data even just to learn the concept of a platypus, never mind learning various complex combination of the concept.<\/p>\n

From a linguistics perspective, the compositional generalization capability of human is mainly reflected in systematicity<\/em> and productivity<\/em>. Systematicity can be simply understood as the local replacement of known expressions. For example, if a person understands the word \u201cplatypus\u201d and the phrase \u201ca dog in the living room,\u201d then he is also able to understand the phrase \u201ca platypus in the living room.\u201d Productivity can be simply understood as the construction of more complex expressions with relatively simple expressions through potential universal laws. For example, if a person understands the word \u201cplatypus\u201d and the clause \u201ca dog in the living room,\u201d then he is also able to understand the phrase \u201ca platypus and a dog in the living room.\u201d<\/p>\n

\"\"

Figure 3: Compositional generalization capability is mainly reflected in systematicity and productivity \uff08image source: https:\/\/arxiv.org\/pdf\/1908.08351.pdf)<\/p><\/div>\n

Linguist and philosopher Chomsky describes language as a system that makes\u00a0\u201cinfinite use of finite means.” Human intelligence has relied on compositional generalization to gradually create a complex and even infinite world of semantics using the most basic elements. It can be said that compositional generalization is a basic ability that humanoid AI must possess.<\/p>\n

Deep learning lacks compositional generalization capability<\/h2>\n

Programs are compositional.\u00a0 Even a small DSL (limited domain, simple grammar, and limited redefined functions) can produce an exponentially large program space. The programs included in the training data set are only the tip of the iceberg in any program space. Therefore, if an AI programming robot lacks compositional generalization capability, it would inevitably lead to instances of \u201cartificial mental retardation\u201d as reflected in the comic above.<\/p>\n

Considering this perspective, an increasing number of research works are beginning to re-examine existing deep learning-base AI programming solutions. Most of current mainstream solutions are based on Neural Encoder-Decoder Architectures. A series of studies conducted by New York University professor Brenden Lake and Facebook AI scientist Marco Baroni have shown that existing deep learning models do not have compositional generalization capability [4]. Figure 4 briefly illustrates their research method. The experimental task is to translate natural language phrases such as \u201crun after walk\u201d into instruction sequences (programs) such as \u201cWALK RUN.\u201d<\/p>\n

\"text,

Figure 4: It\u2019s difficult for existing deep learning models to generalize to combinations outside the training set, even for simple tasks.<\/p><\/div>\n

On the surface, this appears to be a simple sequence-to-sequence generation task. A large number of natural language phrases and their corresponding instruction sequences are collected and randomly divided into a training set and a test set, then an existing deep learning model is used for training, allowing up to 99.8% accuracy on the test set. However, once restrictions are added to the division method between the training set and the test set from a compositional perspective, the deep learning model is no longer effective. For example, in order to verify the systematicity of the model, we can prevent the model from seeing any sample related to \u201cjump\u201d except for \u201cjump -> JUMP\u201d. And then in the testing phase, we can evaluate if the model can perform correctly with phrases including \u201cjump\u201d (e.g. \u201cjump around left\u201d). Experimental results show that under such a setting, the deep learning model can only achieve an accuracy rate of 1.2%.<\/p>\n

On the other hand, in order to verify the productivity of the model, we can only expose the model to samples with an instruction sequence length of less than 24 during the training phase, and then in the testing phase, we can see if the model can correctly generate an instruction sequence with a length no less than 24. Experimental results have shown that under such a setting, the deep encoder-decoder network can only achieve an accuracy rate up to 20.8%. A series of similar studies demonstrate that existing deep learning models do not have the ability for compositional generalization in semantic parsing tasks [4][5].<\/p>\n

In current industrial practices, practitioners mainly use a hybrid system of deep learning and heuristic rules to alleviate this bottleneck (data augmentation can also be included, since deciding what data needs to be augmented usually requires manual induction.) This article seeks to explore a more interesting idea, which is if it would be possible to introduce appropriate inductive biases in deep learning to get rid of simple memory and imitation without introducing heuristic rules, but rather to automatically explore, discover, and summarize the inherent compositional laws of the dataset, so as to endow the end-to-end deep neural network with compositional generalization capability.<\/p>\n

Simulating the abstract thinking of human brains in a deep neural network<\/h2>\n

Human cognition is capable of compositional generalization in large part because of abstraction, that is, omitting the specific details of things to reduce the amount of information contained in them, which is more conducive to discovering the common ground (laws) between things.<\/p>\n

This ability for abstraction is a type of algebraic ability, which is precisely what existing deep neural networks lack. As shown in Figure 5 on the left, existing deep neural networks are more inclined towards memorization for AI programming tasks. Natural language and programming language are regarded as two separate sets, so what\u2019s learned are only simple mapping between specific natural language phrases and specific programs. It would thus be difficult to realize compositional generalization. To tackle this problem, the key idea is to treat natural language and programming as two algebraic structures, and the deep neural network needs to incline towards learning the homomorphism between these two algebraic structures (as shown in Figure 5 on the right).<\/p>\n

\"graphical

Figure 5: Learning the homomorphism between algebraic structures rather than learning the mapping between sets<\/p><\/div>\n

Put more expressly, if the training data already contains samples such as \u201crun opposite walk,\u201d \u201crun after left,\u201d and \u201cwalk twice,\u201d we are now presented with the following example:<\/p>\n

INPUT: \u201crun opposite left after walk twice\u201d<\/em><\/p>\n

OUTPUT: \u201cWALK WALK LTURN LTURN RUN\u201d<\/em><\/p>\n

Existing deep learning models are to remember the mapping between such input and output pairs, while human cognition tends to make abstractions as shown in Figure 6.<\/p>\n

\"\"

Figure 6: Compared with the direct memorization and imitation of deep learning, human thinking is more inclined to take concrete objects and abstract them hierarchically into common analytical expressions.<\/p><\/div>\n

The left side of Figure 6 shows the abstraction process of the natural language sentence used as input from the bottom to up. In steps 1,2, and 4, the specific meanings of the three words \u201crun,\u201d \u201cleft,\u201d and \u201cwalk\u201d are stripped off respectively and abstracted into variables. In steps 3, 5, and 6, the meanings of the three clauses \u201c$x opposite $y,\u201d \u201c$y twice\u201d and \u201c$x after $y\u201d are stripped off respectively and are also abstracted into variables. What humans remember is not the direct mapping between input and output, but the collection of local mappings (shown in Figure 6 on the right) produced at each step of this abstraction process. For example, in step 1, the word \u201crun\u201d is mapped to the program \u201cRUN\u201d; in step 3, the abstract clause \u201c$x opposite $y\u201d is mapped to the program \u201c$Y $Y $X.\u201d The \u201c$X\u201d here is a variable in a program, referring to the program corresponding to the variable \u201c$x\u201d in natural language.<\/p>\n

The above example illustrates that rather than directly remembering relatively complex and specific mappings, humans are more inclined to generalize relatively simple common abstract mappings from them, thereby obtaining compositional generalization capabilities. Therefore, in order to also endow compositional generalization capabilities to deep learning models, it is necessary to design a new neural model that can simulate the abstraction process in human cognition.<\/p>\n

Formalizing each specific input\/output object is called Source Expression (SrcExp) \/Destination Expression (DstExp), which is collectively referred to as Expression (Exp). If one part or some parts of the expression is\/are replaced with variables, the expression would be called an Analytical Expression (AE). Similarly, analytical expressions can also be divided into Source Analytical Expressions (SrcAE) and Destination Analytical Expressions (DstAE).<\/p>\n

The neural model needs to gradually transform each input SrcExp into a simpler SrcAE through several abstract operations (as shown in Figure 6 on the left). In this abstraction process, every SrcAE that is replaced with a variable is parsed as a DstAE. In the end, these DstAEs are composed into a DstExp as the output (as shown in Figure 6 on the right). The model requires the use of this abstraction process as a type of inductive bias, completing the exploration and study of the specific abstraction process and expression mapping in a fully automated process, without relying on any artificially predefined abstraction\/mapping rules.<\/p>\n

Model implementation of LANE<\/h2>\n

The new neural model LANE (Learning Analytical Expressions) can simulate human abstract thinking in semantic parsing tasks, thereby achieving compositional generalization. In previous neural network learning frameworks, the neural network is directly used to learn the mapping function from a Source Token Sequence to a Destination Token Sequence. In LANE, what needs to be learned is a function whose source domain and target domain are respectively derived from the abstraction of the source token sequence and the analytical expression of the destination token sequence.<\/p>\n

LANE consists of two neural network modules. One module is called Composer and is implemented by a TreeLSTM model. It is responsible for the latent tree induction of the input SrcExp, thus delivering a gradually abstracted and simplified intermediate SrcAE. The other module is called Solver and is responsible for performing local semantic parsing every time abstraction occurs, stripping the semantic details and storing them in Memory, so that these details are simplified to a variable in subsequent processing.<\/p>\n

\"\"

Figure 7: Use neural networks to learn implicit analytical expressions to simulate human abstract thinking<\/p><\/div>\n

Figure 7 explains the workflow of LANE and also shows how it handles the fifth and sixth steps of abstraction in Figure 6. In the fifth step, Composer outputs the next abstract action based on the LSTM for the current SrcAE \u201c$x after $y twice\u201d; \u201c$y twice\u201d should be abstracted. Solver uses a deep encoder-decoder network to interpret \u201c$y twice\u201d as DstAE \u201c$Y $Y\u201d and compose it with \u201c$Y = WALK\u201d in the original memory to obtain DstExp \u201cWALK WALK\u201d corresponding to the new variable, and update the memory accordingly. After this process, the details of \u201c$y twice\u201d in \u201c$x after $y twice\u201d are stripped off, forming a more abstract SrcAE \u201c$x after $y\uff0c\u201d after which the sixth step of abstraction can proceed. This way, Composer and Solver work together, allowing LANE to gradually abstract the input SrcExp into an increasingly simplified SrcAE until it forms the simplest SrcAE composed of a single variable. The corresponding value of this variable in the memory is the final output DstExp.<\/p>\n

Since LANE contains operations that not differentiable, the training of the model can be realized based on reinforcement learning. Model training has the following three key points:<\/p>\n

    \n
  1. Reward design: Reward is divided into two parts: one part is based on similarity, that is, the degree of sequence similarity between the DstExp generated by the model and the real DstExp. The other part is the reward based on simplicity, which is inspired by Occam\u2019s razor principle and is used to encourage the model to generate more general\/concise analytical expressions. Since there was no deliberate introduction of any special task-related knowledge in the design of these two rewards, this shows that LANE likely has great universality.<\/li>\n
  2. Hierarchical Reinforcement Learning: Composer and Solver work together, but they have different positioning. Solver\u2019s decision depends on Composer\u2019s decision. Therefore, regarding Composer and Solver as a high-level agent and a low-level agent respectively, hierarchical reinforcement learning is applied to jointly train these two modules.<\/li>\n
  3. Curriculum Learning: In order to enhance the efficiency of exploration, the data is divided according to the length of input sequence into multiple courses ranging from simple to difficult. The model is first trained on the simplest course, and then more difficult courses are gradually added.<\/li>\n<\/ol>\n

    Experimental Results<\/h2>\n

    Lake et al. established a benchmark dataset called SCAN to evaluate the compositional generalization capability of semantic parsing systems. Multiple subtasks are derived from this data set to measure compositional generalization capabilities with regards to different aspects. For example, the ADD_JUMP subtask is used to measure the model\u2019s ability to handle a composition of newly introduced elements; and the LENGTH subtask is used to measure the model\u2019s ability to generate compositions that exceed known lengths in the training data. Research and experimental results show that LANE has reached 100% accuracy on these subtasks.<\/p>\n

    \"\"

    Figure 8: LANE achieves 100% accuracy in all SCAN\u2019s subtasks<\/p><\/div>\n

    Figure 9 shows two implicit tree structures learned by Composer (TreeLSTM) in LANE as an example. TreeLSTM is bifurcated in implementation, and the nodes that perform abstract actions are colored black.\u00a0 It can be seen that even without introducing any predefined abstraction\/mapping rules, LANE can automatically explore the abstraction process that conforms to human thinking.<\/p>\n

    \"\"

    Figure 9: Example: Two implicit tree structures learned by LANE<\/p><\/div>\n

    The new end-to-end neural model LANE can simulate human abstract thinking ability to learn the potential analytical expression mapping in the data, so as to obtain the compositional generalization ability in the AI programming (semantic parsing) task. Researchers at Microsoft Research Asia hope to use this as a starting point to explore how deep learning can go from the \u201cparrot paradigm\u201d (memorization and imitation) to the \u201ccrow paradigm\u201d (exploration and induction), thereby expanding the boundaries of its capabilities. However, this is still preliminary theoretical research, and a great amount of follow-up work needs to be done in order to apply it to more complex tasks (such as improving training efficiency, improving fault-tolerant learning ability, combining with unsupervised methods, etc.).<\/p>\n

    Paper: https:\/\/arxiv.org\/abs\/2006.10627<\/p>\n

    Code: https:\/\/github.com\/microsoft\/ContextualSP<\/p>\n","protected":false},"excerpt":{"rendered":"

    Editor\u2019s note: AI programming is one of the great expectations that people have for artificial intelligence. Although current AI programming technology has benefitted many ordinary users who do not know how to program, it still has a long way to go to reach human-level. One weakness is that existing AI can only memorize, copy and […]<\/p>\n","protected":false},"author":34512,"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-content-parent":199560,"msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-locale":[268875],"msr-post-option":[],"class_list":["post-721234","msr-blog-post","type-msr-blog-post","status-publish","hentry","msr-locale-en_us"],"msr_assoc_parent":{"id":199560,"type":"lab"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-blog-post\/721234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-blog-post"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-blog-post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/34512"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-blog-post\/721234\/revisions"}],"predecessor-version":[{"id":721642,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-blog-post\/721234\/revisions\/721642"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=721234"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=721234"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=721234"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=721234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}