US7130837B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Systems and methods for determining the topic structure of a portion of text
Assignee: Xerox Corp
•
Filing: 2002-03-22
•
Granted: 2006-10-31
•
Expires: 2022-03-22
Abstract
Abstract Systems and methods for determining the topic structure of a document including text utilize a Probabilistic Latent Semantic Analysis (PLSA) model and select segmentation points based on similarity values between pairs of adjacent text blocks. PLSA forms a framework for both text segmentation and topic identification. The use of PLSA provides an improved representation for the sparse information in a text block, such as a sentence or a sequence of sentences. Topic characterization of each text segment is derived from PLSA parameters that relate words to “topics”, latent variables in the PLSA model, and “topics” to text segments. A system executing the method exhibits significant performance improvement. Once determined, the topic structure of a document may be employed for document retrieval and/or document summarization.
Inventors
- 👤 Ioannis Tsochantaridis
- 👤 Thorsten H. Brants
- 👤 Francine R. Chen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/313
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
108 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distribution of words in adjacent text blocks using a similarity metric to determine similarity values smoothing the similarity values after making comparisons; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 2
Dependent Claim
108 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distribution of words in adjacent text blocks using a similarity metric to determine similarity values smoothing the similarity values after making comparisons; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 3
Dependent Claim
17 words
The method of claim 1 , wherein smoothing the similarity values is based on a weighted sum.
Claim 4
Dependent Claim
17 words
The method of claim 1 , wherein smoothing the similarity values is based on a geometric mean.
Claim 5
Dependent Claim
18 words
The method of claim 1 , wherein smoothing the similarity values is based on a n-point median smoother.
Claim 6
Dependent Claim
131 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the position of test corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein making comparisons of the distributions of words in adjacent text blocks using a similarity metric is based on at least one of a Hellinger distance or a Jensen-Shannon divergence.
Claim 7
Dependent Claim
131 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the position of test corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein making comparisons of the distributions of words in adjacent text blocks using a similarity metric is based on at least one of a Hellinger distance or a Jensen-Shannon divergence.
Claim 8
Dependent Claim
127 words
A computerized method for determining the topic structure of a portion of text having one or more segments, comprising: applying a folding-in process to each segment to determine a probability distribution over latent classes for each segment; using each determined distribution to estimate a distribution of word groups for each segment; and identifying at least one topic for each segment based on the distribution of word groups for the segment; wherein identifying at least one topic for each segment is also based on at least one of a measure of an occurrence of word groups in each segment, term vectors for each segment, on parts of speech of the word groups in the segments, and on mutual information between word groups in each segment and each segment.
Claim 9
Dependent Claim
127 words
A computerized method for determining the topic structure of a portion of text having one or more segments, comprising: applying a folding-in process to each segment to determine a probability distribution over latent classes for each segment; using each determined distribution to estimate a distribution of word groups for each segment; and identifying at least one topic for each segment based on the distribution of word groups for the segment; wherein identifying at least one topic for each segment is also based on at least one of a measure of an occurrence of word groups in each segment, term vectors for each segment, on parts of speech of the word groups in the segments, and on mutual information between word groups in each segment and each segment.
Claim 10
Dependent Claim
61 words
The method of claim 6 , wherein, when identifying at least one topic for each segment is also based on the measure of the occurrence of word groups in each segment, identifying at least one topic for each segment is based on the distribution of word groups for each segment and on inverse segment frequency of word groups in the segments.
Claim 11
Dependent Claim
49 words
The method of claim 6 , wherein, when identifying at least one topic for each segment is also based on the term vectors for each segment, identifying at least one topic for each segment is also based on a measure of an occurrence of word groups in the segments.
Claim 12
Dependent Claim
37 words
The method of claim 8 , wherein identifying at least one topic for each segment is based on the distribution of word groups for each segment and an inverse segment frequency of word groups in the segments.
Claim 13
Dependent Claim
54 words
The method of claim 6 , wherein, when identifying at least one topic for each segment is also based on the parts of speech of the word groups in the segments, identifying at least one topic for each segment is also based on a measure of an occurrence of word groups in each segment.
Claim 14
Dependent Claim
37 words
The method of claim 10 , wherein identifying at least one topic for each segment is based on the distribution of word groups for each segment and an inverse segment frequency of word groups in the segments.
Claim 15
Dependent Claim
55 words
The method of claim 6 , wherein when identifying at least one topic for each segment is also based on the mutual information between word groups in each segment and each segment, identifying at least one topic for each segment is also based on a measure of an occurrence of word groups in each segment.
Claim 16
Dependent Claim
37 words
The method of claim 11 , wherein identifying at least one topic for each segment is based on the distribution of word groups for each segment and an inverse segment frequency of word groups in the segments.
Claim 17
Dependent Claim
15 words
The method of claim 6 , wherein each word group includes one or more words.
Claim 18
Dependent Claim
114 words
A computerized method for retrieving a portion of text, comprising: determining topic structures of a plurality of portions of text by; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; and retrieving at least one of the plurality of portions of text using the topic structures of the portions of text.
Claim 19
Dependent Claim
114 words
A computerized method for retrieving a portion of text, comprising: determining topic structures of a plurality of portions of text by; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; and retrieving at least one of the plurality of portions of text using the topic structures of the portions of text.
Claim 20
Dependent Claim
35 words
The method of claim 15 , wherein retrieving at least one of the plurality of portions of text using the topic structures of the portions of text is based on at least one key word.
Claim 21
Independent Claim
106 words
A system for determining the topic structure of a portion of text, comprising: an input device for inputting a portion of a text; and at least one processor for applying a folding-in process to each of a plurality of segments of the portion of text to determine a probability distribution over latent classes for each segment, estimating a distribution of word groups for each segment based on the determined probability distribution and identifying at least one topic for each segment based on the distribution of word groups for each segment, wherein the at least one processor identifies the plurality of segments of the portion of text.
Claim 22
Independent Claim
106 words
A system for determining the topic structure of a portion of text, comprising: an input device for inputting a portion of a text; and at least one processor for applying a folding-in process to each of a plurality of segments of the portion of text to determine a probability distribution over latent classes for each segment, estimating a distribution of word groups for each segment based on the determined probability distribution and identifying at least one topic for each segment based on the distribution of word groups for each segment, wherein the at least one processor identifies the plurality of segments of the portion of text.
Claim 23
Dependent Claim
171 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; averaging the plurality of word group distributions for each text block; making comparisons of the plurality of word groups distributions in adjacent text blocks using a similarity metric to determine similarity values based on the averaged plurality of word group distributions; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a plurality of PLSA models uses at least one of different initializations of the models prior to training each model and different numbers of latent variables.
Claim 24
Dependent Claim
171 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; averaging the plurality of word group distributions for each text block; making comparisons of the plurality of word groups distributions in adjacent text blocks using a similarity metric to determine similarity values based on the averaged plurality of word group distributions; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a plurality of PLSA models uses at least one of different initializations of the models prior to training each model and different numbers of latent variables.
Claim 25
Dependent Claim
149 words
A computerized method for determining the topic structure of a portion of text comprising; identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; averaging the plurality of word group distributions for each text block; smoothing the similarity values after averaging; making comparisons of the plurality of word groups distributions in adjacent text blocks using a similarity metric to determine similarity values based on the averaged plurality of word group distributions; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 26
Dependent Claim
149 words
A computerized method for determining the topic structure of a portion of text comprising; identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; averaging the plurality of word group distributions for each text block; smoothing the similarity values after averaging; making comparisons of the plurality of word groups distributions in adjacent text blocks using a similarity metric to determine similarity values based on the averaged plurality of word group distributions; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 27
Dependent Claim
155 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; making comparisons of the plurality of word group distributions in adjacent text blocks using a similarity metric to determine similarity values; averaging the similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a plurality of PLSA models uses at least one of different initializations of the models prior to training each model and different numbers of latent variables.
Claim 28
Dependent Claim
155 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; making comparisons of the plurality of word group distributions in adjacent text blocks using a similarity metric to determine similarity values; averaging the similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a plurality of PLSA models uses at least one of different initializations of the models prior to training each model and different numbers of latent variables.
Claim 29
Dependent Claim
133 words
A computerized method for determining the topic structure of a portion of text comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; making comparisons of the plurality of word group distributions in adjacent text blocks using a similarity metric to determine similarity values; averaging the similarity values; smoothing the similarity values after averaging; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 30
Dependent Claim
133 words
A computerized method for determining the topic structure of a portion of text comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a plurality of PLSA models; applying a folding-in process with each model to each text block to determine a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a plurality of word group distributions for each text block; making comparisons of the plurality of word group distributions in adjacent text blocks using a similarity metric to determine similarity values; averaging the similarity values; smoothing the similarity values after averaging; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 31
Dependent Claim
128 words
A computerized method for determining the number of training iterations for obtaining a PLSA model, comprising: determining a likelihood value according to the formula L fi ( Q ) = ∑ q ∈ Q ∑ w ∈ q f ( w , q ) log ∑ z P ( w z ) P fi ( z q ) for each iteration; comparing the likelihood value of a current iteration to the likelihood value of a previous iteration; and determining the number of training iterations as the current number of iterations when a difference between the likelihood value of the current iteration and the likelihood value of the previous iteration is less than a selected threshold value.
Claim 32
Dependent Claim
128 words
A computerized method for determining the number of training iterations for obtaining a PLSA model, comprising: determining a likelihood value according to the formula L fi ( Q ) = ∑ q ∈ Q ∑ w ∈ q f ( w , q ) log ∑ z P ( w z ) P fi ( z q ) for each iteration; comparing the likelihood value of a current iteration to the likelihood value of a previous iteration; and determining the number of training iterations as the current number of iterations when a difference between the likelihood value of the current iteration and the likelihood value of the previous iteration is less than a selected threshold value.
Claim 33
Dependent Claim
118 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a distribution of probabilities is performed by applying a folding-in process to each text block.
Claim 34
Dependent Claim
118 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein determining a distribution of probabilities is performed by applying a folding-in process to each text block.
Claim 35
Dependent Claim
111 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; determining local dips in the similarity values after making comparisons; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 36
Dependent Claim
111 words
A computerized method for determining the topic structure of a portion of text, comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; determining local dips in the similarity values after making comparisons; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments.
Claim 37
Dependent Claim
127 words
A computerized method for determining the topic structure of a portion of text comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein making comparisons of the distribution of words in adjacent text blocks using a similarity metric is based on a cosine distance or a variational distance.
Claim 38
Dependent Claim
127 words
A computerized method for determining the topic structure of a portion of text comprising: identifying candidate segmentation points of the portion of text corresponding to locations between text blocks; determining a distribution of probabilities over a plurality of latent classes for each text block; using the determined distributions to estimate a distribution of words for each text block; making comparisons of the distributions of words in adjacent text blocks using a similarity metric to determine similarity values; and selecting segmentation points from the candidate segmentation points of the portion of text based on the comparison to define a plurality of segments; wherein making comparisons of the distribution of words in adjacent text blocks using a similarity metric is based on a cosine distance or a variational distance.
References Cited (Backward Citations)
US5606643A
Cited
US5675819A
Cited
US5659766A
Cited
US5687364A
Cited
US5943669A
Cited
US6239801B1
Cited
US6128634A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-10-30 | 2010-05-01 | 2010-10-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-10-30 | 2014-05-01 | 2014-10-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-10-30 | 2018-05-01 | 2018-10-31 | $7700.00 | Window Closed / Lapsed |