[ANOUNCE] A Viterbi Decoder for Link-Grammar

[Linas Vepstas]

I'd like to announce some recent progress on a Viterbi decoder for link-grammar, including explaining why it's being done.  I'm proud to announce that it can now parse short sentences correctly, albeit very slowly.

The goal of providing this decoder is to present a flexible, powerful interface for implementing high-level semantic algorithms on top of the the low-level link-grammar syntactic parser, and, in particular, for steering the parse based on high-level semantic knowledge.  This allows the parser to move beyond being merely a syntactic parser, and to become fully integrated with general semantic artificial intelligence.

A less abstract list of expected benefits include:

 * Incremental parsing: the ability to obtain partial results after providing partial senences, a word at a time.

 * Less sensitivity to sentence boundaries, allowing longer, run-on sentences to be parsed far more quickly.

 * Mitigation of the combinatorial explosion of parses.

 * Allow gramatically broken/incorrect chat dialog to be parsed;  in general, to do better with slang, hip-speak.

 * Enable co-reference resolution and anaphora resolution across  sentences (resolve pronouns, etc.)

 * Allow richer state to be passed up to higher layers: specifically, alternate parses for fractions of a sentence, alternative reference  resolutions.

 * Allow a plug-in architecture, so that plugins, employing higher-level semantic (AGI) algorithms can provide parse guidance and parse disambiguation.

 * Eliminate many of the hard-coded array sizes in the code.

 

The data structures used to implement this resemble those of the OpenCog AtomSpace.  All data classes inherit from a class called Atom (which is an atomic predicate, in the sense of mathematical logic). Atoms further subdivide into Links and Nodes, thus all data is represented in the form of a "term algebra" (aka the "Free Theory", in the sense of model theory).  This structure allows all data to be represented as (hyper-)graphs, which in turn makes the implementation of graph algorithms easier to implement.  All these theoretical considerations provide a natural setting for storing Vitebrbi state information.  Put differently, this provide a generic, uniform way of holding the various partly-finished parses, and effecting state transformations on them.  

Making the internal state directly visible allows low-level syntactic algorithms, as well as high-level, semantic algorithms to control parsing. In other words, the intended use of the Viterbi decoder is to provide a framework for parsing that should make it possible to integrate tightly (and cleanly) with high-level semantic analysis algorithms. Thus, reference and anaphora resolution can be done using the same graph structure as used for parsing; it should also allow graphical

transformations, such as those currently implemented in RelEx. Annotation with word-sense data, entity markers and the like all become possible and uniform using the same infrastructure.

One may argue that Viterbi is a more natural, biological way of working with sequences.  Some experimental, psychological support for this can be found here:

http://www.sciencedaily.com/releases/2012/09/120925143555.htm per Morten Christiansen, Cornell professor of psychology.

Currently, the parser can correctly parse many short sentences.  It currently runs very slowly, as no pruning algorithms have yet been implemented.

To use this parser, you must run configure with the --enable-viterbi flag:

   configure --enable-viterbi

Then, in the client, switch to the viterbi parser with the ! command !viterbi  (If confused, try !help and !var for general help).

The vitest.cc file contains unit tests. Currently, it consists of 49 tests, and all of them pass.  More tests will be added.

The most recent changes are not in the 4.7.10 tarball; if you want the latest, working code, you need to get it from SVN.  Anyway, some sample structures below.

-- Linas

Parse for "this is a test" .   The normal parser for this looks like this:

         +--Ost--+

   +-Ss*b+  +-Ds-+

   |     |  |    |

this.p is.v a test.n 

or, with wall words:

    +---------------RW--------------+

    |              +--Ost--+        |

    +---Wd---+-Ss*b+  +-Ds-+        |

    |        |     |  |    |        |

LEFT-WALL this.p is.v a test.n RIGHT-WALL 

The output of viterbi is this:

SEQ :                  # a sequence, an ordered set

  LING :               # a link-grammar link; naming conflict with opencog link.

    LING_TYPE : Wd     # the type of the link connecting two words.

    WORD_DISJ :        # holds the word and the connector used

      WORD : LEFT-WALL # all sentences begin with the left-wall.

      CONNECTOR : Wd+  # + means "connect to the right". - means left

    WORD_DISJ :

      WORD : this.p    # word with suffix as it appear in link-grammar dictionary

      CONNECTOR : Wd-

  LING :

    LING_TYPE : Ss*b   # and so on ... 

    WORD_DISJ :

      WORD : this.p

      CONNECTOR : Ss*b+

    WORD_DISJ :

      WORD : is.v

      CONNECTOR : Ss-

  LING :

    LING_TYPE : Ds

    WORD_DISJ :

      WORD : a

      CONNECTOR : Ds+

    WORD_DISJ :

      WORD : test.n

      CONNECTOR : Ds-

  LING :

    LING_TYPE : Ost

    WORD_DISJ :

      WORD : is.v

      CONNECTOR : O*t+

    WORD_DISJ :

      WORD : test.n

      CONNECTOR : Os-

[Ben Goertzel]

Linas,

Wow, it's great to see this working; you've been talking about it for a while ;)

I wonder if you could post a description of the algorithm you're using
somewhere -- say on the OpenCog wiki, or a blog post, etc.? I
basically understand it, but I doubt many others do...

I think the approach has huge potential. I wonder what are your
initial ideas about pruning. Do you intend to do pruning based on the
results of unsupervised corpus analysis? It's kinda cheating, but I
wonder if you could initially do pruning based on the analysis of
frequent patterns in a corpus of sentences parsed by the regular link
parser?

thx
Ben

> --
> You received this message because you are subscribed to the Google Groups
> "link-grammar" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to link-grammar...@googlegroups.com.
> To post to this group, send email to link-g...@googlegroups.com.
> Visit this group at http://groups.google.com/group/link-grammar?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>



--
Ben Goertzel, PhD
http://goertzel.org

"My humanity is a constant self-overcoming" -- Friedrich Nietzsche

[Robert Oschler]

Hello Linas,

Great work! Is this the default parsing algorithm, or can you switch
between the Viterbi algorithm and the original algorithm with a
setting?

Thanks,
Robert

Thanks,
Robert Oschler
Twitter -> http://twitter.com/roschler
http://www.RobotsRule.com/
http://www.Robodance.com/

[Ben Goertzel]

As his email says

***

To use this parser, you must run configure with the --enable-viterbi flag:

configure --enable-viterbi

Then, in the client, switch to the viterbi parser with the ! command
!viterbi (If confused, try !help and !var for general help).

***

[Robert Oschler]

Thanks Ben.

Robert

[Linas Vepstas]

On 20 March 2013 01:45, Robert Oschler <robert....@gmail.com> wrote:

Hello Linas,

Great work!  Is this the default parsing algorithm, or can you switch
between the Viterbi algorithm and the original algorithm with a
setting?

It's not the default -- it is not complete, not ready, too slow, and still contains known 'bugs'.  

FYI, it is the third, not the second, algo implemented, the second being the SAT solver.  It is enabled the way all the other optional add-ons are enabled: with a configure-time flag before compiling, and a run-time command.  Cut-n-paste below.

Linas.

partial output of ./configure --help showing things that can be turned on and off :

  --enable-pthreads          compile with pthread support

  --disable-java-bindings    disable build of java bindings

  --enable-sat-solver        enable use of the Boolean SAT parser

  --enable-viterbi        enable use of the Viterbi parser

  --enable-corpus-stats      use corpus statistics

  --disable-aspell        Build without ASpell support (default is enabled)

  --disable-hunspell      Build without HunSpell support (default is enabled)

  --disable-editline      disable use of editline

Run-time variables; use !help and !var for more info:

linkparser> !help

Special commands always begin with "!".  Command and variable names

can be abbreviated.  Here is a list of the commands:

 !variables      List user-settable variables and their functions    

 !help           List the commands and what they do                  

 !file           Read input from the specified filename              

 !!<string>      Print all the dictionary words matching <string>.

                 Also print the number of disjuncts of each.

 !<var>          Toggle the specified boolean variable.

 !<var>=<val>    Assign that value to that variable.

linkparser> !var

 Variable     Controls                                      Value

 --------     --------                                      -----

 bad          Display of bad linkages                           0 (Off)

 batch        Batch mode                                        0 (Off)

 cluster      Use clusters to loosen parsing                    0 (Off)

 constituents Generate constituent output                       0

 cost-model   Cost model used for ranking                       1

 cost-max     Largest cost to be considered                  2.00

 disjuncts    Display of disjuncts used                         0 (Off)

 echo         Echoing of input sentence                         0 (Off)

 graphics     Graphical display of linkage                      1 (On)

 islands-ok   Use of null-linked islands                        0 (Off)

 limit        The maximum linkages processed                 1000

 links        Display of complete link data                     0 (Off)

 max-length   Maximum sentence length                         170

 memory       Max memory allowed                               -1

 null         Allow null links                                  1 (On)

 null-block   Size of blocks with null count 1                  1

 panic        Use of "panic mode"                               1 (On)

 postscript   Generate postscript output                        0 (Off)

 senses       Display of word senses                            0 (Off)

 short        Max length of short links                        10

 spell        Use spell-guesser for unknown words               1 (On)

 timeout      Abort parsing after this many seconds            30

 union        Display of 'union' linkage                        0 (Off)

 use-fat      Use fat links when parsing                        0 (Off)

 verbosity    Level of detail in output                         1

 vit          Use Viterbit-based parser                         1 (On)

 walls        Display wall words                                0 (Off)

 width        The width of the display                         89

Toggle a boolean variable as in "!batch"; set a variable as in "!width=100".

linkparser> 

[Linas Vepstas]

On 20 March 2013 01:43, Ben Goertzel <b...@goertzel.org> wrote:

Linas,

Wow, it's great to see this working; you've been talking about it for a while ;)

For a suitable definition of 'working'...

I wonder if you could post a description of the algorithm you're using

In a few sentences:

In link-grammar, a "disjunct" can be thought of as a puzzle piece with a word printed on it.  There are many different puzzle pieces with the same word on it. As each word comes in, one tries to find a piece that fits.  Sometimes, more than one fits, so one has multiple 'alternatives'.  The algo keeps a set of these alternatives (of assembled pieces), and, as words come in, alternatives are either discarded (because nothing fits) or are elaborated on. This last sentence is why I'm calling it 'viterbi'.

I don't want to elaborate further at this point because the above is not strong enough to reproduce the old behaviour: it can create islands; it ignores post-processing.  The original algorithm uses integer-valued "cost" to rank parses; I want to replace this by floating point values.

I also want to implement an "algorithm plug-in" API -- basically, a way of saying "here's the state I currently have, do you want to modify it?" ('mind-agents' if you wish)  The above puzzle-piece algo would be the first to run, but clearly, I need more to prevent islands, or to re-order states by probability/liklihood.  Whether I can do this as distinct plugins, or whether they'll need to be integrated into a big ball-o-complexity is unclear.  If you recall, RelEx had a list of algos there were applied in sequential order: first, some POS tagging, then some head-word verb extraction, then some entity extraction, etc.  This demonstrates that algorithms can be layered. 

The core issue I'm hoping to solve here is that of having a uniform development environment:  link-grammar is in C, has no probability (besides cost), and no internal API.  RelEx is in java, is explicitly graphical, but is not a hypergraph, has no probabilities, and can't provide feed-back to control link-grammar.  Relex output was pumped into opencog, which is C++, which could not feedback into relex or link-grammar.

So, at the moment, there aren't really any new or novel algorithms:  I've day-dreamed some in the past, but have been stymied because of the above fractured approach: the boundaries between components were too difficult to cross.

-- Linas

[Murilo Saraiva de Queiroz]

Kudos, Linas! This is extremely interesting stuff. 

It seems to be quite easy to convert the viterbi output you pasted into a graphviz script so we can generate images of the graphs, as I did a long time ago (and in a very hacky way...) for RelEx output... It could be useful in the documentation (or in a web-interface to the parser) and is a nice introductory/trivial project for getting used with link-grammar. 

muriloq

 

--
You received this message because you are subscribed to the Google Groups "link-grammar" group.
To unsubscribe from this group and stop receiving emails from it, send an email to link-grammar...@googlegroups.com.
To post to this group, send email to link-g...@googlegroups.com.
Visit this group at http://groups.google.com/group/link-grammar?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Murilo Saraiva de Queiroz, MSc

Hardware Engineer at NVIDIA

[Linas Vepstas]

Cross-post of ongoing conversations.

---------- Forwarded message ----------
From: Linas Vepstas <linasv...@gmail.com>
Date: 20 March 2013 20:39
Subject: Re: [opencog-dev] Re: [Link Grammar] [ANOUNCE] A Viterbi Decoder for Link-Grammar
To: ope...@googlegroups.com

On 20 March 2013 17:30, Matt Mahoney <mattma...@gmail.com> wrote:

Also, do you have any test results or benchmarks?

There is a unit test.  I expect the new parser, when completed, to produce more or less exactly the same results as the old one.  Parse results are determined by the dictionary, and not by the parse algorithm.  The parser algorithm knows nothing about English -- it obtains all language knowledge from the dictionary. There are dictionaries for English, Arabic, Persian, German, French and Russian. 

  

Such as comparing
error rates for the new parser vs. the old one on some data set? What
test set and evaluation method are we using?

The English dictionaries come with five test files, 4.0.batch, 4.0.biolg.batch, 4.0.enwiki.batch, 4.0.voa.batch and 4.0.fixes.batch, containing more than 5000 test sentences.  I monitor the test results on a regular basis.

I don't know how testing is done for the other languages, I do not maintain those.  

 

What does the new parser output for the following sentences?

When it is completed, it will output the same as the old parser.

 

If it correctly incorporates semantics into the parse in order to
attach the prepositional phrase, then where does that information come
from? Is it coded by hand into the language model? Is it learned? If
so, from what data set?

The English dictionary is manually curated, but contains rules there were learned by various semi-automated means, as published in various papers.  I've expanded the dictionary as well, using results obtained from voice of america, project gutenberg and wikipedia, using the opencog infrastructure to get these.  This included identifying syntactically similar words, tagging with word senses, and enhancing parse ranking with floating-point probabilities.

The French dictionary was automatically constructed from the french wikitionary. It didn't work very well when I last tried it.  I don't think its being updated.

The Russian dictionary was partially constructed/learned from some stemming engines. I don't know the details.  No clue how the Arabic or Persian dicts were built.  I suspect the German dict was hand-built, its small.

--------------------------

Your questions indicate that you're partly missing the point of this work, which is to extend the parsing infrastructure in a way that is extensible and modular.  All data, starting with the dictionary, the intermediate representations, to the parse results, are represented as opencog hypergraphs.  Parsing itself is accomplished by applying a sequence of (small) algorithms to progressively modify and decorate the graph.  I'm trying to think of these algorithms themselves as a set of re-write rules (so that I'm  doing graph re-writing) and plan to express the re-write rules as opencog graphs themselves, so that e.g. the pattern matcher finds a matching pattern and applies a transformative rule to modify the parse graph in some way.   This is how RelEx works today.  The problem with relex is that 1) its in Java,  2) the graphs are edge-labelled graphs, not opencog hypergraphs, 3) it doesn't use any probabilities or truth values while applying transformations.

By moving everything to atoms, endowed with probabilities/truth values, and performing parsing by applying a sequence of graph rewriting rules, I hope to open up the guts to tinkering as well as better integration with other cognitive parts.  Having a uniform infrastructure should make learning easier too, as opposed to the ad-hoc, semi-automated, manually curated learning results of the past.  The current link grammer stores the dictionaries in flat files.  Easy to hand-edit, but horrid for learning algos.

--linas

[Linas Vepstas]

On 20 March 2013 20:44, Ben Goertzel <b...@goertzel.org> wrote:

I meant to refer to learning statistical information for semantic
guidance of parsing from unsupervised corpus analysis, 

What inspired me to embark on this was a vague daydream to somehow start with a blank slate -- an empty dictionary, an empty set of algorithms (let me use 'algorithm' as a synonym for 'graph re-write rule', if I may).  Then, somehow, I'm not sure how, by observing the environment, patterns are discerned, causing words to be added to the dictionary, and re-write rules to be added to the list of algorithms. 

In order to realize this dream, the core infrastructure has to be flexible.  The opencog atomspace seems suitable: it offers a superset of concepts commonly found in predicate logic, first-order logic, model theory, lambda calculus, type theory, universal algebra, term algebra, term rewriting but also offering sufficient floating-point support to implement algorithms from Bayesian probability, Markov nets, and artificial neural-nets.   So its a kind-of theory-agnostic petri dish for expressing evidential knowledge.

Because of this generic representational infrastructure, the 'graph rewrite rules' that might be learned are not limited to a linguistic domain.  A sequence of graph re-write rules might result in a hypergraph that expresses the idea "if a stranger says 'bad dog' then bite him in the leg"  The motor-control parts of the avatar might then observe the 'bite man in leg' part, and proceed accordingly.

Anyway, I can't begin these experiments without first having the infrastructure to perform them in.  On the other hand, building out the lab is a lot like procrastinating on the real science, and sometimes I worry that I'm just procrastinating.  

-- Linas