# US 2012/0084235 A1 · Structured prediction model learning apparatus, method, program, and recording medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084235 A1
- Document ID: US20120084235A1
- Status: Published application
- Kind: A1
- Application number: 12/895,014
- Filed: 2010-09-30
- Published: 2012-04-05
- Earliest claimed: 2010-09-30
- Assignees: Massachusetts Institute of Technology; Nippon Telegraph and Telephone Corporation
- Inventors: Jun Suzuki; Michael J. Collins
- Web page: https://patentgrep.com/patent/US20120084235A1

## CPC

- G06N 20/00: Machine learning
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A structured prediction model learning apparatus, method, program, and recording medium maintain prediction performance with a smaller amount of memory. An auxiliary model is introduced by defining the auxiliary model parameter set θ(k) with a log-linear model. A set Θ of auxiliary model parameter sets which minimizes the Bregman divergence between the auxiliary model and a reference function indicating the degree of pseudo accuracy is estimated by using unsupervised data. A base-model parameter set λ which minimizes an empirical risk function defined beforehand is estimated by using supervised data and the set Θ of auxiliary model parameter sets.

## Claims

### Claim 1

A structured prediction model learning apparatus for learning a structured prediction model used to predict an output structure y corresponding to an input structure x, by using supervised data DL and unsupervised data DU, the structured prediction model learning apparatus comprising:
an output candidate graph generator generating a supervised data output candidate graph for the supervised data and an unsupervised data output candidate graph for the unsupervised data, by using a set of definition data for generating output candidates identified by a structured prediction problem;
a feature vector generator extracting features from the supervised data output candidate graph and the unsupervised data output candidate graph by using a feature extraction template, generating a D-dimensional base-model feature vector fx,y corresponding to a set of the features extracted from the supervised data output candidate graph, dividing a set of the features extracted from the unsupervised data output candidate graph into K subsets, and generating a Dk-dimensional auxiliary model feature vector g(k)x,y corresponding to features included in a subset k of the K subsets, where K is a natural number and kε{1, 2, . . . , K};
a parameter generator generating a base-model parameter set λ which includes a first parameter set w formed of D first parameters in one-to-one correspondence with D elements of the base-model feature vector fx,y, generating an auxiliary model parameter set θ(k) formed of Dk auxiliary model parameters in one-to-one correspondence with Dk elements of the auxiliary model feature vector g(k)x,y, and to generate a set Θ={θ(1), θ(2), . . . , θ(K)} of auxiliary model parameter sets, formed of K auxiliary model parameter sets θ(k);
an auxiliary model parameter estimating unit estimating a set Θ of auxiliary model parameter sets which minimizes the Bregman divergence having a regularization term obtained from the auxiliary model parameter set θ(k), between each auxiliary model qk and a reference function {tilde over (r)}(x, y) which is a nonnegative function and indicates the degree of pseudo accuracy of the output structure y corresponding to the input structure x, by using the regularization term and the unsupervised data DU, where the auxiliary model qk is obtained by defining the auxiliary model parameter set θ(k) with a log-linear model; and
a base-model parameter estimating unit estimating a base-model parameter set λ which minimizes an empirical risk function defined beforehand, by using the supervised data DL and the set Θ of auxiliary model parameter sets, where the base-model parameter set λ includes a second parameter set v={v1, v2, . . . , vK} formed of K second parameters in one-to-one correspondence with K auxiliary models.

### Claim 2 (depends on 1)

The structured prediction model learning apparatus according to claim 1, further comprising:
a convergence determination unit determining whether the values of the base-model parameter set λ and the set Θ of auxiliary model parameter sets have converged; and
a parameter integrating unit integrating the converged base-model parameter set λ and the converged set Θ of auxiliary model parameter sets;
wherein, in a case where the convergence determination unit determines that the values of the base-model parameter set λ and the set Θ of auxiliary model parameter sets have not converged, the auxiliary model parameter estimating unit repeatedly estimates the set Θ of auxiliary model parameter sets, and the base-model parameter estimating unit repeatedly estimates the base-model parameter set λ; and
the reference function {tilde over (r)} is a base-model P used immediately before the current repetition of model parameter set estimation.

### Claim 3 (depends on 1)

The structured prediction model learning apparatus according to claim 1, wherein the base-model parameter estimating unit uses a regularization term Ω(λ) obtained from the base-model parameter set λ to obtain the empirical risk function as the following empirical risk function having a regularization term
L(λ|Θ,DL)=R(λ|Θ,DL)+CLΩ(λ)
where CL is a hyper parameter;
in a case where a negative log likelihood is used as the empirical risk function, the following is used
R

(
λ

Θ
,
D
l
)
=
-
∑
(
x
,
y
)
∈
D
L

log

exp

[
d

(
x
,
y
;
λ
,
Θ
)
]
∑
y

exp

[
d

(
x
,
y
;
λ
,
Θ
)
]
;
and
in a case where a base-model parameter set λ which minimizes L(λ|Θ, DL) is estimated based on margin maximization in a linear identification model, the following are used
R

(
λ

Θ
,
D
L
)
=
∑
(
x
,
y
)
∈
D
L

max

[
0
,
E

(
y
,
y
^
)
-
d

(
x
,
y
;
λ
,
Θ
)
+
d

(
x
,
y
^
;
λ
,
Θ
)
]

y
^
=
arg

max
y
′
∈
Y

(
x
)

\

y

d

(
x
,
y
′
;
λ
,
Θ
)
+
E

(
y
,
y
′
)
.

### Claim 4 (depends on 1)

The structured prediction model learning apparatus according to claim 1, wherein the auxiliary model parameter estimating unit uses the auxiliary model parameter set θ(k) to obtain an L1 norm regularization term |θ(k)|1 obtains the Bregman divergence having the regularization term as the following empirical generalized relative entropy having a regularization term
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

G
^
D
U

(
r
~
||
q
k
)
where Cu is a hyper parameter, and estimates a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy having the regularization term.

### Claim 5 (depends on 4)

The structured prediction model learning apparatus according to claim 4, wherein the auxiliary model parameter estimating unit obtains the empirical generalized relative entropy having the regularization term as one of the following, where the conditional probability of outputting the output structure y in a case where the input structure x is given is q1k(y|x; θ(k)) and the odds of q1k are q′1k,
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
y
)
||
q
k
1

(
y

x
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
y
)
||
q
k
′1

(
y

x
;
θ
(
k
)
)
)
;
and
the auxiliary model parameter estimating unit estimates a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy.

### Claim 6 (depends on 4)

The structured prediction model learning apparatus according to claim 4, wherein the auxiliary model parameter estimating unit obtains the empirical generalized relative entropy having the regularization term as one of the following, where the conditional probability of outputting a local structure z in the output structure y in a case where the input structure x is given is q2k(z|x; θ(k)) and the odds of q2k are q′2k,
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
2

(
z

x
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′2

(
z

x
;
θ
(
k
)
)
)
;
and
the auxiliary model parameter estimating unit estimates a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy.

### Claim 7 (depends on 4)

The structured prediction model learning apparatus according to claim 4, wherein the auxiliary model parameter estimating unit obtains the empirical generalized relative entropy having the regularization term as one of the following, where the conditional probability of outputting a local structure z having a feature n in the output structure y in a case where the input structure x is given is q3k(z|x, n; θ(k)) and the odds of q3k are q′3k,
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′3

(
z

x
,
n
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′3

(
z

x
,
n
;
θ
(
k
)
)
)
;
and
the auxiliary model parameter estimating unit estimates a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy.

### Claim 8

A structured prediction model learning method for learning a structured prediction model used to predict an output structure y corresponding to an input structure x, by using supervised data DL and unsupervised data DU, the structured prediction model learning method comprising:
an output candidate graph generating step of generating a supervised data output candidate graph for the supervised data and an unsupervised data output candidate graph for the unsupervised data, by using a set of definition data for generating output candidates identified by a structured prediction problem;
a feature vector generating step of extracting features from the supervised data output candidate graph and the unsupervised data output candidate graph by using a feature extraction template, generating a D-dimensional base-model feature vector fx,y corresponding to a set of the features extracted from the supervised data output candidate graph, dividing a set of the features extracted from the unsupervised data output candidate graph into K subsets, and generating a Dk-dimensional auxiliary model feature vector g(k)x,y corresponding to features included in a subset k of the K subsets, where K is a natural number and kε{1, 2, . . . , K};
a parameter generating step of generating a base-model parameter set λ which includes a first parameter set w formed of D first parameters in one-to-one correspondence with D elements of the base-model feature vector fx,y, generating an auxiliary model parameter set θ(k) formed of Dk auxiliary model parameters in one-to-one correspondence with Dk elements of the auxiliary model feature vector g(k)x,y, and generating a set Θ={θ(1), θ(2), . . . , θ(K)} of auxiliary model parameter sets, formed of K auxiliary model parameter sets θ(k);
an auxiliary model parameter estimating step of estimating a set Θ of auxiliary model parameter sets which minimizes the Bregman divergence having a regularization term obtained from the auxiliary model parameter set θ(k), between each auxiliary model qk and a reference function {tilde over (r)}(x, y) which is a nonnegative function and indicates the degree of pseudo accuracy of the output structure y corresponding to the input structure x, by using the regularization term and the unsupervised data DU, where the auxiliary model qk is obtained by defining the auxiliary model parameter set θ(k) with a log-linear model; and
a base-model parameter estimating step of estimating a base-model parameter set λ which minimizes an empirical risk function defined beforehand, by using the supervised data DL and the set Θ of auxiliary model parameter sets, where the base-model parameter set λ includes a second parameter set v={v1, v2, . . . , vK} formed of K second parameters in one-to-one correspondence with K auxiliary models.

### Claim 9 (depends on 8)

The structured prediction model learning method according to claim 8, further comprising:
a convergence determination step of determining whether the values of the base-model parameter set λ and the set Θ of auxiliary model parameter sets have converged; and
a parameter integrating step of integrating the converged base-model parameter set λ and the converged set Θ of auxiliary model parameter sets;
wherein, in a case where it is determined in the convergence determination step that the values of the base-model parameter set λ and the set Θ of auxiliary model parameter sets have not converged, the set Θ of auxiliary model parameter sets is repeatedly estimated in the auxiliary model parameter estimating step and the base-model parameter set λ is repeatedly estimated in the base-model parameter estimating step; and
the reference function {tilde over (r)} is a base-model P used immediately before the current repetition of model parameter set estimation.

### Claim 10 (depends on 8)

The structured prediction model learning method according to claim 8, wherein, in the base-model parameter estimating step, a regularization term Ω(λ) obtained from the base-model parameter set λ is used to obtain the empirical risk function as the following empirical risk function having a regularization term
L(λ|Θ,DL)=R(λ|Θ,DL)+CLΩ(λ)
where CL is a hyper parameter;
in a case where a negative log likelihood is used as the empirical risk function, the following is used
R

(
λ

Θ
,
D
l
)
=
-
∑
(
x
,
y
)
∈
D
L

log

exp

[
d

(
x
,
y
;
λ
,
Θ
)
]
∑
y

exp

[
d

(
x
,
y
;
λ
,
Θ
)
]
;
and
in a case where a base-model parameter set λ which minimizes L(λ|Θ, DL) is estimated based on margin maximization in a linear identification model, the following are used
R

(
λ

Θ
,
D
L
)
=
∑
(
x
,
y
)
∈
D
L

max

[
0
,
E

(
y
,
y
^
)
-
d

(
x
,
y
;
λ
,
Θ
)
+
d

(
x
,
y
^
;
λ
,
Θ
)
]

y
^
=
arg

max
y
′
∈
Y

(
x
)

\

y

d

(
x
,
y
′
;
λ
,
Θ
)
+
E

(
y
,
y
′
)
.

### Claim 11 (depends on 8)

The structured prediction model learning method according to claim 8, wherein, in the auxiliary model parameter estimating step, the auxiliary model parameter set θ(k) is used to obtain an L1 norm regularization term |θ(k)|1 the Bregman divergence having the regularization term is obtained as the following empirical generalized relative entropy having a regularization term
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

G
^
D
U

(
r
~
||
q
k
)
where CU is a hyper parameter, and a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy having the regularization term is estimated.

### Claim 12 (depends on 11)

The structured prediction model learning method according to claim 11, wherein, in the auxiliary model parameter estimating step, the empirical generalized relative entropy having the regularization term is obtained as one of the following, where the conditional probability of outputting the output structure y in a case where the input structure x is given is q1k(y|x; θ(k)) and the odds of q1k are q′1k,
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
y
)
||
q
k
1

(
y

x
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
y
)
||
q
k
′1

(
y

x
;
θ
(
k
)
)
)
;
and
a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy is estimated.

### Claim 13 (depends on 11)

The structured prediction model learning method according to claim 11, wherein, in the auxiliary model parameter estimating step, the empirical generalized relative entropy having the regularization term is obtained as one of the following, where the conditional probability of outputting a local structure z in the output structure y in a case where the input structure x is given is q2k(z|x; θ(k)) and the odds of q2k are q′2k,
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
2

(
z

x
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′2

(
z

x
;
θ
(
k
)
)
)
;
and
a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy is estimated.

### Claim 14 (depends on 11)

The structured prediction model learning method according to claim 11, wherein, in the auxiliary model parameter estimating step, the empirical generalized relative entropy having the regularization term is obtained as one of the following, where the conditional probability of outputting a local structure z having a feature n in the output structure y in a case where the input structure x is given is q3k(z|x, n; θ(k)) and the odds of q3k are q′3K
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′3

(
z

x
,
n
;
θ
(
k
)
)
)
and
U

(
Θ

D
U
)
=
C
U

∑
k


θ
(
k
)

1
+
∑
k

K
^
D
U

(
r
~

(
x
,
z
)
||
q
k
′3

(
z

x
,
n
;
θ
(
k
)
)
)
;
and
a set Θ of auxiliary model parameter sets which minimizes the empirical generalized relative entropy is estimated.

### Claim 15 (depends on 1)

A program that makes a computer function as the structured prediction model learning apparatus according to claim 1.

### Claim 16 (depends on 1)

A computer-readable recording medium that records a program that makes a computer function as the structured prediction model learning apparatus according to claim 1.
