Treebuilding Example

Confident in the theory, I went to my bookshelf, grabbed a book and found a random sentence. Using the following (rough draft) operations:

NEW: begin a new predicate
PUSHCUR: push a noun onto the stack, other operations may use the top
POPCUR: remove top element from stack
WRAPL: move from current position into the left position of a new outer predicate; WRAPL(P) = C → P(C,_). After a NEW, the top of the stack is the current position.
SETR: set the right argument of a predicate
IPWRAPL: perform a WRAPL around the last placed argument
TRNS: a transition such as yet, however, etc.
MODP: modify the predicate in the current scope

Leibniz took up the question in his baccalaureate thesis, and argued in the true scholastic style for a principle of individuation which would preserve the independence of universals with respect to ephemeral sensations, and yet embodied universal ideas in the eternal natures of individuals.

NEW
PUSHCUR leibniz
WRAPL TookUp
SETR the question
WRAPL In
SETR his baccalaureate thesis
NEW
WRAPL Argued
WRAPL Manner
SETR true scholastic style
MODP for (Argued → ArguedFor)
SETR principle of individuation
PUSHCUR principle of individuation
NEW
WRAPL Preserves
SETR independence of universals
IPWRAPL RespectTo
SETR ephemeral sensations
NEW
POPCUR
TRNS yet
WRAPL Embodied
SETR universal ideas
IPWRAPL Regarding
SETR eternal natures of individuals

This is a rough draft of an instruction set that would be output from a system and that can generate a sequence of recursive predicates. Some more instructions detailing scoping would be useful, for example to capture yet(A,B) where A and B are sequences of predicates. Ideally, these connectives pairwise connect the members of each sequence from each scope. Some other modifications might be necessary after looking over more sentences. The noun phrases are capable of being further structured, for example the last portion could be

SETR universal ideas
IPWRAPL Regarding
SETR eternal natures
IPWRAPL Of
SETR individuals

The system should be able to tell from the knowledgebase whether the reifiable substructure, e.g “Of(eternal natures,individuals)”, is itself a composite noun or relatable entity.

The use of a stack is a preliminary approach, other example sentences indicate that the data structure(s) for noun handling are more complex, a set of operations might be required that use the last used noun instead of pushing nouns onto a stack. Also possible is that the scoping is related— data structures are used in scopes. Noun handling in the sequential assembly of recursive parse trees is an interesting area.

I'm thinking on connectives such as “which would” and “yet”. Both easily representable— might be advantageous to do so during NLP because the correct usage of connectives like “yet”, “but” and “however”, that illustrate a semantic constrast of some sort between sequences of predicates, is one distinction between NLG and AI, or first and second generation NLU.

Machine Translation, Machine Reasoning

Using a numerical interlingua, paraphrase generating systems that use the same ontology might have interesting applications for machine translation.

Also it shouldn't be terribly difficult to export from the recursive predicates into CYCL, KIF or RDF for machine reasoning applications. This format can represent its own rule system as well which may allow for implicit knowledge to be obtained via machine reading.

Algorithm Design

After WikiCorpus is up and running, I've a few hypotheses to test on the dataset. The first is the use of finite state automata in the sequential processing hypothesis. The FSM might require one or more stacks or cursors. This would take a preprocessed sentence (via NL tools) as input and output a sequence of treebuilding instructions. Some substrings would have to be mapped to predicate candidates.

This first theory is to transform a sentence into an alphabet of treebuilding instructions that may have its own grammar (universal?). I find the permutations on the predicates at the logic-based or knowledge-based level that allows noun-order paraphrases to be transitioned between, the relationship between this and the treebuilding alphabet and the relation to the sentence paraphrases to be interesting.

Rephrased, each sentence is a sequence of words that can be transformed (FSM, HMM, ?) into one or more sequences of treebuilding instructions and the resulting sequence of predicates (or set of sequence candidates) can be permuted for noun order paraphases using the fact that predicates can map to others with the arguments inverted. It's possible that permutations on the tree can be mapped to transformations on the treebuilding instruction set and this can map back to sentence(s). This level of natural language understanding could also be called a paraphrase generator (a less than exciting name for some rather complicated AI).

Thus, it's theoretically possible that the same system that turns sentences into sequences of predicates can be of use in natural language generation.

Machine Reading, Paraphrases

A rule system may allow semantic subtrees to be mapped to one another. For example, the paraphrase:

Tommy put the book on the shelf to be helpful.
InOrderTo(Did(tommy,PutOn(book,shelf)),Is(tommy,helpful))

The following rule Is(X,helpful) → Help(X,_) might resemble that if something is helpful then that something help(s/ed) some thing or things. Formulating rules in this manner might transcend, in part, hermeneutic circles that occur when relating lexical elements to one another.

Hermeneutic circle refers to the semantic interconnectedness of a set of entities— for example, the definitions in a dictionary refer to other words in that dictionary. Philosophers from Schleiermacher and Dilthey through Heidegger and Gadamer considered this phenomenon. Wittgenstein said regarding this that light dawns gradually over the whole.

A rule system lexicon might further assist the semantic equivalence of paraphrases allowing semantic substructures to map to one another based on the lexical hermeneutic circle.

Like most things in AI, machine reading is more easily described than programmed. Any system that can equate noun-order paraphrases to the same set of predicates (or permutable equivalents) would be a milestone in my opinion.

Algorithm Design

I'm collecting important sentences from linguistics to parse examples to look at for algorithm design in machine reading.

“The girl whose car is blocking my view of the tree that I planted last year is my friend.”

This sentence is from a psycholinguistics article [1] and illustrates recursion or “the use of relative pronouns to refer back to earlier parts of a sentence.”

1) IsFriendOf(girl,I)
2) Possesses(girl,car)
3) Obscuring(car,ViewOf(I,tree))
4) On(Planted(I,tree),last year)

Each of these is a simpler sentence. The predicates' arguments are bound identically which shows the use of URI or integers as opposed to strings as the goal is to be able to place these four into a knowledgebase where they can be used with other knowledge and to retrieve them and reassemble the sentence (sentence aggregation [2]) or sentences as needed.

Simulating the process of accumulating these predicates when processing the sentence in left to right order, or sequentially:

P1(girl, A2)

P1(girl, A2)
Possesses(girl,A3)

P1(girl, A2)
Possesses(girl,car)

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,A4)

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,ViewOf(I,A5))

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,ViewOf(I,tree))

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,ViewOf(I,tree))
P2(I,tree)

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,ViewOf(I,tree))
Planted(I,tree)

P1(girl, A2)
Possesses(girl,car)
Obscuring(car,ViewOf(I,tree))
On(Planted(I,tree),last year)

IsFriendOf(girl, I)
Possesses(girl,car)
Obscuring(car,ViewOf(I,tree))
On(Planted(I,tree),last year)

Another pair of important sentences are:
1) “Fred saw the plane flying over Zurich.”
2) “Fred saw the mountains flying over Zurich.”

1a) Saw(fred,FlyingOver(plane,zurich))
2) While(Saw(fred,mountains),FlyingOver(fred,zurich))

P1(fred,A2)	P1(fred,A2)
Saw(fred,A2)	Saw(fred,A2)
Saw(fred,P2(plane,A3))	Saw(fred,mountains)
Saw(fred,FlyingOver(plane,A3))	While(Saw(fred,mountains),FlyingOver(fred,A3))
Saw(fred,FlyingOver(plane,zurich))	While(Saw(fred,mountains),FlyingOver(fred,zurich))

Looking at the bold line, and assuming a sequential processing, it appears that both hypotheses should be kept by an algorithm at that step. These sentences are an argument for knowledge-based processing and lexical data. It does appear that properties of “mountains” and “plane” can distinguish between hypothesized semantic parses. However, a word like “birds” could be in either parse structure or both simultaneously, depending on the context, for example seeing birds from a plane. Theoretically, knowledge-based, statistical and context-based methodologies can help discern between parse candidates.

Another possible representation of those sentences:
1b) While(Saw(fred,plane), FlyingOver(plane,zurich))
2) While(Saw(fred,mountains),FlyingOver(fred,zurich))

This representation makes clear that the difference is in binding the first argument of FlyingOver. The side by side processing of these two would otherwise be equivalent. I'll have to look at more sentences to determine whether 1a or 1b is more useful or if they are equivalent via a rule system. The representation is important in discerning the algorithm. I'm hopeful a corpus will aid in this area.

The sequential processing hypothesis is based on the proof of concept manner in which people read sequentially, however machines need not process text in the same manner. Additionally, even in the sequential processing hypothesis there are possiblities, for example, the text processor could be one or more words ahead of the predicate generator.

Other hypotheses include structural processing where the semantic tree is generated in a top-down or bottom-up manner based on data, patterns and substructural patterns collected and discerned from a corpus. This information can help determine a parse structure based on the fact that one usage of language resulting in one parse structure is extremely rare and the other commonplace.

[1] Psycholinguistics, Wikipedia
[2] Natural Language Generation, Wikipedia

Semantic Parsing

A sentence that parses to a tree structure with all the arguments of each predicate filled can be said to be semantically complete. However, with a tree structure of nested predicates, it's possible that some sentences, even grammatically correct ones, will parse to structures having blank arguments. This can be explained by the fact that contextual information may have been already delivered earlier in a document and that the author can then exercise brevity. This brevity may be more commonplace in informal spoken language.

Example:
Tommy put the book on the shelf in order to help.
InOrderTo(Did(tommy,PutOn(book,shelf)),Help(tommy,_))

The context of a previous sentence in a document may make clear that the setting is a library and thus the person writing or speaking the above sentence may choose to omit that information, while maintaining grammatical correctness, with a listener being able to discern the semantically complete version.

It's possible when parsing sentences into a semantic tree representation, as above, that some argument slots may be blank. These slots can be filled by either nouns or semantic subtrees and empty slots can help a natural language understanding system to know what is unknown when processing a document.

Some NLU systems may be able to discern ranked candidates for these from previous content or context. Algorithmically, this can be achieved by maintaining a context state during document processing or utilizing an event driven knowledge acquisition engine.

If there's anything to this sentence-level semantic abbreviation in natural speech and writing, then NLG systems might be able to utilize it to produce less mechanical sounding text; a sequence of semantically complete sentences might sound formal or verbose.

Speech Technology, Semantic Web

I'm optimistic about the combination of the following technology I've been reading about:

1) Speech to text
2) Machine reading (NLP)
3) Knowledgebase / web
4) Machine writing (NLG)
5) Text to speech

Maybe someday people will be able to talk to their computers to add to and access collective encyclopedic knowledge.