Information Technology Reference
In-Depth Information
3.2
Features
To describe the feature representation of elements from a free group
F
(
X
)we
need the following
Definition 1.
∈
F
(
X
)
is a weighted non-oriented graph, where the set of vertices
V
is equal to the
set
X
±
1
,andfor
x
i
,x
j
∈
Labelled Whitehead Graph
WG
(
v
)=(
V, E
)
of an element
v
E
if the subword
x
i
x
−
1
X
±
1
there is an edge
(
x
i
,x
j
)
∈
j
(or
x
j
x
−
i
)occursintheword
v
viewed as a cyclic word. Every edge
(
x
i
,x
j
)
is
assigned a weight
l
ij
which is the number of times the subwords
x
i
x
−
1
j
and
x
j
x
−
1
i
occur in
v
.
Whitehead Graph is one of the main tools in exploring automorphic proper-
ties of elements in a free group [4, 8].
Now, let
w
F
(
X
) be a cyclically reduced word. We define features of
element
w
as follows. Let
l
(
w
) be a vector of edge weights in the Whitehead
Graph
WG
(
w
) with respect to a fixed order. We define a feature vector
f
(
w
)by
∈
1
f
(
w
)=
l
(
w
)
.
|
w
|
This is the basic feature vector in all our considerations.
3.3
Decision Rule
Below we give a brief description of the classification rule based on Support
Vector Machine.
Let
D
=
,
x
i
=
f
(
w
i
) be the set of feature vectors with the corresponding labels
y
1
,...,y
N
,
where
{
w
1
,...,w
N
}
,
w
∈
F
(
X
) be a training set and
D
=
{
x
1
,...,
x
N
}
y
i
=
+1
,
if
P
(
w
i
)=1;
−
1
,
otherwise
.
Definition 2.
Themarginofanexample
(
x
i
,y
i
)
with respect to a hyperplane
(
w
,b
)
defined as the quantity
γ
i
=
y
i
(
w
·
x
+
b
)
.
Note that
γ
i
>
0 corresponds to the correct classification of (
x
i
,y
i
).
Let
γ
+
(
γ
−
) be the smallest margin among all positive (negative) points.
Define the margin of separation
γ
=
γ
+
+
γ
−
.
A Support Vector Machine (SVM) is a statistical classifier that attempts
to construct a decision hyperplane (
w
,b
) in such a way that the margin of
separation
γ
between positive and negative examples is maximized [9, 10].
Search WWH ::
Custom Search