We consider the problem of weakly supervised structured prediction (SP) with reinforcement learning (RL) – for example, given a database table and a question, perform a sequence of computation actions on the table, which generates a response and  receives  a  binary  success-failure  reward.    This  line  of  research  has  been successful by leveraging RL to directly optimizes the desired metrics of the SP tasks – for example, the accuracy in question answering or BLEU score in machine translation.   However, different from the common RL settings, the environment dynamics is deterministic in SP, which hasn’t been fully utilized by the model-freeRL methods that are usually applied. Since SP models usually have full access to the environment dynamics, we propose to apply model-based RL methods, which rely on planning as a primary model component. We demonstrate the effectiveness of planning-based SP with a Neural Program Planner (NPP), which, given a set of candidate programs from a pretrained search policy, decides which program is the most promising considering all the information generated from executing these programs. We evaluate NPP on weakly supervised program synthesis from natural language(semantic parsing) by stacked learning a planning module based on pretrained search policies. On the WIKITABLEQUESTIONS benchmark, NPP achieves a new state-of-the-art of 47.2% accuracy. Numerous results from natural language processing tasks have shown that Structured Prediction (SP) can be cast into a reinforcement learning (RL) framework, and known RL techniques can give formal performance bounds on SP tasks BID3 BID13 BID0 . RL also directly optimizes task metrics, such as, the accuracy in question answering or BLEU score in machine translation, and avoids the exposure bias problem when compaired to maximum likelihood training that is commonly used in SP BID13 BID12 .However , previous works on applying RL to SP problems often use model-free RL algorithms (e.g., REINFORCE or actor-critic) and fail to leverage the characteristics of SP, which are different than typical RL tasks, e.g., playing video games BID9 or the game of Go BID15 . In most SP problems conditioned on the input x, the environment dynamics, except for the reward signal, is known, deterministic, reversible, and therefore can be searched. This means that there is a perfect model 1 of the environment, which can be used to apply model-based RL methods that utilize planning 2 as a primary model component.Take semantic parsing BID1 BID11 as an example, semantic parsers trained by RL such as Neural Semantic Machine (NSM) BID8 typically rely on beam search for inference -the program with the highest probability in beam is used for execution and generating answer. However, the policy, which is used for beam search, may not be 1 A model of the environment usually means anything that an agent can use to predict how the environment will respond to its actions BID17 .2 planning usually refers to any computational process that takes a model as input and produces or improves a policy for interacting with the modeled environment BID17 able to assign the highest probability to the correct program. This limitation is due to the policy predicting locally normalized probabilities for each possible action based on the partially generated program, and the probability of a program is a product of these local probabilities.For example, when applied to the WEBQUESTIONSSP task, NSM made mistakes with two common patterns: (1) the program would ignore important information in the context; (2) the generated program does not execute to a reasonable output, but still receives high probability (spurious programs). Resolving this issue requires using the information of the full program and its execution output to further evaluate its quality based on the context, which can be seen as planning. This can be observed in Figure 4 where the model is asked a question "Which programming is played the most?". The full context of the input table (shown in TAB0 ) contains programming for a television station. The top program generated by a search policy produces the wrong answer, filtering by a column not relevant to the question. If provided the correct contextual features, and if allowed to evaluate the full program forward and backward through time, we observe that a planning model would be able to better evaluate which program would produce the correct answer.To handle errors related to context, we propose to train a value function to compute the utility of each token in a program. This utility is evaluated by considering the program and token probability as well as the attention mask generated by the sequence-to-sequence (seq2seq) model for the underlying policy. We also introduce beam and question context with a binary feature representing overlap from question/program and program/program, such as how many programs share a token at a given timestep.In the experiments, we found that applying a planner that uses a learned value function to re-rank the candidates in the beam can significantly and consistently improve the accuracy. On the WIKITABLEQUESTIONS benchmark, we improve the state-of-the-art by 0.9%, achieving an accuracy of 47.2%. Reinforcement learning applied to structured prediction suffers from limited use of the world model as well as not being able to consider future and past program context when generating a sequence. To overcome these limitations we proposed Neural Program Planner (NPP) which is a planning step after candidate program generation. We show that an additional planning model can better evaluate overall structure value. When applied to a difficult SP task NPP improves state of the art by 0.9% and allows intuitive analysis of its scoring model per program token.A MORE NPP SCORING DETAILS
A model-based planning component improves RL-based semantic parsing on WikiTableQuestions.
{"src": "scitldr-AIC_train", "paper_id": "HJxPAFgEON"}