Learning from Natural Instructions

Dan Goldwasser, Dan RothIJCAI 2011 · OpenReview

Abstract

Machine learning is traditionally formalized and investigated as the study of learning concepts and decision functions from labeled examples, requiring a representation that encodes information about the domain of the decision function to be learned. We are interested in providing a way for a human teacher to interact with an automated learner using natural instructions, thus allowing the teacher to communicate the relevant domain expertise to the learner without necessarily knowing anything about the internal representations used in the learning process. In this paper, we view the process of learning a decision function as a natural language lesson interpretation problem. We introduce a learning algorithm that receives feedback from its performance on the final task, while learning jointly (1) how to interpret the lesson and (2) how to use this interpretation to do well on the final task. We evaluate our approach by applying it to the rules of the solitaire card game Freecell, showing that our approach can use natural language instructions to learn target concepts and generalize to previously unseen instructions.

Introduction

Traditional machine learning is data-hungry, typically requiring massive datasets of labeled examples to teach a model a new concept. This process is expensive, time-consuming, and requires significant expertise to curate. Humans, however, learn differently; we often learn from "lessons" consisting of high-level instructions and a few clarifying examples. This paper addresses the challenge of instructable computing: creating a learner that can communicate with a human teacher via natural language (NL). The core difficulty is the "semantic gap"—mapping ambiguous NL to a rigid formal logic that a computer can execute without requiring expensive gold-standard logical annotations.

The Lesson Interpretation Framework

The authors propose a framework that treats learning as a lesson interpretation problem. Instead of learning from static examples, the system learns to interpret instructions by trying them out in a game environment. This process is governed by an iterative feedback loop.

The feedback loop: from natural instruction to real-world behavior.
  1. Interpretation: The system takes an NL instruction (e.g., "You can move any top card to an empty freecell") and uses a Semantic Interpreter to map it to a logical formula.
  2. Execution: The system applies this formula to a Game Instance (Freecell) to predict if a move is legal.
  3. Feedback: The environment provides a binary signal (Correct/Incorrect).
  4. Learning: This signal trains a binary classifier (an SVM) that updates the interpreter's weights to favor logical structures leading to correct behavior.

Semantic Interpretation via ILP

To handle the complexity of mapping text to logic, the interpretation is formulated as an Integer Linear Program (ILP). This allows the system to enforce global constraints on the output formula, ensuring it is a single, coherent "tree" rather than disconnected fragments.

The ILP decision space: (a) 1st-order lexical mapping, (b) 2nd-order argument sharing, and (c) flow variables for connectivity.

The ILP model manages three critical decision types:

  • Lexical Mapping (1st-order): Ensuring words align with logical symbols.
  • Argument Sharing (2nd-order): Ensuring predicates (like TOP and MOVE) correctly share variables (like the card ID).
  • Connectivity: Using flow variables to ensure the resulting logical formula is structurally sound.

Experimental Evaluation

The approach was evaluated using the Freecell solitaire card game, focusing on three rules: FREECELL, HOMECELL, and TABLEAU. For each concept, 25 different natural language instructions were collected from humans. The system was evaluated on 900 randomly sampled game moves.

Key Results

  • Concept Accuracy: For the FREECELL rule, accuracy improved from an initial 0.78 to 0.956.
  • Generalization: When given brand-new instructions, the system achieved 0.967 accuracy for the FREECELL concept, demonstrating that the learned semantic interpreter generalizes well.
  • Complexity Challenges: Performance was lower on the TABLEAU concept (improving from 0.536 to 0.628) due to its higher logical complexity involving colors, values, and successor relationships.

Discussion and Future Work

A key insight of this work is learning from failure: by identifying interpretations that lead to illegal moves, the system prunes away incorrect semantic mappings. Furthermore, the joint learning approach allows the model to apply knowledge of terms like "top card" or "empty" across different rules.

While successful, the system currently relies on a small pre-defined seed lexicon and immediate feedback. Future work will explore scaling to more complex logic, reducing reliance on initial lexicons, and integrating with reinforcement learning for full game-playing agents.

Summary updated

Abstract

Machine learning is traditionally formalized and investigated as the study of learning concepts and decision functions from labeled examples, requiring a representation that encodes information about the domain of the decision function to be learned. We are interested in providing a way for a human teacher to interact with an automated learner using natural instructions, thus allowing the teacher to communicate the relevant domain expertise to the learner without necessarily knowing anything about the internal representations used in the learning process. In this paper we suggest to view the process of learning a decision function as a natural language lesson interpretation problem, as opposed to learning from labeled examples. This view of machine learning is motivated by human learning processes, in which the learner is given a lesson describing the target concept directly and a few instances exemplifying it. We introduce a learning algorithm for the lesson interpretation problem that receives feedback from its performance on the final task, while learning jointly (1) how to interpret the lesson and (2) how to use this interpretation to do well on the final task. traditional machine learning by focusing on supplying the learner only with information that can be provided by a task expert. We evaluate our approach by applying it to the rules of the solitaire card game. We show that our learning approach can eventually use natural language instructions to learn the target concept and play the game legally. Furthermore, we show that the learned semantic interpreter also generalizes to previously unseen instructions.
BibTeX
@inproceedings{goldwasser2011learning,
  author = {Dan Goldwasser and Dan Roth},
  title = {{Learning from Natural Instructions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=HJE2zSM_WS},
}
Figure