System and method for text tagging and segmentation using a generative/discriminative hybrid hidden markov model
View Patent ↗A method for sequence tagging medical patient records includes providing a labeled corpus of sentences taken from a set of medical records, initializing generative parameters θ and discriminative parameters {tilde over (θ)}, providing a functional LL−C×Penalty, where LL is a log-likelihood function LL = log p ( θ , θ ~ ) + ∏ l = 1 M [ log p ( X l , Y l | θ ~ ) - log p ( X l | θ ~ ) ] + ∏ l = 1 M log p ( X l | θ ) , Penalty = ∑ y ∈ V Y ( em y 2 + tr y 2 + e m ~ y 2 + t r ~ y 2 ) , where em y =1−Σ ∀x i εV X p(x i |y), e{tilde over (m)} y =1−Σ ∀x i εV X {tilde over (p)}(x i |y) are emission probability constraints, tr y =1−Σ ∀y i εV Y p(y i |y), t{tilde over (r)} y =1−Σ ∀y i εV Y {tilde over (p)}(y i |y) are transition probability constraints, and extracting gradients of LL−C×Penalty with respect to the transition and emission probabilities and solving θ k *,{tilde over (θ)} k *that maximize LL−C×Penalty, initializing a new iteration with θ k *,{tilde over (θ)} k * and incrementing C and repeating until solutions have converged, where parameters θ,{tilde over (θ)} are the probabilities that a new sentence X′ is labeled as Y′.
1. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform a method for sequence tagging medical patient records, the method comprising the steps of:
providing a labeled corpus D={X l ,Y l } l=1 M of M sentences taken from a set of medical records, wherein X=x i . . . x n is a sentence, x j is a word at position j from a finite vocabulary V x , each word x j having a label y j from a finite vocabulary V Y , and Y is a collection of labels for the sentence X, wherein said labels are sequence tags for sentence X;
initializing generative parameters θ and discriminative parameters {tilde over (θ)}, wherein θ={p(x i |y j ), p(y i |y j ), ∀y i , y j εV Y , ∀x i εV X } are generative parameters and {tilde over (θ)}={{tilde over (p)}(x i |y j ), {tilde over (p)}(y i |y j ), ∀y i , y j εV Y , ∀x i εV X } are discriminative parameters, and p(x i |y j ), {tilde over (p)}(x i |y j ) are emission probabilities and p(y i |y j ), {tilde over (p)}(y i |y j ) are transition probabilities; and
finding parameters θ,{tilde over (θ)} that maximize a functional LL−C×Penalty, wherein LL is a log-likelihood function
LL
=
log
p
(
θ
,
θ
~
)
+
∏
l
=
1
M
[
log
p
(
X
l
,
Y
l
❘
θ
~
)
-
log
p
(
X
l
❘
θ
~
)
]
+
∏
l
=
1
M
log
p
(
X
l
❘
θ
)
,
wherein
p
(
θ
,
θ
~
)
∝
p
(
θ
)
p
(
θ
~
)
1
σ
exp
(
-
θ
-
θ
~
2
2
σ
2
)
is a prior wherein σ is a tradeoff parameter that balances contributions of the generative parameters and discriminative parameters,
p
(
X
l
,
Y
l
|
θ
~
)
=
∏
t
=
1
n
p
(
x
t
l
|
y
t
l
,
θ
~
)
p
(
y
t
l
|
y
t
-
1
l
,
θ
~
)
,
and p(X L |{tilde over (θ)}), p(X l |θ) are calculated as
p
(
X
|
θ
)
=
∑
y
α
t
(
y
|
θ
)
β
t
(
y
|
θ
)
,
wherein
α
t
(
y
t
)
=
p
(
x
1
,
…
,
x
t
,
y
t
)
=
p
(
x
t
|
y
t
)
∑
y
p
(
y
t
|
y
)
α
t
-
1
(
y
)
,
with α 0 =1, and
β
t
(
y
t
)
=
p
(
x
t
+
1
,
…
,
x
n
|
y
t
)
=
∑
y
β
t
+
1
(
y
)
p
(
x
t
+
1
|
y
)
p
(
y
|
y
t
)
with β t =1, Penalty is a penalty function defined as
∑
y
∈
V
Y
(
em
y
2
+
tr
y
2
+
e
m
~
y
2
+
t
r
~
y
2
)
,
where
em
y
=
1
-
∑
∀
x
i
∈
V
X
p
(
x
i
❘
y
)
,
e
m
~
y
=
1
-
∑
∀
x
i
∈
V
X
p
~
(
x
i
❘
y
)
are emission probability constraints for state y and
tr
y
=
1
-
∑
∀
y
i
∈
V
Y
p
(
y
i
❘
y
)
,
t
r
~
y
=
1
-
∑
∀
y
i
∈
V
Y
p
~
(
y
i
❘
y
)
are transition probability constraints for state, and C is a constant, wherein parameters θ,{tilde over (θ)} are the probabilities that a new sentence X′ is labeled as Y′.
2. The computer readable program storage device of claim 1 , wherein initializing parameters θ and {tilde over (θ)} comprises finding θ,{tilde over (θ)} that maximize
∏
l
=
1
M
p
(
X
l
,
Y
l
❘
θ
)
,
∏
l
=
1
M
p
(
X
l
,
Y
l
❘
θ
~
)
.
3. The computer readable program storage device of claim 1 , wherein maximizing LL−C×Penalty comprises fixing C, extracting gradients of LL−C×Penalty with respect to said transition and emission probabilities, solving for θ k *,{tilde over (θ)} k *, initializing a new iteration with θ k *,{tilde over (θ)} k * and incrementing C, and repeating said steps of extracting gradients and initializing a new iteration until solutions θ k *,{tilde over (θ)} k * have converged, or until a maximum number of iterations have been executed.
4. The computer readable program storage device of claim 1 , wherein said sequence tagging comprises one of part-of-speech tagging, shallow parsing, and named entity recognition.
5. The computer readable program storage device of claim 2 , the method further comprising maximizing only the conditional likelihoods p(X l |{tilde over (θ)}), p(X l |θ) of functional LL−C×Penalty for a predetermined number of iterations, prior to maximizing LL−C×Penalty.
6. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for sequence tagging medical patient records, the method comprising the steps of:
providing a labeled corpus D={X l ,Y l } l=1 M of M sentences taken from a set of medical records, wherein X=x i . . . x n is a sentence, x j is a word at position j from a finite vocabulary V x , each word x j having a label y j from a finite vocabulary V Y , and Y is a collection of labels for the sentence X, wherein said labels are sequence tags for sentence X;
initializing generative parameters θ and discriminative parameters {tilde over (θ)}, wherein θ={p(x i |y j ), p(y i |y j ), ∀y i , y j εV Y , ∀x i εV x } are generative parameters and {tilde over (θ)}={{tilde over (p)}(x i |y j ), {tilde over (p)}(y i |y j ), ∀y i , y j εV Y , ∀x i εV X } are discriminative parameters, and p(x i |y j ), {tilde over (p)}(x i |y j ) are emission probabilities and p(y i |y j ), {tilde over (p)}(y i |y j ) are transition probabilities;
providing a functional LL−C×Penalty, wherein LL is a log-likelihood function
LL
=
log
p
(
θ
,
θ
~
)
+
∏
l
=
1
M
[
log
p
(
X
l
,
Y
l
|
θ
~
)
-
log
p
(
X
l
|
θ
~
)
]
+
∏
l
=
1
M
log
p
(
X
l
|
θ
)
,
Penalty
=
∑
y
∈
V
Y
(
em
y
2
+
tr
y
2
+
e
m
~
y
2
+
t
r
~
y
2
)
,
wherein
em
y
=
1
-
∑
∀
x
i
∈
V
X
p
(
x
i
❘
y
)
,
e
m
~
y
=
1
-
∑
∀
x
i
∈
V
X
p
~
(
x
i
❘
y
)
are emission probability constraints for state y,
tr
y
=
1
-
∑
∀
y
i
∈
V
Y
p
(
y
i
❘
y
)
,
t
r
~
y
=
1
-
∑
∀
y
i
∈
V
Y
p
~
(
y
i
❘
y
)
are transition probability constraints for state y, and C is a constant; and
extracting gradients of LL−C×Penalty with respect to said transition and emission probabilities and solving θ k *,{tilde over (θ)} k * that maximize LL−C×Penalty,
wherein parameters θ,{tilde over (θ)} are the probabilities that a new sentence X′ is labeled as Y′.
7. The computer readable program storage device of claim 6 , wherein p(X L |{tilde over (θ)}), p(X l |θ) are calculated as
p
(
X
❘
θ
)
=
∑
y
α
t
(
y
❘
θ
)
β
t
(
y
❘
θ
)
,
wherein
α
t
(
y
t
)
=
p
(
x
1
,
…
,
x
t
,
y
t
)
=
p
(
x
t
|
y
t
)
∑
y
p
(
y
t
|
y
)
α
t
-
1
(
y
)
,
with α 0 =1, and
β
t
(
y
t
)
=
p
(
x
t
+
1
,
…
,
x
n
|
y
t
)
=
∑
y
β
t
+
1
(
y
)
p
(
x
t
+
1
|
y
)
p
(
y
|
y
t
)
with β t =1.
8. The computer readable program storage device of claim 6 , the method further comprising initializing a new iteration with θ k *,{tilde over (θ)} k * and incrementing C; and repeating said steps of extracting gradients and initializing a new iteration until solutions θ k *,{tilde over (θ)} k * have converged, or until a maximum number of iterations have been executed.
9. The computer readable program storage device of claim 6 , wherein
p
(
θ
,
θ
~
)
∝
p
(
θ
)
p
(
θ
~
)
1
σ
exp
(
-
θ
-
θ
~
2
2
σ
2
)
is a prior wherein σ is a tradeoff parameter that balances contributions of the generative parameters and discriminative parameters.
10. The computer readable program storage device of claim 6 , wherein
p
(
X
l
,
Y
l
|
θ
~
)
=
∏
t
=
1
n
p
(
x
t
l
|
y
t
l
,
θ
~
)
p
(
y
t
l
|
y
t
-
1
l
,
θ
~
)
.
11. The computer readable program storage device of claim 6 , wherein p(X L |{tilde over (θ)}), p(X l |θ) are calculated as
p
(
X
|
θ
)
=
∑
y
α
t
(
y
|
θ
)
β
t
(
y
|
θ
)
,
wherein
α
t
(
y
t
)
=
p
(
x
1
,
…
,
x
t
,
y
t
)
=
p
(
x
t
|
y
t
)
∑
y
p
(
y
t
|
y
)
α
t
-
1
(
y
)
,
with α 0 =1, and
β
t
(
y
t
)
=
p
(
x
t
+
1
,
…
,
x
n
|
y
t
)
=
∑
y
β
t
+
1
(
y
)
p
(
x
t
+
1
|
y
)
p
(
y
|
y
t
)
with β t =1.