doc/presentation/index.html

<!doctype html>
<html lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=1024" />
    <meta name="apple-mobile-web-app-capable" content="yes" />
    <title>babel</title>
    
    <meta name="description" content="A Clojure library for generation and parsing of natural language expressions." />
    <meta name="author" content="Eugene Koontz" />
    <meta name="thanks-to" content="http://impress.github.io/impress.js/ by @bartaz" />
    <link href="http://fonts.googleapis.com/css?family=Open+Sans:regular,semibold,italic,italicsemibold|PT+Sans:400,700,400italic,700italic|PT+Serif:400,700,400italic,700italic" rel="stylesheet" />

    <link href="css/impress-demo.css" rel="stylesheet" />
    <link href="css/dagre.css" rel="stylesheet" />
    
    <link rel="shortcut icon" href="favicon.png" />
    <link rel="apple-touch-icon" href="apple-touch-icon.png" />

    <link href="css/babel.css" rel="stylesheet" />
    <link href="css/graphs.css" rel="stylesheet" />

  </head>

<body class="impress-not-supported">

  <div id="prose-version" style="display:none">
    <p>
      Here are some random English expressions that babel can generate:

      her black bird's first shoe used to have Antonia
      you all would prepare yourselves
      the small pupil's professor's tall woman would move her

      babel.test.en> (repeatedly #(println (morph (generate))))
    </p>
    <p>
      How does it work?

      Definitions: 

      - phrase structure rule NP &rarr; Det N
      - lexeme (a.k.a. terminal symbol) pizza

      A _phrase structure rule_ consists of a parent and two
      children, whereas a _lexeme_ has no children. The two children of a
      phrase structure rule may be either lexemes or other phrase
      structure rules.

      Babel creates an expression by adding children to rules until
      there are no more empty places in the tree to add children.

      But how does babel know:

      - which rule to start with?
      - which chidren may be added at which location, to which
      parents?
      - how to prevent the procedure from running forever?

      The solution is that both rules and lexemes are maps whose
      values are defined such that they are only allowed them to be
      combined in certain ways.

    </p>
    <p>

      Example 1: category (:cat)

      Lexemes are declared to have a :cat value which can only be one
      of a small number of possibilities: {:noun, :verb, :preposition,
      ..}. These are called "parts of speech". The phrase structure
      rules are declared to only allow children with a certain value.
      For example, the rule: NP -> Det N, the first child must be:
      {:cat :determiner}, while the second child must be: {:cat
      :noun}.
    </p>
    <p>

      In addition, the parent of the rule, also has a :cat value,
      which is the same as one of the children. For example, in the
      rule: NP -> Det N, the :cat of the entire rule is the same as
      that of the second child. This allows rules to be added to other
      rules only in a certain way. For example, in the rule: S -> NP
      VP, the first child must be {:cat :noun}, and the NP in turn,
      will be formed such that its second child is also {:cat :noun}.

    </p>
    <p>

      We call the child that shares the same :cat value as its parent,
      the _head_ child ,and the other child, we call the _complement_.
      (generate) builds a tree by adding _head_ children first, and
      then complements. This is to allow generation by a given
      specification to be efficient.
      
    </p>
    
    <p>
      Example 2: subcategorization (:subcat)
    </p>
    <p>

      The other way that we constrain the generation process is with
      another specially-designated key called :subcat. This key allows
      children to specify what their complement sibling will
      be. (Human children are not so fortunate - imagine if, as an
      older sibling, you could choose a sibling to your preferences.)
    </p>
    <p>

      For example, in the rule NP -> Det N, the head noun chooses a
      determiner according to whether the N is singular, mass, etc:
    </p>
    <p>

      A cat.
      Some cats.
      Some dirt.
      
      * A cats.
      * A dirt.
    </p>
    <p>

      Example 3: semantics: composition of expressions

      The semantics of a parent is a map nested within the parent's
      map, in the :sem key. This key's value is shared with the the
      :sem key's value in the head child.

    </p>
    <p>
      Example 4: semantics: selection of arguments
      
      heads of phrases constrain what their complement sibling will be
      by semantics as well as (as we saw in example 2) by category.

    </p>
      
    <p>
      Generation via specification.

      Earlier we saw a demonstration of random generation, but Babel
      can also generate expressions which match a desired
      specification. A specification is written as a Clojure map, just
      as phrase structure rules and lexemes are, e.g. :sem = :cat.

      babel.test.en> (repeatedly #(println (morph (generate {:synsem {:sem {:pred :cat}
                                                                      :cat :noun}}))))
some stupid student's old cat
Luisa's first cat
some old mothers' first mothers' red cats
      
    </p>

    <p>
      The generative process chooses rules and children randomly, but,
      when it adds children, it requires that the resulting structure
      conforms to the given specification.

      (Show diagram showing rules and children are "belt fed" as children).
      
    </p>
    
    <p>
    Search is made more efficent because of the constraints that the
    head and parent of a phrase structure rule share semantics and
    category.
    </p>

    <p>
      Unification: why it's important. Unification allows us to
    express grammatical information in a concise "Don't Repeat
    Yourself" manner. We can have relatively few rule, because the
    most of the responsibility for determining how expressions are
    generated is borne by the lexicon.
    </p>

    <p>
      But: generation is still slow: we have to do a "sequential scan"
      of the potential children to find a child that actually matches
      our desired specification. 
    </p>

    <p>Optimization</p>

    - add indices to reduce set that we need to scan.
    - truncate trees after adding children to reduce cost of unification.

    <p>Upcoming 
      - more optimization
      - web-based development environment for grammars
      - ingest from from wikitionary, wikipedia, existing HPSG grammars
    </p>
  </div>
  
<!--
    For example this fallback message is only visible when there is `impress-not-supported` class on body.
-->
<div class="fallback-message">
    <p>Your browser <b>doesn't support the features required</b> by impress.js, so you are presented with a simplified version of this presentation.</p>
    <p>For the best experience please use the latest <b>Chrome</b>, <b>Safari</b> or <b>Firefox</b> browser.</p>
</div>

<div id="impress">

    <div class="step slide" data-x="-2000" data-y="-3000" data-scale="2">
      <h1>Babel</h1>

      <h2><a href="https://github.com/ekoontz/babel">
	  http://github.com/ekoontz/babel</a></h2>
      <div class="code">(defproject yourproject "0.1.0-SNAPSHOT"
  :description "Your project"
  :dependencies [[babel "2.3.2"]
                 [org.clojure/clojure "1.8.0"]])</div>

      
    </div>

    <div class="step slide" data-x="0" data-y="-3000" data-scale="2">
    <p>How to generate random English expressions</p>

    <div class="code">(use '[babel.english :only [generate morph]])
(repeatedly #(println (morph (generate))))</div>

    <div class="code" style="font-size:small">Matteo's new cat would pay you all
his second cats' small cities would return Antonia
Antonio's stupid mother wants to wear you
Gianluca and Giovanni's red parties will pay Gianluca
Antonia and Luisa's small coffees' red keys will endure Juan and me
Matteo's intelligent women would lift you
your small games' bread's second books would conserve it
your intelligent woman would assure it
the stupid mens' students' black chairs would listen to it
</div>
    </div>

    <div class="step slide" data-x="2000" data-y="-3000" data-scale="2">
      <h1>Generation: how?</h1>

      <ul>
	<li>phrase structure rules <pre>NP &rarr; article noun</pre></li>
	<li>lexemes (a.k.a. terminal symbols) <i>a,aardvark,..</i></li>
      </ul>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure1"><g/></svg>
      </div>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure2"><g/></svg>
      </div>
      
    </div>

    <div class="step slide" data-x="4000" data-y="-3000" data-scale="2">
      <h1>Rules can be added to rules</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure3" height="600"><g/></svg>
      </div>
      
    </div>
    
    <div class="step slide" data-x="6000" data-y="-3000" data-scale="2">
      <h1>Depth-first, head-first generation (0)</h1>

      <div class="svg" style="width:40%">
	<svg id="s_to_np_vp" height="600"><g/></svg>
      </div>

    </div>

    <div class="step slide" data-x="-2000" data-y="-1500" data-scale="2">
      <h1>Depth-first, head-first generation (1)</h1>

      <div class="svg" style="width:40%">
	<svg id="vp_is_head" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>S</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>VP</td>
	</tr>
	<tr>
	  <th>complement</th>
	  <td class='comp'>NP</td>
	</tr>
      </table>      
    </div>

    <div class="step slide" data-x="0" data-y="-1500" data-scale="2">
      <h1>Depth-first, head-first generation (2)</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure5" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>VP</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>sleeps</td>
	</tr>
      </table>
    </div>

    <div class="step slide" data-x="2000" data-y="-1500" data-scale="2">
      <h1>Depth-first, head-first generation (3)</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure6" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>NP</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>N'</td>
	</tr>
      </table>
    </div>

    <div class="step slide" data-x="4000" data-y="-1500" data-scale="2">
      <h1>Depth-first, head-first generation (4)</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure7" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>N'</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>cat</td>
	</tr>
	<tr>
	  <th>complement</th>
	  <td class='comp'>Adjective</td>
	</tr>
      </table>
    </div>

    <div class="step slide" data-x="6000" data-y="-1500" data-scale="2">
      <h1>Depth-first, head-first generation (5)</h1>

      <div class="svg" style="width:40%">
	<svg id="nbar_finished" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>N'</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>cat</td>
	</tr>
	<tr>
	  <th>complement</th>
	  <td class='comp'>black</td>
	</tr>
      </table>

    </div>

    <div class="step slide" data-x="-2000" data-y="0" data-scale="2">
      <h1>Depth-first, head-first generation (6)</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure8" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>NP</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>N'</td>
	</tr>
	<tr>
	  <th>complement</th>
	  <td class='comp'>Det</td>
	</tr>
      </table>

    </div>

    <div class="step slide" data-x="0" data-y="0" data-scale="2">
      <h1>Depth-first, head-first generation (7)</h1>

      <div class="svg" style="width:40%">
	<svg id="phrase_structure9" height="600"><g/></svg>
      </div>
      <table class="hc">
	<tr>
	  <th>parent</th>
	  <td class='parent'>NP</td>
	</tr>
	<tr>
	  <th>head</th>
	  <td class='head'>N'</td>
	</tr>
	<tr>
	  <th>complement</th>
	  <td class='comp'>a</td>
	</tr>
      </table>

    </div>

    <div class="step slide" data-x="2000" data-y="0" data-scale="2">
      <h1>Agreement</h1>

      <div class="examples">
	<img style="float:right" width="100px" src="Flag_of_England.svg" />
       <p>The cat sleeps</p>
       <p>The cats sleep</p>
       <p>*The cat sleep</p>
       <p>*The cats sleeps</p>
      </div>


      <div class="examples">
	<img style="float:right" width="100px" src="Flag_of_Italy.svg" />
	<p>Il gatto nero dorme</p>
	<p>I gatti neri dormano</p>
	<p>*Il gatti nero dorme</p>
	<p>*I gatti nero dormano</p>
	<p>*Il gatti neri dorme</p>
	<p>*I gatti neri dorme</p>
      </div>

    </div>

    <div class="step slide" data-x="4000" data-y="0" data-scale="2">
      <h1>Rule Explosion (1)</h1>

      <div class="examples">
       <p>The cat sleeps</p>
       <p>The cats sleep</p>
       <p>*The cat sleep</p>
       <p>*The cats sleeps</p>
       <p>*A cats sleep</p>
      </div>

      <div class="code">S &rarr; NP[singular] VP[singular]
S &rarr; NP[plural] VP[plural] 
NP[singular] &rarr; Det[singular] N[singular]
NP[singular] &rarr; Det[plural] N[plural]</div>
    </div>

    <div class="step slide" data-x="6000" data-y="0" data-scale="2">
      <h1>Rule Explosion (2)</h1>

      <div class="examples">
       <p>The black cat sleeps</p>
       <p>The black cats sleep</p>
       <p>*The black cat sleep</p>
       <p>*The black cats sleeps</p>
       <p>*A black cats sleep</p>
      </div>

      <div class="code">S &rarr; NP[singular] VP[singular]
S &rarr; NP[plural] VP[plural] 
NP[singular] &rarr; Det[singular] N[singular]
NP[singular] &rarr; Det[plural] N[plural]
N'[singular] &rarr; Adjective N[singular]
N'[plural] &rarr; Adjective N[plural]</div>
    </div>

    <div class="step slide" data-x="-2000" data-y="1500" data-scale="2">
      <h2>Instead: agreement via structure-sharing (1)</h2>

      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="instead1" width="600" height="600"><g/></svg>
      </div>
    </div>
    
    <div class="step slide" data-x="0" data-y="1500" data-scale="2">
      <h2>Instead: agreement via structure-sharing (2)</h2>
      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="instead2" width="600" height="600"><g/></svg>
      </div>
    </div>

    <div class="step slide" data-x="2000" data-y="1500" data-scale="2">
      <h1>Rules are graphs</h1>
      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="unification1" width="600" height="600"><g/></svg>
      </div>

      <div style="float:right;position:absolute;top:58%;font-size:75%" class='avm'>
        <table>
          <tr>
             <th>rule</th><td>Sentence</td>
          </tr>
          <tr>
            <th>comp</th>
	    <td>
	      <div class='avm'>
		<table>
		  <tr>
  		    <th>rule</th>
		    <td>noun phrase</td>
		  </tr>
		  <tr>
  		    <th>num</th>
		    <td><div class='ref'>1</div></td>
		  </tr>
		</table>
	      </div>
	    </td>
          </tr>
          <tr>
            <th>head</th>
	    <td>
	      <div class='avm'>
		<table>
		  <tr>
  		    <th>rule</th>
		    <td>verb phrase</td>
		  </tr>
		  <tr>
		    <th>num</th>
		    <td><div class='ref'>1</div></td>
		  </tr>
		</table>
	      </div>
	    </td>
          </tr>
        </table>
      </div> 
      
    </div>

    <div class="step slide" data-x="4000" data-y="1500" data-scale="2">
      <h1>Lexemes are also graphs</h1>

      <div style="float:left" class='avm'>
        <table>
          <tr>
             <th>orthography</th><td>"<i>sleeps</i>"</td>
          </tr>
          <tr>
            <th>num</th>
	    <td>singular</td>
	  </tr>
	</table>
      </div>
    </div>

    <div class="step slide" data-x="6000" data-y="1500" data-scale="2">
      <h1>Generation via unification</h1>

      <table class="func" style="font-size:50%">
	<tr>
	  <td class="func">(unify</td>
	  <td>
	    <div style="" class='avm'>
              <table>
		<tr>
		  <th>rule</th><td>Sentence</td>
		</tr>
		<tr>
		  <th>comp</th>
		  <td>
		    <div class='avm'>
		      <table>
			<tr>
  			  <th>rule</th>
			  <td>noun phrase</td>
			</tr>
			<tr>
  			  <th>num</th>
			  <td><div class='ref'>1</div></td>
			</tr>
		      </table>
		    </div>
		  </td>
		</tr>
		<tr>
		  <th>head</th>
		  <td>
		    <div class='avm'>
		      <table>
			<tr>
  			  <th>rule</th>
			  <td>verb phrase</td>
			</tr>
			<tr>
			  <th>num</th>
			  <td><div class='ref'>1</div></td>
			</tr>
		      </table>
		    </div>
		  </td>
		</tr>
              </table>
	    </div> 
	  </td>
	  <td>
	    <div style="float:left" class='avm'>
	      <table>
		<tr>
		  <th>head</th>
		  <td>
		    <div style="float:left" class='avm'>
		      <table>
			<tr>
			  <th>orthography</th><td>"<i>sleeps</i>"</td>
			</tr>
			<tr>
			  <th>num</th>
			  <td>singular</td>
			</tr>
		      </table>
		    </div>
		  </td>
		</tr>
	      </table>
	    </div>
	  </td>
	  <td class="func">)&rarr;</td>
	</tr>
	<tr>
	  <td colspan="2">
	    <div style="margin-left:25%;font-size:90%" class='avm'>
              <table>
		<tr>
		  <th>rule</th><td>Sentence</td>
		</tr>
		<tr>
		  <th>comp</th>
		  <td>
		    <div class='avm'>
		      <table>
			<tr>
  			  <th>rule</th>
			  <td>noun phrase</td>
			</tr>
			<tr>
  			  <th>num</th>
			  <td><div class='ref'>1</div></td>
			  <td>singular</td>
			</tr>
		      </table>
		    </div>
		  </td>
		</tr>
		<tr>
		  <th>head</th>
		  <td>
		    <div class='avm'>
		      <table>
			<tr>
  			  <th>rule</th>
			  <td>verb phrase</td>
			</tr>
			<tr>
			  <th>orthography</th><td>"<i>sleeps</i>"</td>
			</tr>
			<tr>
			  <th>num</th>
			  <td><div class='ref'>1</div></td>
			  <td>singular</td>
			</tr>
		      </table>
		    </div>
		  </td>
		</tr>
              </table>
	    </div> 
	  </td>
	</tr>
      </table>
	
    </div>

    <div class="step slide" data-x="-2000" data-y="3000" data-scale="2">
      <h1>Parent: apply(head,complement) (1)</h1>

      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="parents_apply_heads" width="600" height="600"><g/></svg>
      </div>

    </div>

    <div class="step slide" data-x="0" data-y="3000" data-scale="2">
      <h1>Parent: apply(head,complement) (2)</h1>

      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="parents_apply_heads_2" width="600" height="600"><g/></svg>
      </div>

    </div>
    
    <div class="step slide" data-x="2000" data-y="3000" data-scale="2">
      <h1>Parent's semantics = head's semantics</h1>

      <div style="float:left;width:69%;height:600px;width:600px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="parents_semantics" width="600" height="600"><g/></svg>
      </div>

    </div>

    <div class="step slide" data-x="4000" data-y="3000" data-scale="2">
      <h1>Lexeme: "sleeps"</h1>

      <div class='avm' style="font-size:75%">
	<table>
	  <tr>
	    <th>orthography</th><td>"<i>sleeps</i>"</td>
	  </tr>
	  <tr class="args">
	    <th>args</th>
	    <td>[</td>
	    <td>
	      <div class='avm'>
		<table>
		  <tr>
		    <th>number</th>
		    <td>singular</td>
		  </tr>
		  <tr>
		    <th>semantics</th>
		    <td><div class="ref">1</div></td>
		  </tr>
		</table>
	      </div>
	    </td>
	    <td>]</td>
	  </tr>
	  <tr>
	    <th>semantics</th>
	    <td colspan="3">
	      <table>
		<tr>
		  <th>predicate</th>
		  <td>sleeps</th>
		</tr>
		<tr>
		  <th>subject</th>
		  <td><div class="ref">1</div></td>
		  <td><table><tr><th>animate</th><td>true</td></tr></table></table>
		</tr>
	      </table>
	    </td>
	  </tr>
	</table>
      </div>

    </div>

    <div class="step slide" data-x="6000" data-y="3000" data-scale="2">
      <h1>Add "sleeps" to S &rarr; NP VP</h1>

      <div style="float:left;width:69%;height:600px;width:800px;position:absolute;left:1%;top:15%;font-size:100%">
	<svg id="add_sleeps" width="800" height="600"><g/></svg>
      </div>

    </div>
    
    <div id="overview" class="step" data-x="2000" data-y="0" data-scale="10">
      <!-- zoom out to show all slides -->
      
    </div>

</div>

<div class="hint">
    <p>Use a spacebar or arrow keys to navigate</p>
</div>
<script>
if ("ontouchstart" in document.documentElement) { 
    document.querySelector(".hint").innerHTML = "<p>Tap on the left or right to navigate</p>";
}
</script>
<script src="js/impress.js"></script>
<script>impress().init();</script>

<script src="js/d3.v3.min.js"></script>       
<script src="js/dagre-d3.min.js"></script>
<script src="js/graphlib-dot.js"></script>
<script src="js/graphs.js"></script>
<script src="js/draw.js"></script>

</body>
</html>