D-rule

Revision as of 15:42, 27 August 2013 (view source) Martins (Talk | contribs) (→Transformation) ← Older edit		Revision as of 16:01, 27 August 2013 (view source) Martins (Talk | contribs) (→Properties) Newer edit →
Line 121:		Line 121:
	== Properties ==		== Properties ==
		+	;PRIORITY
		+	:Rules are applied serially, according to the order defined in the grammar. The first rule will be the first to be applied, the second will be the second, and so on.
		+	::For instance, given the grammar:
		+	:::(A)(B)=0;
		+	:::(B)(C)=0;
		+	:::(A)(D)=1;
		+	:::(A)(E)=1;
		+	::The first rule to be checked will be the first one, the second, the second one, and so on.<br />
		+	::Note that the order does not affect blocking rules (i.e., those with the right side = 0) but does affect positive rules. In the example above, if the node after (A) could be both (D) or (E), the first option (D) will be preferred because it is the first to appear in the grammar.
		+
		+	;RECURSIVENESS
		+	:Rules are applied recursively as long as their conditions are true.
		+	::For instance, given the grammar:
		+	:::(A)(B)=0;
		+	:::(B)(C)=0;
		+	:::(A)(D)=1;
		+	:::(A)(E)=1;
		+	::The second rule will be applied only after all possible applications of the first rule.
		+
		+	;COMPREHENSIVENESS
		+	:Grammars are applied comprehensively as long as there is at least one applicable rule.
		+
		+	;INDEXATION
		+	:All instances of the same node must be co-indexed (or they will be considered different nodes). See [[Index]].
		+	::For instance:
		+	:::rel(%x;%y)rel(%x;%z)=0; (there cannot be two relations rel with the same source argument)
		+	:::(%x,GEN=%y)(%y,GEN=%x)=1; (two sequential nodes with the same value of the attribute GEN should be preferred over possible alternatives)
		+
		+	;CONJUNCTION
		+	:D-rules may have as many items in the left side as necessary. They must be always juxtaposed:<br />
		+	:::(A)(B)(C)(D)(E)=0; (there cannot be five nodes in sequence with the features A, B, C, D and E, respectively)
		+	:::rel(A;B)rel(C;D)rel(E;F)=0; (there cannot be three relations rel(A;B), rel(C;D) and rel(E;F))
		+
		+	;DISJUNCTION
		+	:The left side of the rules may bring disjuncts, but not the right side. Disjuncts must be represented between {braces} and must be separated by |.
		+	::{(A)|(B)}=0; (there cannot be any node with the feature A nor any node with the feature B)
		+	::{(A)|(B)}(C)=0; (there cannot be any node with the feature A nor any node with the feature B in front of a node with the feature C)
		+	::{rel(A;B)rel(A;C)}=0; (there cannot be any relation rel between nodes with the features A and B, or A and C
		+
		+	;REGULAR EXPRESSIONS
		+	:The left side of the rules may bring [[http://www.pcre.org/ Perl Compatible Regular Expressions]] between "/", as indicated below:
		+	::("/.../")=0; (there cannot be any node with three characters)
		+	::(/[ABC]/)=0; (there cannot be any node with the features A, B or C)
		+	::/(agt|obj)/(D;D)=0; (there cannot any relation agt or obj between two determiners)
		+
		+	;CONCISION
		+	:In order for rules to be as small as possible, the source and the target nodes may be simple place-holders:
		+	:::cob(;):=0; (there cannot be any cob relation between two nodes, whatever the nodes)
		+
		+	;READABILITY
		+	:There can be blank spaces between variables and symbols. Comments can be added after the “;”.
		+	:::cob ( ; ) = 0; (there cannot be any cob  relation).
	== Formal Syntax of Disambiguation Rules ==		== Formal Syntax of Disambiguation Rules ==

---

Revision as of 16:01, 27 August 2013

D-rules or disambiguation rules are used to prevent wrong lexical choices, to provoke best matches and to check the consistency of graphs, trees and lists. The set of D-rules form the Disambiguation grammar, or D-Grammar.

Contents 1 Syntax 2 Types of Disambiguation Rules 2.1 Linear Disambiguation Rules 2.1.1 Examples 2.2 Non-Linear Disambiguation Rules 2.2.1 Examples 3 Scope of Disambiguation Rules 3.1 Tokenization 3.2 Transformation 4 #FINAL 5 Examples 6 Properties 7 Formal Syntax of Disambiguation Rules

Syntax

D-rules follow the general syntax:

STATEMENT=P;

Where
STATEMENT is the left side (condition) of a L-rule or a S-rule; and
P, which can range from 0 (impossible) to 255 (necessary), is the probability of occurrence of the STATEMENT

Types of Disambiguation Rules

There are two types of disambiguation rules:

• Linear disambiguation rules, when the rule applies over lists of nodes
• Non-linear disambiguation rules, when the rule applies over non-linear relations between nodes

Linear Disambiguation Rules

Linear disambiguation rules apply over the natural language list structure to constrain word selection (dictionary retrieval) or the application of both Tree-to-List (TL) and List-to-List (LL) Transformation Rules. They have the following format:

(node 1)(node 2)(...)(node n)=P;

Where (node 1), (node 2) and (node n) are nodes, and P is an integer (from 0 to 255).

Examples

(ART)(VER)=0;

An article (ART) may not precede a verb (VER).

(ART)(NOU)=255;

Articles (ART) always precede nouns (NOU).

Non-Linear Disambiguation Rules

Non-linear disambiguation rules apply over the syntactic or the network structure to constrain the application of List-to-Tree (LT), Tree-to-Tree (TT), Tree-to-Network (TN) and Network-to-Network (NN) Transformation Rules. They have the following format:

REL1(arg1;arg2;...)REL2(arg3;arg4;...)...RELN(argx;argy;...)=P;

Where REL1, REL2 and REL2 are syntactic or semantic relations, with their corresponding arguments (arg1, arg2, ...), and P is an integer (from 0 to 255).

Examples

VS(VER;ADJ)=0;

An adjective (ADJ) may not be an specifier (VS) of a verb (VER).

NS(NOU;DET)=255;

Determiners (DET) are always specifiers (NS) of nouns (NOU).

agt(VER;ADJ)=0;

An adjective (ADJ) may not be an agent (agt) of a verb (VER).

agt(VER;NOU)=255;

Agents (agt) of verbs (VER) are always nouns (NOU).

Scope of Disambiguation Rules

Disambiguation rules may apply:

• Only during tokenization, in order to control the dictionary retrieval
• Only during transformation, in order to control the application of T-rules
• During tokenization and transformation

Tokenization

main article: tokenization

During tokenization, D-rules are used to resolve lexical ambiguities.
For instance, given the dictionary:

• [ ]{}""(BLK)<eng,0,0>;
• [a]{}""(POS=ART)<eng,0,0>;
• [book]{}"to book(equ>to reserve)" (POS=VER)<eng,2,0>; (higher frequency)
• [book]{}"book(icl>document)" (POS=NOU)<eng,1,0>; (lower frequency)

The input string

"a book"

will be tokenized as

("a",[a],[[]],POS=ART)(" ",[ ],[[]],BLK)("book",[book],[[to book(equ>to reserve)]],POS=VER)

which is not correct, because "book", in this context, should be classified as a noun and not as a verb
In order to induce the correct behavior, two types of D-rules could be used:

• to prevent verbs from appearing after article + blank, i.e., (ART)(BLK)(VER)=0; or
• to force possible nouns to appear after article + blank, i.e., (ART)(BLK)(NOU)=1;

In both case the result will be:

("a",[a],[[]],POS=ART)(" ",[ ],[[]],BLK)("book",[book],[[book(icl>document)]],POS=NOU)

which is the correct one.

Transformation

In transformation, D-rules are used to resolve syntactic and semantic ambiguities.
For instance, given the state:

("book",N)("of",P)("Peter",N)("about",P)("John",N)

And the grammar:

1. (%x,N)(%y,P):=(NA(%x;%y),+N); (i.e., replace the sequence noun + preposition by a hyper-node containing a relation NA (noun adjunct) between them)
2. (%x,P)(%y,N):=(PC(%x;%y),+P); (i.e., replace the sequence preposition + noun by a hyper-node containing a relation PC (prepopsition complement) between them)

The result of the application of the rules, in the order defined by the grammar, would be

(NA("book",N;"of",P)("NA("Peter",N;"about",P)("John",N)

which corresponds to the wrong analysis [ [book of] [Peter about] [John] ]
In order to induce the correct behavior, two types of D-rules could be used:

• to prevent NA's from appearing before nouns, i.e., (NA(;))(N)=0;
• to force PC's to apply first, i.e., PC(P;N)=1;

In both cases the result will be:

("book",N)(PC("of",P;"Peter",N),P)(PC("about",P;"John",N),P) (after applying the rule #2 two times)

(NA("book",N;PC("of",P;"Peter",N),P),N)(PC("about",P;"John",N),P)(after applying the rule #1 for the first time)

(NA(NA("book",N;PC("of",P;"Peter",N),P),N;PC("about",P;"John",N),P),N)(after applying the rule #1 for the second time time)

which corresponds to [ [ [book][of Peter] ] [about John] ].

#FINAL

The feature #FINAL is used to indicate which nodes are not expected to be replaced in a D-rule.
Consider, for instance, the input string:

• this book

and the dictionary:

• [this]{1}"00"(R)<eng,0,0>; (this is my book)
• [this]{2}""(D)<eng,0,0>; (this book is mine)
• [book]{4}"book"(N)<eng,0,0>;
• [book]{3}"to book"(V)<eng,0,0>;

According to the order defined in the dictionary, the input string would be tokenized as

• (R)(N) (i.e., [this] = pronoun and [book] = noun)
  

which is not the expected result (we expect "this" to be tokenized as a determiner, rather than as a pronoun)
In order to prevent this tokenization, we may create a D-rule such as:

• (R)(N)=0; (the sequence pronoun + noun is prohibited)

but the result of this rule would be "book" as a verb, instead of "this" as a determiner, i.e.:

• (R)(V) (i.e., [this] = pronoun and [book] = verb)
  

because D-rules apply from left to right, and the system will try to replace first the rightmost nodes, if possible.
In order to prevent the system from replacing the rightmost nodes, we have to assign #FINAL to the nodes to be preserved:

• (R)(N,#FINAL)=0; (there cannot be a pronoun before a noun)

In this case, the machine will try to replace first the node without #FINAL and will get, then:

• (D)(N) (i.e., [this] = determiner and [book] = noun)
  

which is exactly the expected result.

Examples

• List structures
  • (ART)(BLK)(VER)=0; (an article (ART) may not precede a verb (VER))
  • (ART)(BLK)(NOU)=255; (articles (ART) always precede nouns (NOU))
• Syntactic and semantic structures
  • agt(VER;ADJ)=0; (an adjective (ADJ) may not be an agent (agt) of a verb (VER))
  • agt(VER;NOU)=255; (agents (agt) of verbs (VER) are always nouns (NOU))
  • VS(VER;ADJ)=0; (an adjective (ADJ) may not be an specifier (VS) of a verb (VER))
  • NS(NOU;DET)=255; (determiners (DET) are always specifiers (NS) of nouns (NOU))

Properties

PRIORITY

Rules are applied serially, according to the order defined in the grammar. The first rule will be the first to be applied, the second will be the second, and so on.

For instance, given the grammar:

(A)(B)=0;

(B)(C)=0;

(A)(D)=1;

(A)(E)=1;

The first rule to be checked will be the first one, the second, the second one, and so on.

Note that the order does not affect blocking rules (i.e., those with the right side = 0) but does affect positive rules. In the example above, if the node after (A) could be both (D) or (E), the first option (D) will be preferred because it is the first to appear in the grammar.

RECURSIVENESS

Rules are applied recursively as long as their conditions are true.

For instance, given the grammar:

(A)(B)=0;

(B)(C)=0;

(A)(D)=1;

(A)(E)=1;

The second rule will be applied only after all possible applications of the first rule.

COMPREHENSIVENESS

Grammars are applied comprehensively as long as there is at least one applicable rule.

INDEXATION

All instances of the same node must be co-indexed (or they will be considered different nodes). See Index.

For instance:

rel(%x;%y)rel(%x;%z)=0; (there cannot be two relations rel with the same source argument)

(%x,GEN=%y)(%y,GEN=%x)=1; (two sequential nodes with the same value of the attribute GEN should be preferred over possible alternatives)

CONJUNCTION

D-rules may have as many items in the left side as necessary. They must be always juxtaposed:

(A)(B)(C)(D)(E)=0; (there cannot be five nodes in sequence with the features A, B, C, D and E, respectively)

rel(A;B)rel(C;D)rel(E;F)=0; (there cannot be three relations rel(A;B), rel(C;D) and rel(E;F))

DISJUNCTION

The left side of the rules may bring disjuncts, but not the right side. Disjuncts must be represented between {braces} and must be separated by |.

{(A)|(B)}=0; (there cannot be any node with the feature A nor any node with the feature B)

{(A)|(B)}(C)=0; (there cannot be any node with the feature A nor any node with the feature B in front of a node with the feature C)

{rel(A;B)rel(A;C)}=0; (there cannot be any relation rel between nodes with the features A and B, or A and C

REGULAR EXPRESSIONS

The left side of the rules may bring [Perl Compatible Regular Expressions] between "/", as indicated below:

("/.../")=0; (there cannot be any node with three characters)

(/[ABC]/)=0; (there cannot be any node with the features A, B or C)

/(agt|obj)/(D;D)=0; (there cannot any relation agt or obj between two determiners)

CONCISION

In order for rules to be as small as possible, the source and the target nodes may be simple place-holders:

cob(;):=0; (there cannot be any cob relation between two nodes, whatever the nodes)

READABILITY

There can be blank spaces between variables and symbols. Comments can be added after the “;”.

cob ( ; ) = 0; (there cannot be any cob relation).

Formal Syntax of Disambiguation Rules

Disambiguation rules must comply with the following syntax

<DISAMBIGUATION RULE> ::= <NN RULE> | <TT RULE> | <LL RULE> 
<NN RULE>             ::= (<SEM>)+ "=" [0-255]";"
<TT RULE>             ::= (<SYN>)+ "=" [0-255]";"
<LL RULE>             ::= "(" <NODE> ")" ( "(" <NODE> ")" )+ "=" [0-255]";"
<SEM>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<SYN>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<NODE>                ::= ( (<DESCRIPTION>)( "," <DESCRIPTION> )* )?
<DESCRIPTION>         ::= <STRING> | <ENTRY> | <FEATURE> | <RELATION>
<STRING>              ::= """<text>"""
<ENTRY>               ::= "["<entry>"]"
<FEATURE>             ::= <VALUE> | <ATTRIBUTE> | <ATTRIBUTE>"="<VALUE>
<RELATION>            ::= <SEM>|<SYN>
<VALUE>               ::= <TEXT>
<ATTRIBUTE>           ::= <TEXT>
<TEXT>                ::= any sequence of characters except whitespace | <REGULAR EXPRESSION>
<REGULAR EXPRESSION>  ::= "/"<PERL COMPATIBLE REGULAR EXPRESSIONS>"/"