While working on the parser, I developed a new syntax that appears to be more readily parsed into. While this new syntax appears more readily processed into (from natural language), the syntax described previously appears to be more readily generated from (to natural language). There's a simple heuristic for converting between the two; the new syntax and grammar are a superset of the old syntax and grammar.
In the new syntax there are notational varieties of predicates. These notational conventions appear to reduce the instruction set for building the predicates sequentially and to reduce the context information required during the processing of a sentence— making the heuristic simpler.
Showing posts with label nlp. Show all posts
Showing posts with label nlp. Show all posts
Sunday, May 27, 2007
Sunday, May 13, 2007
Preprocessing and Predicate Patterns
I found an example sentence that shows a promising relationship between the preprocessing and patterns in the predicates. That is, a correct preprocessing can indicate patterns that an incorrect chunking does not.
For example,
{the scientific method}[Seeks+][To+][Explain]{the complexities}[Of]{nature}[In]{a replicable way}<comma><and>[To+][Use]{these explanations}[To+][Make]{useful predictions}
H(B+C+D(A,F(E,G)),I)
O+P(L+M(A,N),Q)
Notice, that B could move across the <comma><and>
H(B+C+D(A,F(E,G)),I)
O+P(B+L+M(A,N),Q)
However, the preprocessing:
{the scientific method}[Seeks][To+][Explain]{the complexities}[Of]{nature}[In]{a replicable way}<comma><and>[To+][Use]{these explanations}[To][Make]{useful predictions}
B(A,H(C+D(_,F(E,G)),I)&O(L+M(_,N),P(_,Q)))
or
B(A,H(C+D(_,F(E,G)),I))
B(A,O(L+M(_,N),P(_,Q)))
Is more illustrative of the patterns indicative of sentences with <comma><and>, namely P(x, y1&y2...). The ampersand is a notational convention that is useful during sequential processing.
The pattern evidenced in the second predicate output, related to the <comma><and>, indicates that the second chunking was more correct than the first. This indicates that the chunking and choice in predicates is not arbitrary and that a set may emerge from patterns dependent upon the <> symbols in certain sentences.
I will find more example sentences that indicate that patterns in the output can reinforce chunking hypotheses. Some areas, in English, that are of potential complexity include the word 'to'.
Bobby went to the store.
{bobby}[Went][+To]{the store}.
B+C(A,D)
Here the 'to' is in the sense of 'towards'.
Bobby likes to draw.
{bobby}[Likes][To+][Draw].
B(A,C(_,_))
Here the 'to' is in the sense of an infinitive.
Bobby bought crayons to draw.
{bobby}[Bought]{crayons}[To][Draw]{pictures}.
D(B(A,C),E(_,F))
Here the 'to' is in the sense of 'in order to'.
Predicates and chunking appear to be a discernable property of patterns from <> in certain sentences. For example, the argument above is that SeeksToExplain(x,y) is not a predicate and that Seeks(x,y), Explain(x,y) are.
For example,
{the scientific method}[Seeks+][To+][Explain]{the complexities}[Of]{nature}[In]{a replicable way}<comma><and>[To+][Use]{these explanations}[To+][Make]{useful predictions}
H(B+C+D(A,F(E,G)),I)
O+P(L+M(A,N),Q)
Notice, that B could move across the <comma><and>
H(B+C+D(A,F(E,G)),I)
O+P(B+L+M(A,N),Q)
However, the preprocessing:
{the scientific method}[Seeks][To+][Explain]{the complexities}[Of]{nature}[In]{a replicable way}<comma><and>[To+][Use]{these explanations}[To][Make]{useful predictions}
B(A,H(C+D(_,F(E,G)),I)&O(L+M(_,N),P(_,Q)))
or
B(A,H(C+D(_,F(E,G)),I))
B(A,O(L+M(_,N),P(_,Q)))
Is more illustrative of the patterns indicative of sentences with <comma><and>, namely P(x, y1&y2...). The ampersand is a notational convention that is useful during sequential processing.
The pattern evidenced in the second predicate output, related to the <comma><and>, indicates that the second chunking was more correct than the first. This indicates that the chunking and choice in predicates is not arbitrary and that a set may emerge from patterns dependent upon the <> symbols in certain sentences.
I will find more example sentences that indicate that patterns in the output can reinforce chunking hypotheses. Some areas, in English, that are of potential complexity include the word 'to'.
Bobby went to the store.
{bobby}[Went][+To]{the store}.
B+C(A,D)
Here the 'to' is in the sense of 'towards'.
Bobby likes to draw.
{bobby}[Likes][To+][Draw].
B(A,C(_,_))
Here the 'to' is in the sense of an infinitive.
Bobby bought crayons to draw.
{bobby}[Bought]{crayons}[To][Draw]{pictures}.
D(B(A,C),E(_,F))
Here the 'to' is in the sense of 'in order to'.
Predicates and chunking appear to be a discernable property of patterns from <> in certain sentences. For example, the argument above is that SeeksToExplain(x,y) is not a predicate and that Seeks(x,y), Explain(x,y) are.
Friday, May 4, 2007
Wikipedia Example 3
The term Artificial Intelligence (AI) was first used by John McCarthy who used it to mean "the science and engineering of making intelligent machines". It can also refer to intelligence as exhibited by an artificial (man-made, non-natural, manufactured) entity. The terms strong and weak AI can be used to narrow the definition for classifying such systems. AI is studied in overlapping fields of computer science, psychology, philosophy, neuroscience and engineering, dealing with intelligent behavior, learning and adaptation and usually developed using customized machines or computers.
Research in AI is concerned with producing machines to automate tasks requiring intelligent behavior. Examples include control, planning and scheduling, the ability to answer diagnostic and consumer questions, handwriting, natural language, speech and facial recognition. As such, the study of AI has also become an engineering discipline, focused on providing solutions to real life problems, knowledge mining, software applications, strategy games like computer chess and other video games. One of the biggest difficulties with AI is that of comprehension. Many devices have been created that can do amazing things, but critics of AI claim that no actual comprehension by the AI machine has taken place. [1]
{The term Artificial Intelligence|A} [was first used by|B] {John McCarthy|C} <who|D> [used|E] {it|F} [to mean|G] <"|H> {the science and engineering|I} [of|J] {making intelligent machines|K} <"|L>. {It|M} [can also refer to|N] {intelligence|O} as [exhibited by|P] {an artificial (man-made, non-natural, manufactured) entity|Q}. {The terms strong and weak AI|R} [can be used to narrow|S] {the definition|T} [for|U] [classifying|V] {such systems|W}. {AI|X} is [studied|Y] [in|Z] {overlapping fields|AA} [of|AB] {computer science|AC}, {psychology|AD}, {philosophy|AE}, {neuroscience and engineering|AF}, [dealing with|AG] {intelligent behavior|AH}, {learning and adaptation|AI} and [usually developed using|AJ] {customized machines|AK} [or|AL] {computers|AM}.
{Research in AI|AN} [is concerned with|AO] [producing|AP] {machines|AQ} [to automate|AR] {tasks|AS} [requiring|AT] {intelligent behavior|AU}. {Examples|AV} [include|AW] {control|AX}, [planning and scheduling|AY], [the ability to answer|AZ] {diagnostic and consumer questions|BA}, {handwriting|BB}, {natural language|BC}, {speech and facial recognition|BD}. <As such|BE>, {the study|BF} [of|BG] {AI|BH} [has also become|BI] {an engineering discipline|BJ}, [focused on providing|BK] {solutions|BL} [to|BM] {real life problems|BN}, {knowledge mining|BO}, {software applications|BP}, {strategy games|BQ} [like|BR] {computer chess and other video games|BS}. {One|BT} [of|BU] {the biggest difficulties|BV} [with|BW] {AI|BX} [is|BY] <that|BZ> <of|CA> {comprehension|CB}. {Many devices|CC} [have been created|CD] that [can do|CE] {amazing things|CF}, <but|CG> {critics|CH} [of|CI] {AI|CJ} [claim|CK] that <no|CL> {actual comprehension|CM} [by|CN] {the AI machine|CO} [has|CP] {taken place|CQ}.
B(A,C)
G(E(C,F),J(I,K))
N(M,P(O,Q))
S(R,U(T,V(_,W)))
Y+Z(X,AB(AA,AC&AD&AE&AF&AG&AH&AI))
AJ(X,AL(AK,AM))
AO(AN,AR(AP(_,AQ),AT(AS,AU)))
BE(AW(AV,AX&AY(_,_)&AZ(_,BA)&BB&BC&BD),BI(BG(BF,BH),BJ))
BE(AW(AV,AX&AY(_,_)&AZ(_,BA)&BB&BC&BD),BK(BJ,BM(BL,BN&BO&BP&BR(BQ,BS))))
BY(BW(BU(BT,BV),BX),CB)
CG(CE(CD(CC,_),CF),CK(CI(CH,CJ),!CP(CN(CM,CO),CQ)))
I'm looking into the linguistic reification of occurrence in the representation format (... CP CQ). A logic-based rule system may aid in this area.
Also interesting in this text is the passive voice, “Many devices have been created that can do amazing things.” The underscore indicates that the creator is unknown to the machine reading algorithm: CA(BZ,_) as CA corrolates to ~Created. I'm using the notation P(_,_) to represent gerunds.
One strategy in developing machine reading algorithms is to look at children's books and texts. These are already categorized by reading level, so any algorithm that appears to somehow build on itself as the reading level is increased would, philosophically, have additional merit, in my opinion.
[1] Artificial Intelligence, Wikipedia
Tuesday, May 1, 2007
Foundations of Machine Reading/Writing
[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].
Let us label each bracketed chunk with a letter, A through S.
with the [yet] (O), we would have
D(B(A,C),E)
{
G(F+I(A,J),H)
K(J,M(L,N))
}
O
{
P(A,R(Q,S))
}
Theoretically resembling:
D(B(A,C),E)
G(F+I(A,J),H)
K(J,M(L,N))
P(A,R(Q,S))
O(G(F+I(A,J),H),P(A,R(Q,S)))
O(K(J,M(L,N),P(A,R(Q,S)))
but let us look at the following four and call the processing of O a metaoperation.
D(B(A,C),E)
G(F+I(A,J),H)
K(J,M(L,N))
P(A,R(Q,S))
So, in this paradigm of machine reading, the goal is to turn a sequence of chunks into a structure with necessary internal states to manage the noun chunks during the process. Transitions may occur via chunked and non-chunked tokens.
How would we describe the process of building these four predicates?
Start a new predicate with A as the left argument.
Name that predicate B.
Place C in the right argument of that predicate.
Move that predicate into the left position of a new predicate.
Name that predicate D.
Place E in the right argument of that predicate.
Start a new predicate with A as the left argument.
Name that predicate F.
Move that predicate into the left position of a new predicate.
Name that predicate G.
Place H in the right argument of that predicate.
Now back to the last predicate that we just moved into the left position of this predicate.
Add I to that predicate's label.
Place J in the right argument of that predicate.
Start a new predicate with J as the left argument.
Name that predicate K.
The next statement is set in the right argument of that predicate.
Start a new predicate with L as the left argument.
Name that predicate M.
Place N in the right argument of that predicate.
Start a new predicate with A as the left argument.
Name that predicate P.
The next statement is set in the right argument of that predicate.
Start a new predicate with Q as the left argument.
Name that predicate R.
Place S in the right argument of that predicate.
Patterns:
(×4)
Start a new predicate with <X> as the left argument.
Name that predicate <X+1>.
(×3)
Start a new predicate with <X> as the left argument.
Name that predicate <X+1>.
Place <X+2> in the right argument of that predicate.
(×2)
Name that predicate <X>.
The next statement is set in the right argument of that predicate.
Start a new predicate with <X+1> as the left argument.
Name that predicate <X+2>.
Place <X+3> in the right argument of that predicate.
“A” is the subject of the sentence, "Start a new predicate with A as the left argument" (×3)
In two of the occasions that "Start a new predicate with A as the left argument" occurs (Start a new predicate with <SUBJ> as the left argument), it is preceded by "Place <X> in the right argument of that predicate." As the sentence ends with that instruction, it is possible that in a sequence of sentences, all three occurances would be.
I theorize that in a processed document, a continuous sequence of these instructions (across sentence boundaries) would have robust and complex patterns indicative of natural writing style. Furthermore, I theorize that this methodology will be able to explain why people read active tense faster than passive and how these are processed differently in this paradigm.
Let us label each bracketed chunk with a letter, A through S.
with the [yet] (O), we would have
D(B(A,C),E)
{
G(F+I(A,J),H)
K(J,M(L,N))
}
O
{
P(A,R(Q,S))
}
Theoretically resembling:
D(B(A,C),E)
G(F+I(A,J),H)
K(J,M(L,N))
P(A,R(Q,S))
O(G(F+I(A,J),H),P(A,R(Q,S)))
O(K(J,M(L,N),P(A,R(Q,S)))
but let us look at the following four and call the processing of O a metaoperation.
D(B(A,C),E)
G(F+I(A,J),H)
K(J,M(L,N))
P(A,R(Q,S))
So, in this paradigm of machine reading, the goal is to turn a sequence of chunks into a structure with necessary internal states to manage the noun chunks during the process. Transitions may occur via chunked and non-chunked tokens.
How would we describe the process of building these four predicates?
Start a new predicate with A as the left argument.
Name that predicate B.
Place C in the right argument of that predicate.
Move that predicate into the left position of a new predicate.
Name that predicate D.
Place E in the right argument of that predicate.
Start a new predicate with A as the left argument.
Name that predicate F.
Move that predicate into the left position of a new predicate.
Name that predicate G.
Place H in the right argument of that predicate.
Now back to the last predicate that we just moved into the left position of this predicate.
Add I to that predicate's label.
Place J in the right argument of that predicate.
Start a new predicate with J as the left argument.
Name that predicate K.
The next statement is set in the right argument of that predicate.
Start a new predicate with L as the left argument.
Name that predicate M.
Place N in the right argument of that predicate.
Start a new predicate with A as the left argument.
Name that predicate P.
The next statement is set in the right argument of that predicate.
Start a new predicate with Q as the left argument.
Name that predicate R.
Place S in the right argument of that predicate.
Patterns:
(×4)
Start a new predicate with <X> as the left argument.
Name that predicate <X+1>.
(×3)
Start a new predicate with <X> as the left argument.
Name that predicate <X+1>.
Place <X+2> in the right argument of that predicate.
(×2)
Name that predicate <X>.
The next statement is set in the right argument of that predicate.
Start a new predicate with <X+1> as the left argument.
Name that predicate <X+2>.
Place <X+3> in the right argument of that predicate.
“A” is the subject of the sentence, "Start a new predicate with A as the left argument" (×3)
In two of the occasions that "Start a new predicate with A as the left argument" occurs (Start a new predicate with <SUBJ> as the left argument), it is preceded by "Place <X> in the right argument of that predicate." As the sentence ends with that instruction, it is possible that in a sequence of sentences, all three occurances would be.
I theorize that in a processed document, a continuous sequence of these instructions (across sentence boundaries) would have robust and complex patterns indicative of natural writing style. Furthermore, I theorize that this methodology will be able to explain why people read active tense faster than passive and how these are processed differently in this paradigm.
Monday, April 30, 2007
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
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.
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.
Thursday, April 26, 2007
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))
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
“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
Saturday, April 21, 2007
Reification, Ontological Consensus and Ergonomics
Ontological consensus is the goal of the WikiCorpus project and is, in theory, possible via the on screen predictive list of predicates. Users would rather select predicates (that work for the semantics of the sentence) from the list than create new ones, just as users prefer to find the results of a search on the first page of a search engine's results. This list, hopefully produced by an accurate predictive algorithm, will facilitate consistency in the dataset.
In the user interface, the ergonomics of nested predicates would be that a completed predicate can be dragged (moved or copied) into the argument slot of a predicate being formed. The problem is, firstly, that moving and copying the predicate are both done with the drag and drop motion. Secondly, the nesting of predicates might deter from semantic and ontological consensus as complicated constructions are possible from the elements in the predictive list.
Take for example:
1) The book was put on the shelf.
2) Tommy put the book on the shelf.
3) Tommy put the book on the shelf to help the library.
Each is a semantic superset of its previous sentence duplicating and nesting the previous predicate.
1) PutOn(book,shelf)
2) Did(tommy,PutOn(book,shelf))
3) InOrderTo(Did(tommy,PutOn(book,shelf)),Help(tommy,library))
That is, the first sentence is the first predicate, the second is both the first and second, and the third is all three. Two terms related to this method of representing sentences are that sentences have a semantic core and a semantic root (I'll try to find out if other terminology already exists). The core is the predicate constructed from, often the most nested predicate, and the root is the least and the root of the corresponding tree structure.
So, while recursive binary predicates appear to be able to capture natural language, the interface considerations and ergonomics are more complicated. Also, finding the semantic core of sentences appears to relate to placing the sentence into its semantic frame via PropBank or FrameNet corpora; the algorithm would then be to construct the entirety. These nested predicates can be represented in the matrix format with some notational conventions.
Interestingly, similar to the reording of nouns in the matrix format, the reordering of the predicate arguments or nouns can be done, resembling:
InOrderTo(DoneBy(PutOn(book,shelf),tommy),Help(tommy,library))
The book was put on the shelf by Tommy to help the library.
InOrderToInverse(Help(tommy,library),DoneBy(PutOn(book,shelf),tommy))
In order to help the library, the book was put on the shelf by Tommy.
In order for Tommy to help the library, the book was put on the shelf by him.
InOrderToInverse(Help(tommy,library),Did(tommy,PutOn(book,shelf))
In order for Tommy to help the library, he put the book on the shelf.
To help the library, Tommy put the book on the shelf.
So, each binary predicate may be related to another predicate with its arguments in the opposite order. Some predicates may not, limiting the possible noun orderings for paraphrases. This is just one approach to capturing semantics using nested predicates; I look forward to learning other approaches and designing a web interface for a collaborative corpus.
In the user interface, the ergonomics of nested predicates would be that a completed predicate can be dragged (moved or copied) into the argument slot of a predicate being formed. The problem is, firstly, that moving and copying the predicate are both done with the drag and drop motion. Secondly, the nesting of predicates might deter from semantic and ontological consensus as complicated constructions are possible from the elements in the predictive list.
Take for example:
1) The book was put on the shelf.
2) Tommy put the book on the shelf.
3) Tommy put the book on the shelf to help the library.
Each is a semantic superset of its previous sentence duplicating and nesting the previous predicate.
1) PutOn(book,shelf)
2) Did(tommy,PutOn(book,shelf))
3) InOrderTo(Did(tommy,PutOn(book,shelf)),Help(tommy,library))
That is, the first sentence is the first predicate, the second is both the first and second, and the third is all three. Two terms related to this method of representing sentences are that sentences have a semantic core and a semantic root (I'll try to find out if other terminology already exists). The core is the predicate constructed from, often the most nested predicate, and the root is the least and the root of the corresponding tree structure.
So, while recursive binary predicates appear to be able to capture natural language, the interface considerations and ergonomics are more complicated. Also, finding the semantic core of sentences appears to relate to placing the sentence into its semantic frame via PropBank or FrameNet corpora; the algorithm would then be to construct the entirety. These nested predicates can be represented in the matrix format with some notational conventions.
Interestingly, similar to the reording of nouns in the matrix format, the reordering of the predicate arguments or nouns can be done, resembling:
InOrderTo(DoneBy(PutOn(book,shelf),tommy),Help(tommy,library))
The book was put on the shelf by Tommy to help the library.
InOrderToInverse(Help(tommy,library),DoneBy(PutOn(book,shelf),tommy))
In order to help the library, the book was put on the shelf by Tommy.
In order for Tommy to help the library, the book was put on the shelf by him.
InOrderToInverse(Help(tommy,library),Did(tommy,PutOn(book,shelf))
In order for Tommy to help the library, he put the book on the shelf.
To help the library, Tommy put the book on the shelf.
So, each binary predicate may be related to another predicate with its arguments in the opposite order. Some predicates may not, limiting the possible noun orderings for paraphrases. This is just one approach to capturing semantics using nested predicates; I look forward to learning other approaches and designing a web interface for a collaborative corpus.
Labels:
knowledge representation,
nlg,
nlp,
ontology,
wikicorpus
Thursday, April 19, 2007
Knowledge Representation, Paraphrases
In machine reading, a goal is for all paraphrases to be processed into the same set of predicates or other form of representing semantics. One method I found to represent this feature is to represent a sentence as a block matrix representing the pairwise binary predicates between nouns. This utilizes the fact that n-ary predicates can be decomposed into a set of binary predicates.
The rows and columns are in the order of nouns occurring in a sentence and the entry in the i-th row and j-th column is meant as the predicate(s) that relate(s) the i-th and j-th noun (nouns on main diagonal). Using this, permutations can change noun ordering (one variety of paraphrases) and the semantics can be preserved.
Example:
1) Tommy went to the store to get a crescent wrench. <Tommy,store,wrench>
2) To get a crescent wrench, Tommy went to the store. <wrench,Tommy,store>
From this or another noun-order invariant representation format, the goal of NLG is then to compose grammatically correct sentences containing the semantics with the nouns in the order of the underlying matrix. A reason for robustness in this is that noun ordering is often context dependent, as sentences are composed in paragraphs and documents; both noun ordering and sentence aggregation [1] are overarching processes that are part of “good writing style”.
Using the phases of NLG from the article, the process with this knowledge representation may resemble:
Content determination: Knowledge is obtained from a knowledgebase or web.
Discourse planning: Knowledge is moved into a matrix format.
Sentence aggregation: Block diagonalization and utilization of other patterns discerned from a corpus of well-written articles.
Lexicalisation: Putting words to the concepts.
Referring expression generation: Linking words in the sentences by introducing pronouns and other types of means of reference.
Syntactic and morphological realisation: Permutations are applied as per patterns discerned from well-written articles; each sentence is realized with the nouns in the best order.
Orthographic realisation: Matters like casing, punctuation, and formatting are resolved.
[1] Natural Language Generation, Wikipedia article
The rows and columns are in the order of nouns occurring in a sentence and the entry in the i-th row and j-th column is meant as the predicate(s) that relate(s) the i-th and j-th noun (nouns on main diagonal). Using this, permutations can change noun ordering (one variety of paraphrases) and the semantics can be preserved.
Example:
1) Tommy went to the store to get a crescent wrench. <Tommy,store,wrench>
2) To get a crescent wrench, Tommy went to the store. <wrench,Tommy,store>
From this or another noun-order invariant representation format, the goal of NLG is then to compose grammatically correct sentences containing the semantics with the nouns in the order of the underlying matrix. A reason for robustness in this is that noun ordering is often context dependent, as sentences are composed in paragraphs and documents; both noun ordering and sentence aggregation [1] are overarching processes that are part of “good writing style”.
Using the phases of NLG from the article, the process with this knowledge representation may resemble:
Content determination: Knowledge is obtained from a knowledgebase or web.
Discourse planning: Knowledge is moved into a matrix format.
Sentence aggregation: Block diagonalization and utilization of other patterns discerned from a corpus of well-written articles.
Lexicalisation: Putting words to the concepts.
Referring expression generation: Linking words in the sentences by introducing pronouns and other types of means of reference.
Syntactic and morphological realisation: Permutations are applied as per patterns discerned from well-written articles; each sentence is realized with the nouns in the best order.
Orthographic realisation: Matters like casing, punctuation, and formatting are resolved.
[1] Natural Language Generation, Wikipedia article
WikiCorpus, Natural Language Processing
I'm tentatively calling the website 'WikiCorpus Project'. I'm hoping to make the interface as easy to use as possible to make entering read knowledge a rapid and ergonomic process. Interestingly, the design of the interface and algorithms for ergonomics are similar to the process of natural language processing.
There will be an on screen list of predicates offered to the user for each sentence. Hopefully, this list will be accurately predicted so that the user does not have to search for or create a new predicate. This predictive list will likely improve over time, as the corpus is populated, using patterns in the sentence (improved by word sense discernment, see: WordNet) and context. This (now theoretical) algorithm and its statistics-based dataset (both to be freely downloadable) might be of use as an algorithm component to some approaches.
Pronouns and other indirect entity references will have a context-menu where the user can select which entity the reference refers to. Again, ideally the correct reference is the first in a list offered and the goal is to minimize the probability of the user having to select 'Other' and select from a comprehensive list of the entities in the document.
So where NLP aims to resolve these completely, the ergonomics of this project aim to make an improving list of options for a user entering the knowledge they are reading. The ergonomics says that the predicate they are going to use next should be on screen (predicted) and the resolving of pronouns should have the correct candidate (hopefully first) in a drop down list.
The ergonomics then is an “easier” problem resembling information retrieval and predictive search that hopefully can be of use to some algorithmic approaches to the “less easy” task of mechanically and accurately doing the entire process (reading) on sentences in documents.
There will be an on screen list of predicates offered to the user for each sentence. Hopefully, this list will be accurately predicted so that the user does not have to search for or create a new predicate. This predictive list will likely improve over time, as the corpus is populated, using patterns in the sentence (improved by word sense discernment, see: WordNet) and context. This (now theoretical) algorithm and its statistics-based dataset (both to be freely downloadable) might be of use as an algorithm component to some approaches.
Pronouns and other indirect entity references will have a context-menu where the user can select which entity the reference refers to. Again, ideally the correct reference is the first in a list offered and the goal is to minimize the probability of the user having to select 'Other' and select from a comprehensive list of the entities in the document.
So where NLP aims to resolve these completely, the ergonomics of this project aim to make an improving list of options for a user entering the knowledge they are reading. The ergonomics says that the predicate they are going to use next should be on screen (predicted) and the resolving of pronouns should have the correct candidate (hopefully first) in a drop down list.
The ergonomics then is an “easier” problem resembling information retrieval and predictive search that hopefully can be of use to some algorithmic approaches to the “less easy” task of mechanically and accurately doing the entire process (reading) on sentences in documents.
Friday, April 13, 2007
Semantic Role Labeling
Semantic Role Labeling (SRL) appears to be the algorithmically independent term for parsing sentences into structures like PropBank or FrameNet.
I'm investigating ontology to store the SRL'd structure that can additionally be used for NLG. I'm looking at loom, kpml, cypher and others to see if there's any overlap. It'd be “easier” to code if there's one format to and from natural language. Not sure if this SRL'd/pre-NLG would work well for machine reasoning (which is ideally what'd be stored in a db).
[1] CoNLL-2005 Shared Task: Semantic Role Labeling
[2] CCG: Semantic Role Labeling Demo
I'm investigating ontology to store the SRL'd structure that can additionally be used for NLG. I'm looking at loom, kpml, cypher and others to see if there's any overlap. It'd be “easier” to code if there's one format to and from natural language. Not sure if this SRL'd/pre-NLG would work well for machine reasoning (which is ideally what'd be stored in a db).
[1] CoNLL-2005 Shared Task: Semantic Role Labeling
[2] CCG: Semantic Role Labeling Demo
Head-Driven Phrase Structure Grammar
I'm thinking that the PropBank style of parsing (redwoods treebank) is more readily converted to structured knowledge than part of speech tagging. However, looking over the initial results of some software, it appears that some style of recursion would be of use in capturing all the structure (substructure) of a sentence. Some arguments to the main predicate appear to have discernable structure remaining — if an argument to the predicate could be a predicate, then this would capture as much structure as possible. Also noticing the inability of this style of parser to capture parallel predicates with some sentences that use logical connectives. Different levels in the recursion should be able to reuse arguments from across the sentence. I may have to code up a prototype to obtain as much semantic structure as possible, possibly outputting a set of these parses that capture it in parallel.
Also looking into initializing this style of parser with the POS-style to discern the main verb and then the remainder in order. After entity recognition and string concatenation of multiword nouns, parsers seem to function more accurately. I'm going to look at the parse trees for verb hierarchy and SBAR information to construct recursive predicate structures, utilize the NP information to bootstrap entity recognition, and post here which code appears “easiest” to build from.
[1] Miyao, Y. and Tsujii, J. 2004. Deep linguistic analysis for the accurate identification of predicate-argument relations. In Proceedings of the 20th international Conference on Computational Linguistics (Geneva, Switzerland, August 23 - 27, 2004). International Conference On Computational Linguistics. Association for Computational Linguistics, Morristown, NJ, 1392.
[2] Towards Parsing Unrestricted Text into PropBank Predicate-Argument Structures
Also looking into initializing this style of parser with the POS-style to discern the main verb and then the remainder in order. After entity recognition and string concatenation of multiword nouns, parsers seem to function more accurately. I'm going to look at the parse trees for verb hierarchy and SBAR information to construct recursive predicate structures, utilize the NP information to bootstrap entity recognition, and post here which code appears “easiest” to build from.
[1] Miyao, Y. and Tsujii, J. 2004. Deep linguistic analysis for the accurate identification of predicate-argument relations. In Proceedings of the 20th international Conference on Computational Linguistics (Geneva, Switzerland, August 23 - 27, 2004). International Conference On Computational Linguistics. Association for Computational Linguistics, Morristown, NJ, 1392.
[2] Towards Parsing Unrestricted Text into PropBank Predicate-Argument Structures
Labels:
hpsg,
nlp,
propbank,
semantic web,
sentence parsing
Thursday, April 12, 2007
Natural Language and Semantic Web
Been browsing on the Web for various tools in natural language processing (NLP) and natural language generation (NLG). Presently looking at cypher, heart of gold, gate, stanford parser, charniak parser, enju, opennlp, lkb, assert, halogen, kpml and a couple of others. Also looking at a couple of methods of storing structured knowledge from a parse including Berkeley's FrameNet ontology and some that came with halogen and kpml. Hoping to throw these tools at the Wikipedia dataset (9.74 gb) and post some results.
Subscribe to:
Posts (Atom)