Information processing apparatus information processing method, and storage medium

Patent metadata

Field	Value
Publication number	US-9779207-B2
Application number	US-201113824473-A
Country	US
Kind code	B2
Filing date	Dec 19, 2011
Priority date	Feb 17, 2011
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

An information processing apparatus that selects appropriate features in polynomial time from the viewpoint of both the relevance and the redundancy of features to be selected. This information processing apparatus includes a relevance evaluator that evaluates relevance of each feature included in a set of features, a redundancy evaluator that evaluates redundancy between the features included in the set of features, and a selected feature determiner that determines selected features that optimize a submodular objective function defined using the relevance calculated by the relevance evaluator and the redundancy calculated by the redundancy evaluator.

First claim

The invention claimed is:

1. An information processing apparatus comprising: a processor configured to execute:
a relevance evaluator that evaluates relevance E 1 by calculating relevance of each feature S i included in a set of features by
E 1 (s i , X (i) , y), where S i indicates selection or non-selection of the feature, X (i) is the sample group including only the i th feature, and y is class level;
a redundancy evaluator that evaluates redundancy E 2 by calculating redundancy between the features included in the set of features by
E 2 (s i , s j , X (i) , X (j) , y), wherein S j indicates selection or non-selection of the feature, X (j) is the sample group including only the j th feature and the redundancy E2 satisfies a submodularity represented by
E 2 (0,0, X (i) ,X (j) ,y )+ E 2 (1,1, X (i) ,X (j) ,y )≦ E 2 (0,1, X (i) ,X (j) ,y )+ E 2 (1,0, X (i) ,X (j) ,y ); and

a selected feature determiner that determines selected features that minimize a submodular objective function E defined as a sum of the relevance E 1 calculated by said relevance evaluator and the redundancy E 2 calculated by said redundancy evaluator wherein the submodular objective function E defined by

E
⁡

(
s
)

=

-

∑
i

⁢

E
1

⁡

(

s
i

,

X

(
i
)

,
y

)

+

λ
⁢

∑

i
,
j

⁢

E
2

⁡

(

s
i

,

s
j

,

X

(
i
)

,

X

(
j
)

,
y

)

where λ is a positive constant that determines a relative weight of two terms corresponding to the i th feature and the j th feature.

2. The information processing apparatus according to claim 1 , wherein each feature included in the set of features includes a plurality of parameters.

3. The information processing apparatus according to claim 1 , wherein said selected feature determiner optimizes the submodular objective function formed from a term using two features at maximum as arguments to determine the selected features.

4. The information processing apparatus according to claim 1 , wherein said relevance evaluator calculates the relevance using at least two features as arguments.

5. The information processing apparatus according to claim 1 , wherein said relevance evaluator calculates the relevance using a Fisher score.

6. The information processing apparatus according to claim 1 , wherein said redundancy evaluator calculates the redundancy from two features extracted from the set of features.

7. The information processing apparatus according to claim 1 , wherein said selected feature determiner optimizes, by graph cut, an objective function including the relevance calculated by said relevance evaluator and the redundancy calculated by said redundancy evaluator.

8. The information processing apparatus according claim 1 wherein relevance E 1 is evaluated by using Fisher linear discriminant analysis,
and,
wherein the redundancy evaluator calculates the redundancy E2 using a coefficient ρ of correlation by
E 2 ⁡ ( s i , s j , X ( i ) , X ( j ) , y ) = { a 00 ⁢  ρ ij  ( s i = 0 , s j = 0 ) a 01 ⁢  ρ ij  ( s i = 0 , s j = 1 ) a 10 ⁢  ρ ij  ( s i = 1 , s j = 0 ) a 11 ⁢  ρ ij  ( s i = 1 , s j = 1 ) where a 00 +a 11 ≦a 01 +a 10

and where

ρ
ij

=

∑
n

⁢

(

X
n

(
i
)

-

X

(
i
)

_

)

⁢

(

X
n

(
j
)

Assignees

• Ishii Masato
• Nec Corp

Inventors

• Ishii Masato

Classifications

• G06F18/2115

  by evaluating different subsets according to an optimisation criterion, e.g. class separability, forward selection or backward elimination · CPC title

• G06F18/2113

  by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation · CPC title

• G06F19/24 Primary

  Physics · mapped topic

• G06F17/30

  Physics · mapped topic

• G06K9/6231

  Physics · mapped topic