US8938386B2ActiveUtilityPatentIndex 78
Classification-based redaction in natural language text
Est. expiryMar 15, 2031(~4.7 yrs left)· nominal 20-yr term from priority
G06F 40/30G06F 40/10G06F 40/279G06F 17/2785G06F 17/21G06F 17/2765
78
PatentIndex Score
11
Cited by
47
References
23
Claims
Abstract
When redacting natural language text, a classifier is used to provide a sensitive concept model according to features in natural language text and in which the various classes employed are sensitive concepts reflected in the natural language text. Similarly, the classifier is used to provide an utility concepts model based on utility concepts. Based on these models, and for one or more identified sensitive concept and identified utility concept, at least one feature in the natural language text is identified that implicates the at least one identified sensitive topic more than the at least one identified utility concept. At least some of the features thus identified may be perturbed such that the modified natural language text may be provided as at least one redacted document. In this manner, features are perturbed to maximize classification error for sensitive concepts while simultaneously minimizing classification error in the utility concepts.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A method for redacting natural language text, the method comprising:
receiving, by a processing device and via a user input device operatively connected to the processing device, one or more user inputs indicating sensitive concepts and utility concepts based on a user interface that includes a visual representation of a plurality of concepts in the natural language text,
the plurality of concepts including the sensitive concepts and the utility concepts, and
the natural language text being in an electronic format;
determining, by the processing device, the sensitive concepts based on the one or more user inputs;
determining, by the processing device, the utility concepts based on the one or more user inputs;
determining, by the processing device and for at least one feature in the natural language text, a sensitive concepts implication factor based on class-conditional probabilities of the at least one feature according to the sensitive concepts;
determining, by the processing device and for the at least one feature, a utility concepts implication factor based on class-conditional probabilities of the at least one feature according to the utility concepts;
determining, by the processing device and for the at least one feature, a feature score based on a difference between the sensitive concepts implication factor and the utility concepts implication factor;
identifying, by the processing device and to obtain identified features, the at least one feature based on the feature score satisfying a threshold,
the at least one feature implicating at least one identified sensitive concept, of the sensitive concepts, more than at least one identified utility concept of the utility concepts; and
perturbing, by the processing device, at least some of the identified features in at least a portion of the natural language text.
2. The method of claim 1 , further comprising:
providing, by the processing device and via a display operatively connected to the processing device, the user interface.
3. The method of claim 1 , wherein the feature score is determined according to at least one mathematical function, where the at least one mathematical function is at least one of: ScoreLO(x i ), ScoreOR(x i ), ScoreFL(x i ), or ScoreIG(x i ),
where:
ScoreLO
(
x
i
)
=
1
S
∑
s
∈
S
LogOdds
(
s
,
x
i
)
-
1
U
∑
u
∈
U
LogOdds
(
u
,
x
i
)
,
1
S
∑
s
∈
S
LogOdds
(
s
,
x
i
)
corresponding to the sensitive concepts implication factor,
1
U
∑
u
∈
U
LogOdds
(
u
,
x
i
)
corresponding to the utility concepts implication factor, and
LogOdds
(
y
,
x
i
)
=
log
log
(
P
(
x
i
y
)
)
log
(
P
(
x
i
Y
_
)
)
,
ScoreOR
(
x
i
)
=
1
S
∑
s
∈
S
OddsRatio
(
s
,
x
i
)
-
1
U
∑
u
∈
U
OddsRatio
(
u
,
x
i
)
,
1
S
∑
s
∈
S
OddsRatio
(
s
,
x
i
)
corresponding to the sensitive concepts implication factor,
1
U
∑
u
∈
U
OddsRatio
(
u
,
x
i
)
corresponding to the utility concepts implication factor, and
OddsRatio
(
y
,
x
i
)
=
log
P
(
x
i
y
)
(
1
-
P
(
x
i
Y
_
)
)
(
1
-
P
(
x
i
y
)
)
P
(
x
i
Y
_
)
,
ScoreFL
(
x
i
)
=
∑
s
∈
S
FreqLogP
(
s
,
x
i
)
S
-
∑
u
∈
U
FrqLogP
(
u
,
x
i
)
U
∑
s
∈
S
FreqLogP
(
s
,
x
i
)
S
corresponding to the sensitive concepts implication factor
∑
u
∈
U
FreqLogP
(
u
,
x
i
)
U
corresponding to the utility concepts implication factor, and
FreqLog
(
y
,
x
i
)
=
freq
(
x
i
)
×
log
P
(
x
,
y
)
P
(
x
i
,
Y
_
)
,
ScoreIG
(
x
i
)
=
InfoGain
(
S
,
x
i
)
-
InfoGain
(
U
,
x
i
)
,
InfoGain
(
S
,
x
i
)
corresponding to the sensitive concepts implication factor,
InfoGain(U, x i ) corresponding to the utility concepts implication factor, and
InfoGain
(
Y
,
x
i
)
=
-
∑
y
∈
Y
P
(
y
)
log
P
(
y
)
+
P
(
x
i
)
∑
y
∈
Y
P
(
y
❘
x
i
)
log
P
(
y
❘
x
i
)
+
P
(
x
_
i
)
∑
y
∈
Y
P
(
y
❘
x
_
i
)
log
P
(
y
❘
x
i
)
,
and
where:
x i is an i'th feature of the natural language text,
S is a set constituting the at least one sensitive concept,
s is a sensitive concept,
U is a set constituting the at least one utility concept,
u is a utility concept,
Y is a dummy variable standing in for either S or U, and
Y =Y\y for some yεY.
4. The method of claim 1 , wherein identifying the at least one feature comprises:
determining, by the processing device and for a document forming a part of the natural language text, selected features of the document that numerically optimize a constrained objective function established to ensure that the selected features of the document implicate at least one identified sensitive concept for the document more than at least one utility identified concept for the document; and
providing, by the processing device, the selected features as the identified features.
5. The method of claim 4 ,
where the constrained objective function is:
min
f
(
x
^
)
=
-
∑
i
Gain
(
x
i
,
s
,
U
x
)
x
^
i
such
that
:
0
≤
x
^
i
≤
freq
(
x
i
)
,
∑
i
(
log
(
P
(
x
i
|
s
)
)
-
1
)
x
^
i
≤
0
,
∑
i
(
-
log
(
P
(
x
i
|
u
)
)
-
1
)
x
^
i
≤
0
,
where
:
Gain
(
x
i
,
s
,
U
x
)
=
log
(
P
(
x
i
|
s
)
)
-
μ
·
log
(
∑
u
∈
U
x
P
(
x
i
|
u
)
)
,
and
where:
x i is an i'th feature of the document,
s is a sensitive concept of the document,
U x is a set constituting at least one utility concept of the document,
u is a utility concept of the document, and
μ is a weighting parameter.
6. The method of claim 1 , further comprising:
determining, by the processing device and for a document forming a part of the natural language text, selected features of the document that numerically optimize a constrained objective function established to ensure that the selected features of the document implicate a sensitive concept, of the sensitive concepts, for the document more than at least k−1 other sensitive concepts, of the sensitive concepts, for the document,
the constrained objective function being based on class-conditional probabilities of the selected features according to the at least one utility concept; and
providing, by the processing device, the selected features as part of the identified features.
7. The method of claim 6 ,
where the constrained objective function is:
min
f
(
x
^
)
=
-
∑
i
Utility
(
x
i
,
u
)
x
^
i
such
that
:
0
≤
x
^
i
≤
freq
(
x
i
)
,
∑
i
(
log
(
P
(
x
i
|
s
)
)
x
^
i
)
≤
∑
i
log
(
P
(
x
i
|
s
_
1
)
)
x
^
i
,
⋮
∑
i
(
log
(
P
(
x
i
|
s
)
)
x
^
i
)
≤
∑
i
log
(
P
(
x
i
|
s
_
k
-
1
)
)
x
^
i
where
:
Utility
(
x
i
,
u
)
=
(
1
-
P
(
u
)
)
log
(
P
(
x
i
|
u
)
)
-
∑
u
_
∈
U
\
u
P
(
u
_
)
P
(
x
i
|
u
_
)
,
and
where:
x i is an i'th feature of the document,
s is a sensitive concept of the document,
U is a set constituting at least one utility concept of the document,
u is a utility concept of the document, and
s = s 1 , . . . , s k-1 εS are a sequence of k−1 sensitive concepts obtained by ranking all s εS\s by P( s )P(x| s ).
8. The method of claim 1 , where perturbing the at least some of the identified features comprises:
suppressing the at least some of the identified features.
9. The method of claim 1 , where perturbing the at least some of the identified features comprises:
generalizing the at least some of the identified features.
10. The method of claim 1 , further comprising:
providing, by the processing device, the portion of the natural language text in which the at least some of the identified features have been perturbed as at least one redacted document.
11. An apparatus for redacting natural language text comprising a plurality of features comprising:
a storage;
a processor to:
receive, via a user input device operatively connected to the processor, one or more user inputs indicating sensitive concepts and utility concepts based on a user interface that includes a visual representation of a plurality of concepts in natural language text,
the plurality of concepts including the sensitive concepts and the utility concepts, and
the natural language text being in an electronic format;
determine the sensitive concepts based on the one or more user inputs;
determine the utility concepts based on the one or more user inputs;
determine, for at least one feature in the natural language text, a sensitive concepts implication factor based on class-conditional probabilities of the at least one feature according to the sensitive concepts;
determine, for the at least one feature in the natural language text, a utility concepts implication factor based on class-conditional probabilities of the at least one feature according to the utility concepts;
determine, for the at least one feature in the natural language text, a feature score based on a difference between the sensitive concepts implication factor and the utility concepts implication factor;
identify features of the natural language text based on the feature score satisfying a threshold,
the identified features including the at least one feature, and
the at least one feature implicating at least one identified sensitive concept, of the sensitive concepts, more than at least one utility concept of the utility concepts; and
perturb at least some of the identified features in at least a portion of the natural language text.
12. The apparatus of claim 11 , where the processor is further to:
provide, via a display operatively connected to the processor, the user interface.
13. The apparatus of claim 11 , where the feature score is determined according to at least one mathematical function, where the at least one mathematical function is at least one of: ScoreLO(x i ), ScoreOR(x i ), ScoreFL(x i ), or ScoreIG(x i ),
where
:
ScoreLO
(
x
i
)
=
1
S
∑
s
∈
S
LogOdds
(
s
,
x
i
)
-
1
U
∑
u
∈
U
LogOdds
(
u
,
x
i
)
,
LogOdds
(
y
,
x
i
)
=
log
log
(
P
(
x
i
|
y
)
)
log
(
P
(
x
i
|
Y
_
)
)
,
ScoreOR
(
x
i
)
=
1
S
∑
s
∈
S
OddsRatio
(
s
,
x
i
)
-
1
U
∑
u
∈
U
OddsRatio
(
u
,
x
i
)
,
OddsRatio
(
y
,
x
i
)
=
log
P
(
x
i
|
y
)
(
1
-
P
(
x
i
|
Y
_
)
)
(
1
-
P
(
x
i
|
y
)
)
P
(
x
i
|
Y
_
)
,
ScoreFL
(
x
i
)
=
∑
s
∈
S
FreqLogP
(
s
,
x
i
)
S
-
∑
u
∈
U
FreqLogP
(
u
,
x
i
)
U
,
FreqLogP
(
y
,
x
i
)
=
freq
(
x
i
)
×
log
P
(
x
i
|
y
)
P
(
x
i
|
Y
_
)
,
ScoreIG
(
x
i
)
=
InfoGain
(
S
,
x
i
)
-
InfoGain
(
U
,
x
i
)
,
and
InfoGain
(
Y
,
x
i
)
=
-
∑
y
∈
Y
P
(
y
)
log
P
(
y
)
+
P
(
x
i
)
∑
y
∈
Y
P
(
y
|
x
i
)
log
P
(
y
|
x
i
)
+
P
(
x
_
i
)
∑
y
∈
Y
P
(
y
|
x
_
i
)
log
P
(
y
|
x
_
i
)
,
and
where:
x i is an i'th feature of the natural language text,
S is a set constituting the at least one sensitive concept,
s is a sensitive concept,
U is a set constituting the at least one utility concept,
u is a utility concept,
Y is a dummy variable standing in for either S or U, and
Y =Y\y for some yεY.
14. The apparatus of claim 11 , where, when identifying the features, the processor is to:
determine, for a document forming a part of the natural language text, selected features of the document that numerically optimize a constrained objective function established to ensure that the selected features of the document implicate the at least one sensitive concept for the document more than the at least one utility concept for the document; and
provide the selected features as the identified features.
15. The apparatus of claim 14 ,
where the constrained objective function is:
min
f
(
x
^
)
=
-
∑
i
Gain
(
x
i
,
s
,
U
x
)
x
^
i
such
that
:
0
≤
x
^
i
≤
freq
(
x
i
)
,
∑
i
(
log
(
P
(
x
i
|
s
)
)
-
1
)
x
^
i
≤
0
,
∑
i
(
-
log
(
P
(
x
i
|
u
)
)
-
1
)
x
^
i
≤
0
,
where
:
Gain
(
x
i
,
s
,
U
x
)
=
log
(
P
(
x
i
|
s
)
)
-
μ
·
log
(
∑
u
∈
U
x
P
(
x
i
|
u
)
)
,
and
where:
x i is an i'th feature of the document,
s is a sensitive concept of the document,
U x is a set constituting at least one utility concept of the document,
u is a utility concept of the document, and
μ is a weighting parameter.
16. The apparatus of claim 11 , where, when identifying the features, the processor is to:
determine, for a document forming a part of the natural language text, selected features of the document that numerically optimize a constrained objective function established to ensure that the selected features of the document implicate the at least one identified sensitive concept for the document more than at least k−1 other sensitive concepts, of the sensitive concepts, for the document; and
provide the selected features as the identified features.
17. The apparatus of claim 16 ,
where the constrained objective function is:
min
f
(
x
^
)
=
-
∑
i
Utility
(
x
i
,
u
)
x
^
i
such
that
:
0
≤
x
^
i
≤
freq
(
x
i
)
,
∑
i
(
log
(
P
(
x
i
|
s
)
)
x
^
i
)
≤
∑
i
log
(
P
(
x
i
|
s
_
1
)
)
x
^
i
,
⋮
∑
i
(
log
(
P
(
x
i
|
s
)
)
x
^
i
)
≤
∑
i
log
(
P
(
x
i
|
s
_
k
-
1
)
)
x
^
i
,
where
:
Utility
(
x
i
,
u
)
=
(
1
-
P
(
u
)
)
log
(
P
(
x
i
|
u
)
)
-
∑
u
_
∈
U
\
u
P
(
u
_
)
P
(
x
i
|
u
_
)
,
and
where:
x i is an i'th feature of the document,
s is a sensitive concept of the document,
U is a set constituting at least one utility concept of the document,
u is a utility concept of the document, and
s = s 1 , . . . , s k-1 εS are a sequence of k−1 sensitive concepts obtained by ranking all s εS\s by P( s )P(x| s ).
18. The apparatus of claim 11 , where, when perturbing the at least some of the identified features, the processor is to:
suppress the at least some of the identified features.
19. The apparatus of claim 11 , where, when perturbing the at least some of the identified features, the processor is to:
generalize the at least some of the identified features.
20. The apparatus of claim 11 , where the processor is further to:
provide the portion of the natural language text in which the at least some of the identified features have been perturbed as at least one redacted document.
21. A non-transitory computer-readable medium storing instructions, the instructions comprising:
one or more instructions that, when executed by at least one processor, cause the at least one processor to:
receive, via a user input device operatively connected to the at least one processor, one or more user inputs indicating sensitive concepts and utility concepts based on a user interface that includes a visual representation of a plurality of concepts in natural language text,
the plurality of concepts including the sensitive concepts and the utility concepts, and
the natural language text being in an electronic format;
determine the sensitive concepts based on the one or more user inputs, the sensitive concepts being concepts that are to be obscured;
determine the utility concepts based on the one or more user inputs, the utility concepts being concepts are desirable to be preserved;
determine, for at least one feature in the natural language text, a sensitive concepts implication factor based on class-conditional probabilities of the at least one feature according to the sensitive concepts;
determine, for the at least one feature in the natural language text, a utility concepts implication factor based on class-conditional probabilities of the at least one feature according to the utility concepts;
determine, for the at least one feature in the natural language text, a feature score based on a difference between the sensitive concepts implication factor and the utility concepts implication factor; and
perturb the at least one feature based on the feature score satisfying a threshold.
22. The non-transitory computer-readable medium of claim 21 ,
where the one or more user inputs includes a topic, and
where the sensitive concepts are associated with the topic.
23. The non-transitory computer-readable medium of claim 21 , where the one or more instructions to perturb the at least one feature comprise:
one or more instructions that, when executed by the at least one processor, cause the at least one processor to: suppress the at least one feature.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.