Link Grammar's influence on AtomSpace design

[Linas Vepstas]

Not everyone is aware that Link Grammar's underlying theory is far more broad than simply describing natural language. It would seem that the theory generalizes to one of describing graphs, in general (and knowledge graphs, in particular).

I just updated the wiki page https://wiki.opencog.org/w/Link_Grammar to give a brief sketch of how this theory generalizes, and how it influences the AtomSpace design.  The generalization is reviewed in https://wiki.opencog.org/w/Connectors_and_Sections

If you've heard these ideas before, then this page "doesn't say anything new"; it just reminds you of the names of the Atoms that implement the various concepts, such as connectors and disjuncts (connector sequences). It also points to the half-dozen PDF's that justify and articulate this generalization.

If you haven't heard of these ideas before... well, enjoy! Just be aware that the ideas are deceptively simple. You might read this stuff and nod to yourself "yes, of course, obvious" until you get to something like the https://wiki.opencog.org/w/CrossSection and wonder "what the heck?" The apparent simplicity of these concepts makes them sometimes hard to understand.

-- Linas

[Ivan V.]

Really interesting.

I'm approaching a similar problem from the similar side. I start with a parsing algorithm, and extend it to support left side conjunctions and right side disjunctions. This extension makes the rules equivalent to normalized sequents known from sequent calculus. The result is very interesting: any logical formula can be converted to these normalized sequents suitable for (enhanced) parsing. All rules then become:

A1 /\ A2 /\ A3 /\ ... -> B1 \/ B2 \/ B3 \/ ...

The parsing process then becomes equivalent to the logical abduction process. We start from the `Goal` atom and chain rules backwards to verify if the input string matches the rules.

I like to think that this system resembles a kind of URE on steroids.

--
You received this message because you are subscribed to the Google Groups "opencog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opencog+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAHrUA378PEv7%3Dm4A2yte-1icmL32JYrd-EndgE%2BuHGZvzAgc%3Dg%40mail.gmail.com.

[Linas Vepstas]

Hi Ivan,

On Fri, Apr 2, 2021 at 3:00 AM Ivan V. <ivan....@gmail.com> wrote:

I'm approaching a similar problem from the similar side. I start with a parsing algorithm, and extend it to support left side conjunctions and right side disjunctions.

I don't understand what you are saying here. What does it mean to extend a parser in this way? What do you mean by conjunctions and disjunctions?

The conventional definition of a parser is a device that acts on a string of symbols, that, when it's done, indicates how that string can be decomposed into parts.

The conventional definition of conjuncts and disjuncts are strings of symbols combined with and/or operators.

How are you modifying these conventional definitions to obtain what you are doing?

-- Linas

To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAB5%3Dj6W5VnC-2A_k%3D3Vc2rV29%3DKuKLhddQzBXgpXsxc%3Dm%2BbuWw%40mail.gmail.com.

--

Patrick: Are they laughing at us?

Sponge Bob: No, Patrick, they are laughing next to us.

 

[Ivan V.]

Hi Linas, thanks for the response :)

I'll try to explain myself and provide a link to a project supporting my reasoning. If I'm not mistaken, you are talking about *link grammar* rules capable of doing inference process. The similar thing I'm trying to articulate is an extension to more popular grammar production rules which renders them deductively complete. The result stands for URE equivalent capable of reasoning about flexible syntax expressions (may be non-strict syntax form of Atomspace). Basically, it is a fusion between term rewriting rules and classical logic.

Usual parsers take productions of the form `A -> B` (I write this backwards to align it with logic, as explained in correspondence between production rules and logical implication section).

Within the extension I propose, having a kind of a production:

A1 /\ A2 -> B

reads as follows - when checking for `B`, we derive *both* `A1` *and* `A2` to be parsed in the same input string fragment at the appropriate place.

Similarly,

A -> B1 \/ B2

means that if *either* `B1` *or* `B2` is priorly derived, then derive `A` to parse in input string fragment at appropriate place.

This extension to the parsing is a matter of expecting ambiguous expressions, and it comes handy when parsing logical expressions during proof construction. I imagined the whole inference mechanism around these extensions. I named it "expression logic", and it represents all of the following: expression recognizer and generator, SMT solver, deductive system, term rewriting framework, and metatheory language formalization. In less words, it is a problem solver. Implementation is still a work in process, but I believe that background theory won't change too much. I'm trying to keep the size of the whole implementation below 300 javascript LOC.

Putting once more the background theory on trial, I wonder if the planned logic operators can be described only using basic term rewriting rules (only rules of the form `A -> B`) while retaining deductive completeness. Supported logic operators would still have the same significance to the theory behind, only that they would be implemented as a library, a level above the bare metal term rewriting algorithm.

I hope I managed to be more understandable this time.

Thanks again for the response,

- ivan -

To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAHrUA36Sm5O_SYqYJ-WxqLSNcq%3DD6aoRm8rZ4UPVVFU2Nq%3DqGg%40mail.gmail.com.

[Linas Vepstas]

On Fri, Apr 2, 2021 at 1:38 PM Ivan V. <ivan....@gmail.com> wrote:

Hi Linas, thanks for the response :)

I'll try to explain myself and provide a link to a project supporting my reasoning. If I'm not mistaken, you are talking about *link grammar* rules capable of doing inference process.

Link grammar does not have "rules" or "production rules". It is not a production grammar in the 1960's sense of a Chomsky context-free (or context-sensitive) grammar. In terms of linguistics, it is not a head-driven phrase-structure grammar (HPSG). It is a dependency grammar, with bi-directional dependencies.  Thus, concepts like "inference" or "deduction" do not apply to link grammar or it's generalizations.  There is a left-over fragment of "chaining" but that fragment is indistinguishable from parsing. The form of parsing that it does is "assembly". In terms of code, that means that the URE is incompatible with link-grammar: there are no rules.

One reason I'm excited by link-grammar is that it gets rid of ideas like deduction and inference and chaining, and replaces them by assembly. This is exciting because... well, look at the vast amounts of effort put into PLN and URE. They're problematic, they've always been problematic because of the difficulty of composing rules, and the difficulty of the notation of "input" and "output" when using lambda-calculus style notation, or Hilbert-style natural deduction, or sequent calculus, or Bayesian inference.

Worse, the "rules" are hand-curated, human-crafted carefully-engineered artifacts. I have not seen any coherent, complete proposal by which these rules could be learned by a learning system. I think those proposals are absent because trying to think of ways to learn rules and production systems is complicated.

Link-grammar nukes these concepts, replaces them with the idea of assembling parts, and nukes the lambda-calculus notation in favor of a more generic, more general connector notation. Its a more powerful, more fundamental technique.  Things like lambda calc and sequent calc and production rules (and rules in general) are narrow special cases. Things like beta reduction and term re-writing and deduction and inference and reasoning are special cases.

I'll mention the nature of the solution below: link-grammar gets rid of arrows, and replaces them by bi-directional links. One no longer writes A -> B to mean "A implies B" or "A produces B" or "a function that takes A as input and returns output values of type B".  Or rather, one is no longer forced to write A->B. One still can, and in certain problem domains, it's handy. It's just that now, one is liberated from a forced sequential flow. There's no forward-chaining, backward-chaining; the constraint satisfaction problem is symmetric with respect to that arrow.

Getting rid of that arrow is what nukes deduction and induction (and replaces them by the more general act of assembling)

The similar thing I'm trying to articulate is an extension to more popular grammar production rules which renders them deductively complete. The result stands for URE equivalent capable of reasoning about flexible syntax expressions (may be non-strict syntax form of Atomspace). Basically, it is a fusion between term rewriting rules and classical logic.

Usual parsers take productions of the form `A -> B` (I write this backwards to align it with logic, as explained in correspondence between production rules and logical implication section).

The direction of this arrow is the tip of the ice-berg that led me to understand link-grammar (and to propose it as a replacement for productions and rules). What link-grammar says is "you don't need to assign a directionality to this arrow", and more strongly: "assigning a direction to this arrow leads to pathological cases in reasoning, theorem proving, natural deduction, etc." 

Within the extension I propose, having a kind of a production:

A1 /\ A2 -> B

reads as follows - when checking for `B`, we derive *both* `A1` *and* `A2` to be parsed in the same input string fragment at the appropriate place.

Similarly,

A -> B1 \/ B2

means that if *either* `B1` *or* `B2` is priorly derived, then derive `A` to parse in input string fragment at appropriate place.

A worked example here would aid in understanding.  I almost get what you are saying, but not quite.

This extension to the parsing is a matter of expecting ambiguous expressions, and it comes handy when parsing logical expressions during proof construction. I imagined the whole inference mechanism around these extensions. I named it "expression logic", and it represents all of the following: expression recognizer and generator, SMT solver, deductive system, term rewriting framework, and metatheory language formalization. In less words, it is a problem solver. Implementation is still a work in process, but I believe that background theory won't change too much.

OK.

I'm trying to keep the size of the whole implementation below 300 javascript LOC.

!

Putting once more the background theory on trial, I wonder if the planned logic operators can be described only using basic term rewriting rules (only rules of the form `A -> B`) while retaining deductive completeness. Supported logic operators would still have the same significance to the theory behind, only that they would be implemented as a library, a level above the bare metal term rewriting algorithm.

I hope I managed to be more understandable this time.

Examples, please!

To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAB5%3Dj6VTy259EpZ55CqeH8u7QhM3x8U3DXOG7VEQf2uymBCyVg%40mail.gmail.com.

[Ivan V.]

Examples, please!

Well, the following ruleset should be a solution to entscheidungsproblem for propositional logic, written in expression logic:

    (
        "true" -> Goal
    ) <- (
        (
            (
                // semantics
                (
                    (   <a> "↔" <b> <-> (<a> <-> <b>)  ) /\
                    (   <a> "→" <b> <-> (<a> -> <b>)   ) /\
                    (   <a> "∧" <b> <-> (<a> /\ <b>)   ) /\
                    (   <a> "∨" <b> <-> (<a> \/ <b>)   ) /\
                    (       "¬" <a> <-> ~ <a>          )
                ) <- (
                    (<a> <-> logic) /\
                    (<b> <-> logic)
                )
            ) /\ (
                // constants
                (
                    (         ~ "true" <-> "false" ) /\
                    (        ~ "false" <-> "true"  ) /\
                   
                    (   (<a> /\ ~ <a>) <-> "false" ) /\
                    (  (<a> /\ "true") <-> <a>     ) /\
                    ( (<a> /\ "false") <-> "false" ) /\
                   
                    (   (<a> \/ ~ <a>) <-> "true"  ) /\
                    (  (<a> \/ "true") <-> "true"  ) /\
                    ( (<a> \/ "false") <-> <a>     )
                ) <- (
                    (<a> <-> logic)
                )
            ) /\ (
                // axioms
                (
                    ( <a> -> (<b> -> <a>)                                     ) /\
                    ( (<a> -> (<b> -> <c>)) -> ((<a> -> <b>) -> (<a> -> <c>)) ) /\
                    ( (~ <a> -> ~ <b>) -> (<b> -> <a>)                        )
                ) <- (
                    (<a> <-> logic) /\
                    (<b> <-> logic) /\
                    (<c> <-> logic)
                )
            )
        ) <- (
            // syntax
            (                       eq -> logic   ) /\
            (              impl "↔" eq -> eq      ) /\
            (                     impl -> eq      ) /\
            (             and "→" impl -> impl    ) /\
            (                      and -> impl    ) /\
            (               and "∧" or -> and     ) /\
            (                       or -> and     ) /\
            (               or "∨" not -> or      ) /\
            (                      not -> or      ) /\
            (              "¬" primary -> not     ) /\
            (               "(" eq ")" -> primary ) /\
            (                     atom -> primary ) /\
            ( /[_A-Za-z][_0-9A-Za-z]*/ -> atom    )
        )
    )

We convert the entire formula to sequents (that will represent enhanced production rules), and parse backwards from the `Goal` atom. If I'm not mistaken, only tautologies should parse. Of course, to fully understand what's going on, one is expected to follow the above link to expression logic basics and invest some time in learning what it is all about. The entscheidungsproblem example is meant to interest someone to do so only if one can compare it to the same problem solution in URE. My deal is covering backward chaining using only enhanced parsing algorithm, and covering forward chaining as a solid point between parsed text and the `Goal` atom.

But I understand that most people reading this are too busy to crunch on the proposed read (that probably takes a half an hour or more), while concrete exhaustive testing of the theory behind expression logic is still not performed. Anyway, if one is interested in my ramblings about a relation between parsing and a form of logic without negation, one can find the link in my previous post.

Thank you,

- ivan -

To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAHrUA34KGk15YZ3%3DmCMcboVKSkGj-Y-%2B154NjHJ_1vAYqLrymA%40mail.gmail.com.

[Ivan V.]

TLDR;

Here is a simpler example of a ruleset deciding if an individual is a frog or a duck:

(

    (
        sentence -> Goal
    ) /\ (
        (
            ( (<x> eats flies /\ <x> croaks) -> <x> is a frog ) /\
            ( (<x> eats flies /\ <x> quacks) -> <x> is a duck )
        ) <- (
            <x> <-> word

        )
    ) /\ (
        (

            (<a> and <b>) -> (<a> /\ <b>)
        ) <- (
            ( <a> <-> sentence ) /\
            ( <b> <-> sentence )

        )
    )
) <- (

    ( word sentence -> sentence )
    (          word -> sentence )
    (      /[a-z]+/ -> word     )
)

Given this ruleset, after sequent normalization, if we pass an input:

Nora eats flies and Nora quacks

then we get an abstract syntax tree that looks like:

--+ { Goal }

  +-+ { sentence }

    +-+ { Nora is a duck }

      +-+ { Nora eats flies /\ Nora quacks } // both conjuncts will reside in the same column during chart-parsing - this is that ambiguity part

        +-- { Nora eats flies and Nora quacks }

Basically, expression logic represents URE with a flexible syntax, and that is not that interesting. Another uninteresting fact is that backward chaining may be implemented by using normalized sequents. What is finally interesting is the claim that sequent interpretation may be implemented using a parsing algorithm extended by "left side conjunctions" and "right side disjunctions". The example above shows the "left side conjunctions" part.

Linas commented about link grammar that expresses graphs. In a similar way, normalized sequents may express graph relations, and I thought it may be interesting to bring up the assumption that sequents may be interpreted as enhanced production rules in parsing.

Thank you,

- ivan -