Information Technology Reference
In-Depth Information
⎡
⎤
⎡
⎤
seized
VBD
Verb
protesters
NNS
Noun
Person
stations
NNS
Noun
Facility
⎣
⎦
×
[
→
]
×
⎣
⎦
×
[
←
]
×
Fig. 3.6.
Featuregenerationfromdependency path.
Forverbs and nouns(and their respective word classes) occurring along ade-
pendency path we also use an additionalsu
x '(-)' to indicate anegative polarity
item.Inthecase ofverbs, thissu
x is usedwhenthe verb (oranattached auxil-
iary) is modifiedbyanegative polarity adverb suchas 'not'or'never.' Nounsget
the negativesu
x whenevertheyare modifiedbynegative determinerssuchas 'no,'
'neither'or'nor.' For example, the phrase “He neverwent to Paris” is associated
with the dependency path “He
→
went(-)
←
to
←
Paris.”
As in Section3.2, we use kernel SVMs in orderto avoid workingexplicitly
with high-dimensional dependency path feature vectors. Computing the dot-product
(i.e., kernel) betweentwo relation examples amounts tocalculating the number of
commonfeatures (i.e., paths) betweenthe twoexamples. If
x
=
x
1
x
2
...x
m
and
y
=
y
1
y
2
...y
n
are two relation examples, where
x
i
denotes theset ofword classes
corresponding to position
i
(as in Figure 3.6), thenthe number of commonfeatures
between
x
and
y
iscomputedas in Equation3.4.
n
K
(
x
,
y
)=
1
(
m
=
n
)
·
c
(
x
i
,y
i
)
(3.4)
i
=1
where
c
(
x
i
,y
i
)=
is the number of commonword classes between
x
i
and
y
i
.
This is a simple kernel, whose computationtakes
O
(
n
) time. Ifthe two paths
have different lengths, they correspond to different waysof expressing arelationship
- forinstance, theymaypass through a different number ofpredicate argument
structures. Consequently, the kernel is definedto be0in thiscase. Otherwise, it
is the product ofthe number of commonword classes at eachpositioninthe two
paths. As an example, letusconsidertwo instances ofthe Located relationship,
and their corresponding dependency paths:
|
x
i
∩
y
i
|
1. '
his
actions in
Brcko
'(
his
→
actions
←
in
←
Brcko
).
2. '
his
arrival in
Beijing
'(
his
→
arrival
←
in
←
Beijing
).
Their representationas a sequence of setsofword classes isgivenby:
1.
x
=[
x
1
x
2
x
3
x
4
x
5
x
6
x
7
], where
x
1
=
{
his, PRP, Person
}
,
x
2
=
{→}
,
x
3
=
{
actions, NNS,Noun
}
,
x
4
=
{←}
,
x
5
=
{
in,IN
}
,
x
6
=
{←}
,
x
7
=
{
Brcko,
NNP,Noun, Location
}
2.
y
=[
y
1
y
2
y
3
y
4
y
5
y
6
y
7
], where
y
1
=
{
his, PRP, Person
}
,
y
2
=
{→}
,
y
3
=
{
arrival, NN, Noun
}
,
y
4
=
{←}
,
y
5
=
{
in,IN
}
,
y
6
=
{←}
,
y
7
=
{
Beijing, NNP,
Noun, Location
}
Based onthe formulafrom Equation3.4, the kernel iscomputedas
K
(
x
,
y
)=
3
×
1
×
1
×
1
×
2
×
1
×
3 = 18.
Search WWH ::
Custom Search