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.
- 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.
- Execution: The system applies this formula to a Game Instance (Freecell) to predict if a move is legal.
- Feedback: The environment provides a binary signal (Correct/Incorrect).
- 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 model manages three critical decision types:
- Lexical Mapping (1st-order): Ensuring words align with logical symbols.
- Argument Sharing (2nd-order): Ensuring predicates (like
TOPandMOVE) 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
FREECELLrule, accuracy improved from an initial 0.78 to 0.956. - Generalization: When given brand-new instructions, the system achieved 0.967 accuracy for the
FREECELLconcept, demonstrating that the learned semantic interpreter generalizes well. - Complexity Challenges: Performance was lower on the
TABLEAUconcept (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