# ADAM: A Sandbox for Implementing Language Learning

Ryan Gabbard<EMAIL_ADDRESS>All work done while at ISI, prior to
joining Amazon. Information Sciences Institute, University of Southern
California  Deniz Beser<EMAIL_ADDRESS>Information Sciences Institute,
University of Southern California  Jacob Lichtefeld<EMAIL_ADDRESS>Information
Sciences Institute, University of Southern California  Joe Cecil<EMAIL_ADDRESS>Information Sciences Institute, University of Southern California  Mitch
Marcus  Department of Computer and Information Science, University of
Pennsylvania  Sarah Payne  Department of Computer and Information Science,
University of Pennsylvania  Department of Linguistics, University of
Pennsylvania  Charles Yang  Department of Computer and Information Science,
University of Pennsylvania  Department of Linguistics, University of
Pennsylvania  Marjorie Freedman  Information Sciences Institute, University of
Southern California

###### Abstract

We present ADAM, a software system for designing and running child language
learning experiments in Python. The system uses a virtual world to simulate a
grounded language acquisition process in which the language learner utilizes
cognitively plausible learning algorithms to form perceptual and linguistic
representations of the observed world. The modular nature of ADAM makes it
easy to design and test different language learning curricula as well as
learning algorithms. In this report, we describe the architecture of the ADAM
system in detail, and illustrate its components with examples. We provide our
code.111Our code is available at https://github.com/isi-vista/adam

Keywords: Language Acquisition, Cognitive Modeling

##  1 Introduction

ADAM is a software “sandbox” for experiments in child language learning. It
enables an experimenter with a modest degree of Python programming experience
to quickly and compactly specify a curriculum consisting of a sequence of
situations in a virtual world. It then projects these situations into
customizable linguistic representations and non-linguistic perceptual
representations which can be consumed by learning algorithms. It also provides
a framework for evaluating learner performance both during and after the
learning phase. This approach provides several advantages:

  * •

Learning from language together with concrete situations captures the fact
that humans learn language not from language alone but rather from language
grounded in particular situations.

  * •

Using a virtual world for our grounding makes it easy for a researcher to
design custom curricula for their experiments (see section 3.2).

  * •

Using a virtual world for grounding provides the learner with a realistic
model of a pre-linguistic infant’s perception of the world (see section 3.4)
as grounding, rather than, for example, raw pixels.

  * •

Generating language from situations enables performing experiments across
multiple languages by only swapping out one system module (the language
generator; see section 3.3).

  * •

Generating the curriculum and perceptions in Python code makes it easy to
perform variations on experiments, including adding irrelevant situations,
adding noise to the perceptual representations, and altering word
distributions.

In the main body of this report, we first review relevant background in the
language acquisition literature. Then, we describe the ADAM system
architecture at a high level and then provide some examples of what it learns
from a simple sample curriculum. We then describe related work and directions
for future work. Finally, a series of appendices provide detailed descriptions
of system components.

Figure 1: A High-level architecture diagram, which happens in a loop.

##  2 Background

The current literature consists of several proposals for children’s word
learning process which fall into two broad groups. ‘Global’ approaches (e.g,
?, ?, ?, ?, ?, ?) resolve uncertainty by aggregating situational data over
time to identify the best supported word-referent associations. By contrast,
‘local’ approaches (e.g, ?, ?, ?, ?, ?) attempt to resolve uncertainty
immediately: in the simplest form, the learner hypothesizes a word meaning,
maintains it when the word is heard if it is confirmed (e.g. is present in the
observed situation) but replaces it with a new meaning if disconfirmed.
Additionally, there are models that combine aspects of both approaches (?, ?),
where only actively hypothesized meanings are maintained (as in the local
approach), whose associations with the word change probabilistically in
response to the cumulative effect of learning instances (as in the global
approach).

Most previous computational research has focused on the modeling of behavioral
results from word learning experiments or the quantitative assessment of the
models’ effectiveness on (small) annotated child-directed input corpora.
Larger-scale simulation studies (e.g, ?, ?, ?, ?), by contrast, are evaluated
on arbitrary word-reference mappings that bear little resemblance to the
linguistic, cognitive, and perceptual information available to the child
learner.

Moreover, the words used in previous studies are most often basic-level terms
(_dog_), sometimes reflecting different levels of carefully constructed
conceptual taxonomy (‘husky’, ‘dog’, ‘animal’) (e.g, ?, ?, ?). The meanings of
the words are almost always atomic. In the real world, however, word meanings
can only be learned by making subtle and incremental refinements. For
instance, the word _chair_ is used for referents with highly variable
attributes (size, color, number of legs, etc.).

ADAM aims to provide a computational platform that enables systematic studies
of how the structure of the learning data, the perceptual complexity of the
learning environment, and the cognitive resources available to the learner
collectively impact the effectiveness of the language acquisition models. In
the following sections, we describe the ADAM system in detail.

##  3 High-level System Architecture

At the highest level, the ADAM system is a loop where a language learner
repeatedly perceives situations (states of the world or transitions between
such states) paired with linguistic utterances (Figure 1). After each
observation, the learner updates its internal state. The sequence of
situations observed by the learner is called a curriculum. At any time, the
learner can perceive a new situation and be asked to generate a relevant and
appropriate utterance.

Figure 2 displays the full architecture, which has three notable additions.
First, the learner has no direct access to the situations in the curriculum.
Instead, it receives only a pairing of a linguistic representation (section
3.3) and a perceptual representation (section 3.4) which are both generated
from a situation representation (section 3.1) by the language generator
(section 3.3) and perception generator (section 3.4), respectively. In the
current implementation, these representations are meant to model an 18-month-
old’s perception of the world around them. Second, we provide situation
templates, which are a compact way for an experimenter to specify a large
curriculum (section 3.2). Third, an evaluator allows for tracking learning
progress and evaluating experiments (section 3.6).

Below we describe the components of the system in more detail.

Figure 2: A Mid-level architecture diagram, with additional detail added to
the processing loop.

###  3.1 Situations and Curricula

A situation is an abstract description of either a state or action in the
world. A curriculum is a sequence of situations. Situations are never accessed
directly by the learner but rather only through the mediation of a derived
perception (section 3.4).

A situation consists of a set of objects which may have properties, a set of
relations between these objects, and a set of actions which occur. Object
locations are not encoded via coordinates but only in terms of regions which
are defined with respect to other objects; the way these regions are defined
is largely drawn from ? (?). Objects, object properties, and relations are
drawn from a user-defined ontology; this ontology is for the convenience of
the curriculum designer only and is _not_ accessible to the language learner.
Certain aspects of a situation may be marked as salient, meaning they will be
remarked upon in linguistic utterances derived from this situation.

More detail on the representation of situations (appendix B) and ontologies
(appendix A) may be found in the appendices.

###  3.2 Situation Templates

Figure 3: A simple situation template which will generate many concrete
situations where an object is sitting on some flat surface.

Defining every situation in a realistic curriculum consisting of thousands or
millions of instances would be impractical. Instead, we allow researchers to
use a simple Python-based domain-specific language to specify situation
templates (Figure 3). For example, a situation template like x[+ANIMATE,
+HUMAN] $\wedge$ y[+ INANIMATE] $\wedge$ MANIPULATION_ACTION(x, y) $\wedge$
RELATIVE_SIZE(SMALLER, y, x) could be instantiated by PICK_UP(PERSON, CUP) or
ROLL(DOG, BALL).

Situation templates have a similar structure to situations, but where
situations contain objects, properties, relations, and actions situation
templates can instead contain template variables which range over elements of
the user-defined hierarchical ontology. Restrictions can be placed on how
these variables may be filled. A situation generator then reads these
templates and instantiates the templates using either exhaustive enumeration
or configurable sampling strategies.

Because situation templates are defined using Python code, the creation of
templates can itself be automated. This can be useful, for example, to easily
test all possible combinations of multiple experimental parameters.

###  3.3 Linguistic Representation

Any sequence of discrete symbols can in principle work as a linguistic
representation for ADAM (phonemes, morphemes, etc.). In the default
implementation, we use English orthographic words222The plural marker is split
off as its own token; learning morphonology could be done in an extended
version of the default ADAM implementation and Yale romanization for Chinese.

Linguistic representations are not directly specified as part of a curriculum
but instead are generated from situation representations by a language
generator. This results in a key strength of ADAM: experiments can be
performed in multiple languages from the same curriculum simply by swapping
the language generator component. The initial language generator
implementations for English and Chinese are described in Appendix E.

###  3.4 Perceptual Representation

The language learner is not permitted to observe situations directly. Instead,
a perception generator module first translates them to perceptual
representations. The default implementation uses a perceptual representation
designed to mimic those of a roughly 18-month-old child.

This default representation includes object shape and structure
representations derived from (?, ?) and (?, ?); region and path information
derived from (?, ?); a small set of object properties, such as liquid and
self-moving; the ability of the language learner to recognize particular
familiar individuals; information on what objects are gazed at by the speaker
(?, ?); very coarse grained relative size and possession relationships; which
objects are the speaker and addressee; and proto-roles such as stationary,
causes-change, and volitionally-involved derived from (?, ?).

The perception generator component could be swapped for a different
implementation to run experiments with a different perceptual representation.
It is also possible to parameterize the current implementation to allow for
the addition, exclusion, or unreliable perception of aspects of the
representation.

Ontology Type | Ontology Subtypes
---|---
thing | inanimate-object, head, hand, person, animal,
| body-part
person | me, you, Mom, Dad, baby
animal | dog, cat, bear, bird, chicken, cow
relation | in-region, spatial-relation, partOf, size-relation,
| axis-relation, has
action | walk, run, consume, put, push, shove, go, come, take,
| grab, give, spin, sit, fall, throw, pass, move, jump,
| roll, fly
property | can-fill-template-slot, substance, is-addressee,
| is-speaker, is-human, perceivable-property,
| can-manipulate-objects, edible, rollable,
| can-have-things-on-them, is-body-part,
| person-can-have, transfer-of-possession,
| can-jump, can-fly, has-space-under,
| can-be-sat-on, fast, slow, side, left, right,
| hard-force, soft-force, aboutSameSizeAsLearner
color | red, blue, green, black, white, light-brown,
| dark-brown, transparent
inanimate-object | substance, ground, food, table, bed, ball,
| paper, book, house, car, cup, box, chair,
| truck, door, hat, (furniture) leg, chairback,
| chairseat, tabletop, mattress, headboard, wall,
| roof, tire, truckcab, trailer, flatbed
Table 1: The sample ontology included with ADAM. These ontology nodes describe
scenes, which are used to generate plausible perception graphs with geons and
other perceptual features, and then provided as input to the learner

###  3.5 Language Learner

In ADAM, a learner is any object which can

  * •

observe pairs of perceptual and linguistic representation and update its
internal state in response.

  * •

observe a perceptual representation and produce a linguistic representation in
response.

We intend ADAM as a “sandbox” where many different learning algorithms can be
implemented. By default, the system includes four learning algorithms: subset
learning, Pursuit (?, ?), Cross-Situational Learning (?, ?), and Propose but
Verify (?, ?). These are described in detail in Appendix H.2, along with a
collection of representations and data structures for learning that can help
researchers implement their own algorithms more easily. While the default
learning algorithms are relatively simple and heuristic, arbitrary learning
algorithms (e.g. deep neural networks, etc.) could be substituted.

###  3.6 Evaluation

The evaluation module allows the user to monitor learning progress (during
training) and the effectiveness of the learned representations (at runtime).
Details on this module are provided in Appendix I.

##  4 Evaluation on a Sample Curriculum

The ADAM system includes a simple sample curriculum. Below, we describe the
content of this curriculum and provide examples of what ADAM learns from it.

###  4.1 Sample Curriculum Content

The ontology of the sample curriculum is shown in Table 1. It consists of the
following situations with:

  * •

single objects

  * •

single objects sitting on the ground

  * •

objects described by color

  * •

objects possessed by the speaker

  * •

objects possessed by a non-speaker

  * •

objects resting upon other objects

  * •

objects placed horizontally beside other objects

  * •

objects positioned vertically relative to other objects

  * •

objects inside other objects

  * •

objects positioned in front of or behind other objects

  * •

examples of all the verbs in the ontology

  * •

examples of objects defined by their function (e.g. chair)

  * •

multiple instances of the same type of object (plurals)

  * •

objects with part-whole relationships

Some samples of what ADAM learns from the curriculum are given in figures 4
through 10. The representation used in these figures is described in Appendix
G.1.

##  5 Conclusions and Future Work

In this report, we presented ADAM, a software system based in Python that can
be used to simulate language acquisition experiments. Various system
capabilities outlined in this report, including the modular abilities to craft
learning curricula as desired (section 3.1) and to build different language
learning algorithms (section 3.5) make ADAM suitable for systematic studies of
language and how language acquisition models are impacted by the learning
data, the perceptual complexity of the learning environment, and the cognitive
resources available to the learner.

There are many future directions to improve the ADAM system. On the language
processing side, the linguistic realization learned for objects, properties,
relations, and actions could be enriched to have syntactic structure, rather
than surface templates (Appendix G.3). Also, the concept to language
generation can be improved to take a situation and generate multiple potential
language descriptions of the scene. Language processing can be done in real
time using audio inputs for generating Speech-To-Text sequences. Similarly,
perceptual processing can be further improved by processing real-world inputs
from 2D or 3D visuals. This would be an undertaking to replace the perception
generation module (Appendix F) with a different processing system.

Experiments with complex scenes is sometimes inconvenient due to ADAM’s core
graph matching algorithms being slow on some perception graphs. To scale up
experimentation, we need to shift the graph matching code from pure Python to
a more efficient language and to explore newer graph matching algorithms than
VF2.

##  6 Acknowledgements

Approved for public release; distribution is unlimited. This material is based
upon work supported by the Defense Advanced Research Projects Agency (DARPA)
under Agreement No. HR00111990060. The views and conclusions contained herein
are those of the authors and should not be interpreted as necessarily
representing the official policies or endorsements, either expressed or
implied, of DARPA or the U.S. Government.

## References

  * Aravind et al.Aravind et al. Aravind, A., de Villiers, J., Pace, A., Valentine, H., Golinkoff, R., Hirsch-Pasek, K., … Wilson, M. S.  (2018).  Fast mapping word meanings across trials: Young children forget all but their first guess.  _Cognition_ , _177_ , 177–188.
  * BiedermanBiederman Biederman, I.  (1987).  Recognition-by-components: a theory of human image understanding.  _Psychological review_ , _94_(2), 115.
  * Blythe, Smith, SmithBlythe et al. Blythe, R. A., Smith, A. D., Smith, K.  (2016).  Word learning under infinite uncertainty.  _Cognition_ , _151_ , 18–27.
  * Conboy, Rivera-Gaxiola, Silva-Pereyra, KuhlConboy et al. Conboy, B. T., Rivera-Gaxiola, M., Silva-Pereyra, J., Kuhl, P. K.  (2008).  Event-related potential studies of early language processing at the phoneme, word, and sentence levels.
  * Cordella, Foggia, Sansone, VentoCordella et al. Cordella, L. P., Foggia, P., Sansone, C., Vento, M.  (2001).  An improved algorithm for matching large graphs.  In _3rd iapr-tc15 workshop on graph-based representations in pattern recognition_ (pp. 149–159).
  * Cordella, Foggia, Sansone, VentoCordella et al. Cordella, L. P., Foggia, P., Sansone, C., Vento, M.  (2004).  A (sub) graph isomorphism algorithm for matching large graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , _26_(10), 1367–1372.
  * DowtyDowty Dowty, D.  (1991).  Thematic proto-roles and argument selection.  _language_ , _67_(3), 547–619.
  * Fazly, Alishahi, StevensonFazly et al. Fazly, A., Alishahi, A., Stevenson, S.  (2010).  A probabilistic computational model of cross-situational word learning.  _Cognitive Science_ , _34_(6), 1017–1063.
  * Goodman, Dale, LiGoodman et al. Goodman, J. C., Dale, P. S., Li, P.  (2008).  Does frequency count? parental input and the acquisition of vocabulary.  _Journal of child language_ , _35_(3), 515–531.
  * Hagberg, Schult, SwartHagberg et al. Hagberg, A. A., Schult, D. A., Swart, P. J.  (2008).  Exploring network structure, dynamics, and function using networkx.  In G. Varoquaux, T. Vaught, J. Millman (Eds.), _Proceedings of the 7th python in science conference_ (p. 11 - 15).  Pasadena, CA USA.
  * Landau JackendoffLandau Jackendoff Landau, B., Jackendoff, R.  (1993).  " what" and" where" in spatial language and spatial cognition.  _Behavioral and brain sciences_ , _16_ , 217–217.
  * MarrMarr Marr, D.  (1982).  Vision: A computational investigation into the human representation and processing of visual information.
  * Medina, Snedeker, Trueswell, GleitmanMedina et al. Medina, T. N., Snedeker, J., Trueswell, J. C., Gleitman, L. R.  (2011).  How words can and cannot be learned by observation.  _Proceedings of the National Academy of Sciences_ , _108_(22), 9014–9019.
  * SiskindSiskind Siskind, J. M.  (1996).  A computational study of cross-situational techniques for learning word-to-meaning mappings.  _Cognition_ , _61_(1), 39–91.
  * Smith, Smith, BlytheSmith et al. Smith, K., Smith, A. D., Blythe, R. A.  (2011).  Cross-situational learning: An experimental study of word-learning mechanisms.  _Cognitive Science_ , _35_(3), 480–498.
  * Spelke KinzlerSpelke Kinzler Spelke, E. S., Kinzler, K. D.  (2007).  Core knowledge.  _Developmental science_ , _10_(1), 89–96.
  * Spencer, Perone, Smith, SamuelsonSpencer et al. Spencer, J. P., Perone, S., Smith, L. B., Samuelson, L. K.  (2011).  Learning words in space and time: Probing the mechanisms behind the suspicious-coincidence effect.  _Psychological science_ , _22_(8), 1049–1057.
  * Spiegel HalberdaSpiegel Halberda Spiegel, C., Halberda, J.  (2011).  Rapid fast-mapping abilities in 2-year-olds.  _Journal of experimental child psychology_ , _109_(1), 132–140.
  * Stevens, Gleitman, Trueswell, YangStevens et al. Stevens, J. S., Gleitman, L. R., Trueswell, J. C., Yang, C.  (2017).  The pursuit of word meanings.  _Cognitive science_ , _41_ , 638–676.
  * Trueswell, Medina, Hafri, GleitmanTrueswell et al. Trueswell, J. C., Medina, T. N., Hafri, A., Gleitman, L. R.  (2013).  Propose but verify: Fast mapping meets cross-situational word learning.  _Cognitive psychology_ , _66_(1), 126–156.
  * VogtVogt Vogt, P.  (2012).  Exploring the robustness of cross-situational learning under zipfian distributions.  _Cognitive Science_ , _36_(4), 726–739.
  * Webster MarcusWebster Marcus Webster, M., Marcus, M.  (1989).  Automatic acquisition of the lexical semantics of verbs from sentence frames ‘.  In _27th annual meeting of the association for computational linguistics_ (pp. 177–184).
  * Xu TenenbaumXu Tenenbaum Xu, F., Tenenbaum, J. B.  (2007).  Word learning as Bayesian inference.  _Psychological Review_ , _114_(2), 245.
  * Yu SmithYu Smith Yu, C., Smith, L. B.  (2007a).  Rapid word learning under uncertainty via cross-situational statistics.  _Psychological Science_ , _18_(5), 414–420.
  * Yu SmithYu Smith Yu, C., Smith, L. B.  (2007b).  Rapid word learning under uncertainty via cross-situational statistics.  _Psychological science_ , _18_(5), 414–420.

Figure 4: ADAM learns that _my_ indicates possession by the speaker. Figure 5:
ADAM learns that for one object to be _on_ another, it needs to not only be
above it, but also in contact with it. Figure 6: ADAM learns that you can only
_roll_ things with circular cross-sections (see the cross-section property on
slot2) Figure 7: ADAM learns that _goes in_ involves the movement of an object
into the interior of a hollow object. Figure 8: ADAM learns that if someone is
eating something, the eater is animate, while the eatee is inanimate and
smaller than the eater, and the eatee becomes interior to the eater Figure 9:
ADAM learns that the thrower loses possession of the object, which traverses a
path above the ground towards someone else. It does not learn that the catcher
necessarily gains possession of the ball (e.g. _The quarterback threw the ball
to the open man, but the receiver dropped it_) Figure 10: ADAM learns you can
only drink liquids.

##  Appendix A Ontologies

An ontology is a collection of object, attribute, relation, and action types
used for two purposes:

  * •

to define the objects, attributes, relations, and actions in a situation and
to provide the necessary information for transforming them into the perceptual
representation

  * •

to define how variables in situation templates may be instantiated. For
example, the arguments of a certain action in a template may be restricted to
animate objects.

An ontology is structured as a collection of ontology nodes with parent-child
relationships. Every node may be associated with a set of ontology node
properties which are inherited by all its child nodes. There are six special
nodes which must be present in any ontology. thing, property, relation, and
action are self-explanatory. perceivable is a meta-property used to mark which
other properties can be perceived by the learner. can_fill_template_slot
indicates those nodes which can potentially be arguments of relations and
actions.

An ontology node derived from object may be associated with an object
structural scheme which provides a hierarchical representation of the internal
structure of a type object and guides how that object is perceived as a
collection of sub-objects and geons. A structural schema represents the
general pattern of the structure of an object, rather than the structure of
any particular object. For example a person’s body is made up of a head,
torso, left arm, right arm, left leg, and right leg. These sub-objects have
various relations to one another (e.g. the head is above and supported by the
torso).

Any ontology node derived from action may be associated with an action
description which guides how that action is perceived in terms of changes to
objects and their relations. An action description consists of:

  * •

A mapping of semantic roles to action description variables. All the relations
and conditions specified below will be in terms of these variables, which will
be bound to concrete objects when an action is instantiated in a particular
situation.

  * •

a collection of pre-conditions, which are relations which hold only in the
frame before the action happens

  * •

a collection of post-conditions, which are relations which hold only in the
frame after the action happens

  * •

a collection of enduring conditions, which are relations which hold before and
after the action happens.

  * •

a description of what happens during the action, consisting of

    * –

a mapping from action description variables to paths traversed by those
objects during the action

    * –

a set of relations which hold continuously during the action

    * –

a set of relations which hold at some point, but not necessarily continuously,
during the action.

  * •

properties required on objects involved in the action (e.g. the agent must be
animate

  * •

auxiliary variables, which do not occupy semantic roles but are still referred
to by conditions, paths, etc. An example would be the container for the liquid
which is an argument of a drink action.

##  Appendix B Situation Representation

A situation consists of

  * •

a set of objects, some subset of which may be marked as salient. These are the
ones which will be foregrounded in any linguistic descriptions of the
situation. For example, the ground is always present but rarely salient. Every
object in a situation possesses a type from the ontology and three axes; these
axes can be used to construct regions to describe the spatial relationships of
objects to one another in an abstract way.

  * •

a set of relations between objects in the situation which hold before and/or
after any actions occur. It is not necessary to state every relationship which
holds in a situation. Rather this should contain the salient relationships
which should be expressed in the linguistic description. It is also not
necessary to state relations which are implied by actions occurring in the
situation.

  * •

which objects in the situation are gazed at by the speaker.

  * •

a set of actions which occur in the situation. An action is an action
description from the ontology together with a mapping from the semantic roles
and auxiliary variables of the action to the objects in the situation.

  * •

syntax hints, which can constrain how the language generator expresses the
situation. A curriculum designer can, for example, use these to force actions
in a situations to always be described in the passive voice, if possible.

##  Appendix C Regions

Regions (which we derive almost entirely from (?, ?)’s account of the
semantics of prepositions) are used to describe the locations of objects
relative to one another in an abstract way. They may be used in action
descriptions, situations, perceptions, and situation templates.

A region consists of:

  * •

a reference object

  * •

a distance, one of interior, exterior_but_in_contact, proximal, and distal.

  * •

a direction, which is an object axis together with a positive or negative
polarity.

Regions can also be used to construct paths which describe how objects move. A
path (whose representation we again derived almost entirely from (?, ?)):

  * •

source and destination reference object or regions

  * •

an optional path operator, which must be one of via, to, toward, from, or
away_from

  * •

an optional reference axis

  * •

whether the orientation of an object changes as it moves along the path

##  Appendix D Situation Templates

A situation template has the same structure as a template, except all objects,
properties, relations, and actions may be replaced by variables. The
instantiations of these variable is controlled by constraints, the most common
being restrictions on which types from the ontology can be used.

Situation templates may be instantiated into concrete situations using either
a sampling or exhaustive enumeration strategy.

##  Appendix E Initial Language Generator Implementations

ADAM by default provides language generators for English and Chinese. These
implementations both work by translating the portions of situations marked as
salient into dependency trees. The learner has no access to these dependency
trees but only the resulting token sequence.

##  Appendix F Default Perceptual Representation

The world is represented to the learner as either one or two perception frames
(one for static situations; two for those containing actions, encoding the
state of the world before and after the action). A perception frame consists
of a collection of perception objects which have properties and have relations
with one another. Perception objects

  * •

may have sub-objects with which they have a sub-part relation.

  * •

have three axes, one of which is marked as primary (typically the longest).
These axes may have relations between each other (for example, to indicate
that an object is longer along one axis than another). Each axis has boolean
flags to indicate whether it is

    * –

curved

    * –

directed

    * –

aligned with gravity

  * •

a geon (with a few exceptions, such as objects which appear two-dimensional).
A geon has

    * –

three axes. Axes can have coarse-grained size relationships with each other
(e.g. for a pencil, its extent along one axis is much greater than the other
two, which are roughly the same).

    * –

a generating axis, which usually corresponds to its longest axis.

    * –

a cross-section data structure which specifies for the cross-section of the
object along its primary axis

      * *

whether it is curved

      * *

whether it has reflective symmetry

      * *

whether it has rotational symmetry

      * *

its size, which is one of

        * ·

constant if the cross-section is of roughly constant size along the generating
axis

        * ·

small-to-large if the cross-section gets bigger along the positive direction
of the generating axis

        * ·

large-to-small if the cross-section gets smaller along the positive direction
of the generating axis

        * ·

small-to-large-to-small if the cross section starts small, gets large in the
middle, and then shrinks (along the generating axis).

  * •

may have properties. The following properties can be perceived:

    * –

self-moving

    * –

animate

    * –

inanimate

    * –

two-dimensional

    * –

liquid

    * –

hollow

    * –

recognized-particular (is-dad, is-mom, is-baby, is-learner, is-ground)

    * –

gazed-at

    * –

Proto-roles (?, ?)

      * *

volitionally-involved

      * *

sentient-or-perceives

      * *

causes-change

      * *

moves

      * *

undergoes-change

      * *

incremental-theme (roughly speaking, this is the object involved in an action
whose part-whole state corresponds to the progress of the action itself, e.g.
_sandwich_ in _eat a sandwich_)

      * *

stationary

      * *

causally-affected

    * –

colors, expressed as an red-green-blue triples

  * •

may have a path (see A).

The following relations are perceivable

  * •

part-of

  * •

bigger-than, smaller-than, much-bigger-than, much-smaller-than

  * •

possession

  * •

in-region (which takes a region as an argument)

Two-frame perceptions of actions can also contain descriptions of what happens
during the action itself, consisting of:

  * •

a mapping from objects to paths (C) traversed by those objects during the
action

  * •

a set of relations which hold continuously during the action

  * •

a set of relations which hold at some point, but not necessarily continuously,
during the action.

Perceptions are generated from situations by combining the situation
representations with information from the ontology such as ontology node
properties, object structural schemata, and action descriptions.

##  Appendix G Learning Representations

ADAM provides representations and algorithms used by all the sample learning
algorithms implemented by ADAM (Appendix H). Although user-implemented
algorithms are not required to use them, they do make the process of writing a
learning algorithm much simpler.

###  G.1 Perception Graphs

Figure 11: A simple perception graph for the learner’s perception of a box
sitting on the ground.

For our learning algorithms, it is convenient to convert our learner’s
perceptual representation into a directed acyclic graph (a perception graph;
Figure 11). A node in a perception graph can represent:

  * •

an object perception (Appendix F)

  * •

geons (Appendix F)

  * •

an object property (Appendix F)

  * •

a spatial region (Appendix C)

  * •

an axis (Appendix C)

  * •

a path (Appendix C)

Note that some nodes, such as object perceptions and axes, have labels on them
for the convenience of developers when debugging (box_0, axis:side-to-side-0).
These are not accessible to the learner.

Edges between nodes represent relations from the inventory in Section 3.4
(e.g. partOf). Geons and paths are represented as multi-node sub-graphs, with
each aspect of their structure described in Appendix F getting its own node,
joined by special edge types. In dynamic situations, every edge in a
perception graph is labelled with a set of temporal scopes (either before,
after, or both) indicating at which frame(s) during the action the
relationship encoded by the edges holds true.

#### Perception Graph Patterns

ADAM’s default learner represents the “meaning” of an object, relation, or
action by perception graph patterns which can be matched against the
perception graphs for new situations. Like perception graphs, these are
directed acyclic graphs, but their nodes and edge are boolean functions
(predicates) which accept or reject matches against nodes and edges of
perception graphs, respectively (Figure 12).

Figure 12: An example of a perception graph pattern which would match any
perception graph that has an object perception node with properties hollow and
inanimate, such as that of a box or a cup.

The predicates can be complex; for example, we can require an edge have both a
certain type and a certain temporal scope. Patterns can also contain special
slot variable nodes; these are ‘wildcards’ corresponding to the arguments of
the property, relation, or action the pattern represents.

###  G.2 Perception Graph Algorithms

#### Perception Graph Pattern Matching

Matching a perceptual graph pattern against a perception graph becomes an
instance of a restricted form of the sub-graph isomorphism problem. Although
this problem is NP-complete in general, in practice it runs efficiently over
the sort of graphs encountered in ADAM. ADAM uses the implementation of the
VF2 sub-graph isomorphism algorithm (?, ?, ?) from the networkx library (?, ?)
with a few of custom optimizations.

ADAM also supports matching perception graphs patterns against one another
(e.g. to determine if one pattern is a generalization rather than another
pattern). This can also be accomplished by a slight variation on the same
algorithm by imposing a partial order on the node and edge predicates
according to the set of nodes and edges they can possibly match.

#### Perception Graph Pattern Generalization

ADAM learning algorithms encounter the need to generalize patterns in one of
two ways:

  * •

Given a pattern and perception graph the pattern fails to match, determine if
there is some generalization of the pattern which would successfully match the
graph.

  * •

Given two patterns, compute their intersection (the largest sub-pattern which
is implied by both input patterns).

Both of these can be approximated using this greedy match generalization
algorithm:

  * •

Attempt a regular match. If successful, stop.

  * •

If the match failed, use information gathered during the match process to
determine which pattern node blocked the expansion of the largest alignment
found between pattern nodes and graph nodes. ‘Relax’ this node either by
deleting it or (in a few cases) performing a node-specific relaxation (e.g. if
the node was a color predicate, we might expand the range of colors it is
willing to match).

  * •

When certain nodes are deleted, the deletion is propagated to other graph
nodes:

    * –

if an object is deleted, so are its sub-objects

    * –

if during relaxation a portion of the graph becomes (weakly-)disconnected and
contains no slot variables, remove it.

###  G.3 Surface Templates and Perception Graph Templates

A surface template is a sequence of tokens or argument slots, such as _ARG1
gives ARG2 to ARG3_ or _green ARG1_. The argument slots are referred to as
surface template variables. A surface template can be instantiated to produce
a token sequence by providing a binding of surface template variables to
tokens. Alternate representations with richer syntactic structure can easily
be introduced.

A perception graph template is a perception graph pattern together with an
alignment of its slot variable nodes to surface template variables. the
linguistic realization of learned objects, properties, relations, and actions
(including objects, which are degenerate argumentless templates).

#### Concepts

ADAM’s default implementation uses an extremely simplified semantic
representation consisting of a set of concepts, which are of four types:

  * •

object concepts, which have no argument slots

  * •

attribute concepts, which take one other concept as an argument

  * •

relation concepts, which take two other concepts as (numbered) arguments

  * •

action concepts, which take a variable number of other concepts as (numbered)
arguments

#### Alignment Data Structures

A language-concept alignment (LCA) is a mapping between concepts and their
corresponding token sequences. A perception-concept alignment (PCA) is a
mapping between concepts and sub-graphs in a perception graph. A language-
perception-concept alignment (LPCA) is pair of an LCA and a PCA over the same
set of concepts.

During training, the sample integrated learner implementation builds up an
LPCA. At inference time, it builds up a PCA and then translates it into
language.

##  Appendix H Sample Learners

###  H.1 Top-level Integrated learner

In the sample implementation, learning is coordinated at the top-level by an
integrated learner which contains sub-learners for objects, attributes,
relations, and actions, each of which can be customized to use different
learning algorithms. The integrated learner first initializes an empty LPCA
(G.3) to represent its understanding of the relationship between the
linguistic utterance and the perception graph. It then applies each sub-
learner in the order objects, then attributes, then relations, then actions.
Each sub-learner observes the linguistic utterances, the perception graph, and
the LPCA. After updating its internal state, each learner then has the
opportunity to update the LPCA before it is passed down the pipeline. For
example, if the object learner is confident it has learned the concept dog and
it recognizes one in the perception graph, it can align dog to the token _dog_
in the utterance and to the corresponding portion of the perception graph.

At inference time, the same process is applied, except that a PCA is used
instead of an LPCA. After all sub-learners have finished, the PCA is discarded
and the set of concepts is translated to language using the algorithm below,
which will be illustrated using the following concepts: { dad, ball,
throws(dad, ball), red(ball), shiny (ball ) }

  1. 1.

each object concept is translated to a set of token sequences as follows:

     * •

first, get the (argument-less) token sequence learned for the object concept
by the object sub-learner (e.g.ball to _ball_). If there is none, the object
concept is not translated. In the initial implementation, ADAM does not try to
learn English determiners and they are added by special logic.

     * •

second, get the set of surface templates associated with the attributes333This
should also be done for relations, but this has not yet been implemented. of
this object by the attribute sub-learner (if any). For example, {_red_ X,
_shiny_ X}.

     * •

return a set consisting of the result of recursively instantiating all subsets
(of size $<=3$) of the relation surface templates (using the object surface
template to bind the argument slot of the first attribute surface template).
For example, {_ball_ , _shiny ball_ , _red ball_ , _shiny red ball_}

  2. 2.

each relation concept mapped to a surface template by the relation sub-learner
is translated to a set of token sequences by instantiating the surface
template with its two arguments bound to each pair from the cross-product of
all instantiations of the argument object concepts (from step 1).

  3. 3.

each action concept mapped to a surface template by the action sub-learner is
translated to a set of token sequences by instantiating its the surface
template with its arguments bound to each tuple from the cross-product of all
instantiations of the argument object concepts (from step 1). For example,
_Dad throws the ball_ , _Dad throws the red ball_ , _Dad throws the shiny
ball_ , _Dad throws the shiny red ball_.

The scope of language covered by this process is limited and enhancing this is
a direction for future work.

###  H.2 Sub-Learners

All of our sample sub-learners share a common structure. First, all learners
except the object learner preprocess the perception graph to replace all sub-
graphs aligned to object concepts with single nodes annotated with those
concepts. Next, candidate surface templates are generated from the language-
concept alignment:

  * •

for objects, any unaligned token.

  * •

for attributes, any unaligned token before or after a token aligned to an
object concept forms a candidate surface template (e.g. if _red ball on the
table_ is the utterance and _ball_ is the only aligned token, then _red ARG1_
and _X on_ would be candidates).

  * •

for relations, any span of unaligned tokens for length at most 2 between two
aligned tokens aligned to object concepts is a candidate.

  * •

for verbs, ADAM uses a complex set of patterns to generate surface templates
based which account for different possible word order patterns in a language.

Finally, for each candidate surface template one or more perception hypotheses
is created for each candidate surface template:

  * •

for objects, any object perception subgraph not already aligned is a
candidate.

  * •

for attributes, only single property perception nodes attached to the
arguments are candidates.

  * •

for relations, the single initial hypothesis is the sub-graph consisting of
all shortest paths between the arguments together with any nodes one hop off
this path

  * •

for actions, the initial hypothesis is the entire graph.

If there was not an existing hypothesis for this surface template from
previously observed situations, these new hypotheses are stored for it.
Otherwise, this new hypothesis set is used to update the existing hypothesis
set in a way which depends on the particular learning algorithm; this can
cause the hypothesis set to become empty, in which case the learner concludes
the corresponding surface pattern candidate should be discarded (e.g. the
learner may eventually conclude that _red_ is not an action).

The following sample learning algorithms are provided in ADAM:

  * •

Subset. This learns the ‘meaning’ of a word to be those aspects of the
perception graph which are present every time it is used (inspired by (?, ?)).
It is provided as a simple baseline, but it will fail in the presence of
noise. ADAM’s sample implementation uses it for learning actions.

  * •

Pursuit, which implements the word learning model of (?, ?) into a variant we
call pursuit-na. (see appendix H.3) It learns well under noisy conditions, but
struggles with complex hypothesis spaces. ADAM’s sample implementation uses it
for object, attribute, and relation learning.

  * •

ADAM includes a less-tested implementation of Cross-Situational Learning (?,
?), a global learning model that uses distributional statistics across
learning instances to make hypotheses for word meanings.

  * •

Propose but Verify (?, ?), a local learning model that proposes and retains a
word meaning hypothesis after a single word-learning instance, and abandons
the hypothesis if the subsequent learning instances do not confirm it is also
provided. Similarly to the Cross-Situation Learning model, this is also less
tested.

###  H.3 Pursuit Non-Atomic

The Pursuit algorithm was designed to learn an alignment between words and
atomic meanings, as is typically the case in word learning experiments.
However, the grounded world as perceived by the learner in ADAM is not made up
of simple atomic objects. Rather objects form sub-graphs of a rich, complex
perceptual structure. This requires that the meaning representations assigned
to words must have a similarly rich and complex structure. We use ADAM
perception patterns (appendix G.1) for this representation.

Adapting Pursuit to use perception patterns as meaning representations
(resulting in a variant we call Pursuit-na for ‘non-atomic’) requires several
changes to the base algorithm. First, Pursuit-na needs to select a new
hypothesis from the intractably large space of possible perception sub-graphs
both in (1) when a new word is encountered (to choose the initial hypothesis)
and in (3) when rewarding a new random hypothesis because the leading
hypothesis is disconfirmed. Fortunately, ADAM’s perceptual representation
assumes the boundaries between objects (but not their identities) are known at
a pre-linguistic stage (?, ?). Our implementation of pursuit-na therefore uses
these object boundaries to define the hypothesis space whenever it needs to
make random choices.

Second, the perceptual representation of an object will contain both elements
essential to the meaning of the corresponding word and elements which are
accidental. For example, the shape of a ball is crucial to the meaning of the
word _ball_ , but its color is not; however, from the perspective of a child,
the color of _juice_ may be essential to how they use the word. Without a way
to generalize our hypotheses and distinguish the essential from the
accidental, pursuit-na will be unable to learn because its leading hypotheses
will consistently fail to match in situations outside those where they were
initially perceived. To address this, pursuit-na modifies Pursuit in two ways:

  * •

when attempting to confirm whether or not the current leading hypothesis
matches a new situation in (2), pursuit-na exploits ADAM’s ability to find
partial matches of patterns. If a perfect match is not found, pursuit-na still
disconfirms and penalizes the leading hypotheses. However, instead of
rewarding a random hypothesis in (3), the sub-graph of the leading hypothesis
which did successfully match the scene’s perception graph is rewarded, so long
as the number of nodes in the matched sub-pattern is of sufficient size
relative to the original pattern (this size ratio is the _partial match
parameter_). For example, if the learner believes being red is part of the
meaning of _ball_ and then observes the word _ball_ being used in a situation
with a green ball, it will reward the (possibly new) hypothesis which contains
the shape information but omits the color information.

  * •

Whenever any hypothesis is rewarded (in (2) or (3)), pursuit-na also rewards
any hypotheses which are generalizations of that hypothesis, where one pattern
is a generalization of another if its perception pattern graph representation
is a sub-graph of the other’s. This helps prevent the learner from learning
very slowly by continually jumping between overly specific hypotheses, with
more general hypotheses taking a very long time to become the leading
hypothesis, which is necessary for their scores to increase.

###  H.4 Specialized Learners

ADAM provides two specialized learners which are modules that augment the
normal sub-learners to provide additional learning capability. These
specialized learner’s operate on ADAM’s perceptual representation (see
Appendix F) either before or after the other sub-learners discussed in
Appendix H.2. These learners target linguistic structures which depend on
actions, relations, attributes, or objects to construct a representation of.

  * •

Plural Learner that learns templates for plurals (e.g many cats, two balls).
Although the plural learner module learns linguistic templates very similarly
to the attribute learner module that learn attributes such as colors, it runs
only when the perceived scene contains multiple objects that match the same
pattern. The module preprocesses the scene to mark these objects perceptually
with nodes indicating counts to be learned as count attributes.

  * •

Functional Object Learner that learns meanings of objects based on their
function (e.g. a person sits on a _chair. An independent model. unlike the
standard object learner, this module tracks the interactions between a
specific known object concept and how the object is used in an action concept.
Allowing the learner to make an assumption to what an unknown object
functioning in the same roll of an action might be. For example, if a chair in
the action _“A man sits on a chair”_ is replaced by a chair with only three
legs, or a stool which has no back the learner could still describe the action
as _“A man sits on a chair”_ even though the specific object is not
immediately recognized correctly.

##  Appendix I Experimentation and Evaluation Framework

ADAM provides a convenient framework for setting up and executing experiments.
The user specifies:

  * •

the language learner to use. This may optionally be initialized from a saved
learner state (e.g. to run experiments with actions with a learner which has
already learned the objects appearing in the actions).

  * •

one or more training stages. A training (or test) stage is a sequence of
$(situation,linguisticutterances,perceptualrepresentation)$ tuples. Typically
these are not provided directly; instead the user provides a collection of
situation templates, a template instantiation strategy (e.g. random sampling),
a language generator, and a perception generator.

  * •

zero or more test warm-up stages. These are observed by the learner without
evaluation before evaluating on the test set.

  * •

one or more test stages.

  * •

a collection of experiment observers. These observers can hook into different
points in the experiment process (before and after the observation of each
training example, after training is complete, after each test instance).

Experiment observers are provided to:

  * •

track how often the top-scoring linguistic description produce by the learner
on an instance matches the ‘gold’ utterance associated with the instance.

  * •

track how often the ‘gold’ utterance associated with an instance appears
anywhere in the learner’s candidate description list. This is typically more
useful to track since there are numerous valid and reasonable linguistic
utterances in any given situation.

  * •

write a detailed report of the learning process to a human-readable HTML file.
This report contains the situation, linguistic utterance, and perceptual
representation of every training and test instance, together with the
linguistic utterances produced by the learner.