Boosting to Determine Indicative Features from a Training Set
AssigneeMicrosoft Corporation
InventorsJohn Platt, Harvey Rook, Shengquan Yan, Rajasi Saha
Life of this patent
Estimating the term…
Abstract
Determining indicative features may be provided. First, a first set of features may be determined using a document frequency process. Then a second set of features may be determined using a boosting process. Using the boosting process may comprise using an approximation for a one-dimensional optimization. The approximation may include an upper bound. Next, the first set of features and the second set of features may be combined into a combined set of features. The combined set of features may comprise a union of the first set of features and the second set of features. At least one document may then be classified based on the combined set of features.
Claims20
A method for determining indicative features, the method comprising:
- determining a first set of features using a document frequency process;
- determining a second set of features using a boosting process;
- combining the first set of features and the second set of features into a combined set of features, the combined set of features comprising a union of the first set of features and the second set of features;
- and
- classifying at least one document based on the combined set of features.
A computer-readable medium that stores a set of instructions which when executed perform a method for determining indicative features, the method executed by the set of instructions comprising:
- determining a second set of features using a boosting process, wherein using the boosting process comprises using an approximation for a one-dimensional optimization, the approximation including an upper bound, wherein using the boosting process comprises:
- maintaining a zn score for each example n in a training set, each zn score being initiated at zero;
- (a) computing
- s
- n
- =
- 1
- 1
- +
- exp
-
- (
- z
- n
-
- y
- n
- )
- for each possible additional feature into the second set of features, sn comprising the current strength of each example n;
- (b) for the each possible additional feature,
- computing,
- A
- c
- =
- ∑
- n
- ∈
- C
-
- y
- n
-
- s
- n
- B
- c
- =
- ∑
- n
- ∈
- C
-
- (
- 1
- -
- 2
-
- s
- n
- )
- /
- (
- y
- n
-
- z
- n
- )
- η
- c
- =
- 2
-
- A
- c
- B
- c
- comparing, for each possible additional feature into the second set of features, their improvement on the upper bound wherein the improvement comprises,
- ∑
- c
-
- A
- c
- 2
- B
- c
- updating zn for each example n in a training set, and
- updating a weight vector for the second set of features;
- and
- repeating (a) and (b) Until a predetermined improvement value is attained;
- combining a first set of features and the second set of features into a combined set of features, the combined set of features comprising a union of the first set of features and the second set of features;
- and
- transmitting the combined set of features to a classifying module.
A system for determining indicative features, the system
- comprising:
- a memory storage;
- and
- a processing unit coupled to the memory storage, wherein the processing unit is operative to:
- determine a first set of features using a document frequency process;
- determine a second set of features using a boosting process, wherein using the boosting process comprises using an approximation for a one-dimensional optimization, the approximation including an upper bound;
- combine the first set of features and the second set of features into a combined set of features, the combined set of features comprising a union of the first set of features and the second set of features;
- and
- transmit the combined set of features to a classifying module.
Dependencies are inferred from the claim text.