An Adaptive Feature Selection Methodfor Learning-to-Enumerate Problem
Satoshi Horikawa
Chiyonosuke Nemoto
Keishi Tajima
Masaki Matsubara
Atsuyuki Morishima
University of Tsukuba

Kyoto University

What is Learning-to-Enumerate Problem [1]?

Problem Setting

item sety

 Given a ﬁxed set of items
 Find n instances of the target classy

with examining a min number of items
 Start with no classiﬁer/training datayyyyy“ﬁnd 3y”

In this study, we also assume: Start with a hand-crafted noisy feature set↓

including both useful ones and useless ones
[1] Jörger et al., “Learning to Enumerate”, ICANN 2016
University of Tsukuba / Kyoto University

ECIR 2024

2/16

What is Learning-to-Enumerate Problem?

Example Given a corpus of news articles.
 Find 10 news that may inﬂuence the business ofToyota.

 No existing classiﬁer, no training data, but we can come up with many candidate keywords:“EV”, “hybrid”, “oil”, “Tesla”, . . .
↑a noisy feature set
University of Tsukuba / Kyoto University

ECIR 2024

3/16

What is Learning-to-Enumerate Problem?

Basic Strategy of L-to-E
Find positive instances + train a classiﬁer in parallel
Until we ﬁnd n positive instances, repeat:
1. Select an item to label based on some criteria.
2. Manually label it, and add it to the training dataset.
3. If it is a positive instance,
add it also to the set of found items.
4. Retrain a classiﬁer with the expanded dataset.
University of Tsukuba / Kyoto University

ECIR 2024

4/16

What is Learning-to-Enumerate Problem?

L-to-E ̸= Active Learning
What is common Label items and re-train a classiﬁer repeatedly.

Diﬀerence Active Learning: to obtain a good classiﬁer→ label items that best improve the classiﬁer

 L-to-E: to ﬁnd positive instances→ exploitation-exploration trade-oﬀ
Jörger et al.[1]: exploitation-only strategy works well
University of Tsukuba / Kyoto University

ECIR 2024

5/16

What is Learning-to-Enumerate Problem?

Exploitation-only Strategy for L-to-E
Until we ﬁnd n positive instances, repeat:
1. Select the most likely item by the current classiﬁer.
2. Manually label it, and add it to the training dataset.
3. If it is a positive instance,
add it also to the set of found items.
4. Retrain a classiﬁer with the expanded dataset.
Exploitation-only L-to-E ≈ Relevance Feedback
University of Tsukuba / Kyoto University

ECIR 2024

6/16

Problems to Solve

1. We assume we start with a noisy feature set.
How can we quickly discard useless ones?
2. Drawback of exploitation-only strategy:
The classiﬁer is biased to clusters found earlier.
5yyy3

1y
2
yy

University of Tsukuba / Kyoto University

4y

ECIR 2024

7/16

Basic Approach of Our Method AdaFeaSE1. Binary weights to features.
 Compare discriminative power of features.
 Inactivate features inferior to any others.

“hybrid” > “oil” → inactivate “oil” (weight=0)2. Adaptively change the features to use.
 When we run out of items having some feature,

we re-activate features that were inferior to it.

no remaining article includes “hybrid”→ re-activate “oil”
University of Tsukuba / Kyoto University

ECIR 2024

8/16

Details of AdaFeaSE (1/4)

State Transition of Features

University of Tsukuba / Kyoto University

ECIR 2024

9/16

Details of AdaFeaSE (2/4)

Algorithm (1/2)
Initialization of variables:
FactiveFinactiveFﬁnished= {all features}= ∅= ∅

active features
inactive features
ﬁnished features

Xlabeled= ∅Xunlabeled = {all items}

already labeled items
remaining items= ∅found positive items

Ans

University of Tsukuba / Kyoto University

ECIR 2024

10/16

Details of AdaFeaSE (3/4)

Algorithm (2/2)
While |Ans| < n
1. Select x ∈ Xunlabeled having the largest number off ∈ Factive
2. Label x, move x from Xunlabeled to Xlabeled
3. If positive(x), add x to Ans
4. Move features no remaining item has to Fﬁnished
5. Reassign f ̸∈ Fﬁnished to Factive or Finactive
based on the expanded dataset Xlabeled
University of Tsukuba / Kyoto University

ECIR 2024

11/16

Details of AdaFeaSE (4/4)

ExampleinactiveactiveEVhybridoilunlabeled items'ﬁnished$' labeled items$%&%. . . hybrid . . . EV . . .
EV, hybrid . . .
. . . EV . . .

&. . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16Details of AdaFeaSE (4/4)

ExampleinactiveactiveEVhybridoilunlabeled items'. . . hybrid . . . EV . . .
EV, hybrid . . .
. . . EV . . .

&ﬁnished$' labeled items$%&%✓ . . . hybrid . . . EV . . .

. . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16

Details of AdaFeaSE (4/4)

Exampleinactive

activeEVhybridoilunlabeled items'EV, hybrid . . .
. . . EV . . .

&. . . EV . . . oil

ﬁnished$' labeled items$%&%✓ . . . hybrid . . . EV . . .
× . . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16

Details of AdaFeaSE (4/4)

Exampleinactive

activeEVhybridoiloilunlabeled items'EV, hybrid . . .
. . . EV . . .

&ﬁnished$' labeled items$%&%✓ . . . hybrid . . . EV . . .
× . . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto UniversityECIR 2024

12/16

Details of AdaFeaSE (4/4)

Exampleinactive

activeEVhybridﬁnishedoilunlabeled items'EV, hybrid . . .
. . . EV . . .

&$' labeled items$%&%✓ . . . hybrid . . . EV . . .
✓ EV, hybrid . . . × . . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16

Details of AdaFeaSE (4/4)

Exampleinactive

activeEVhybridﬁnishedhybridoilunlabeled items'. . . EV . . .

&$' labeled items$%&%✓ . . . hybrid . . . EV . . .
✓ EV, hybrid . . . × . . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16

Details of AdaFeaSE (4/4)

Exampleinactive

activeEVﬁnishedhybridoiloilunlabeled items'. . . EV . . .

&$' labeled items$%&%✓ . . . hybrid . . . EV . . .
✓ EV, hybrid . . . × . . . EV . . . oil. . . oil . . . EV

University of Tsukuba / Kyoto University

ECIR 2024

12/16Experiment

DatasetNews Corpus 6,684 news articles by Yahoo! JapanTwo Topics
1. Events inﬂuencing Toyota (79 positive instances)
2. Scandals of celebrities (252 positive instances)
Initial Feature Set (keyphrases) Crowdsourced
 272 phrases for Toyota and 286 for Scandal
University of Tsukuba / Kyoto University

ECIR 2024

13/16

ExperimentBaselines
 logistic regression (LR) logistic regression (LR) + PCA
 random forest (RF) random forest (RF) + PCA
 Lasso Lasso + PCA⋆ Deep learning does not work well with small training data.
University of Tsukuba / Kyoto University

ECIR 2024

14/16

Experiment

ResultAdaFeaSE
LR
LR-PCA
RandomForest

0.6
0.5

RandomForest-PCA
lasso
lasso-PCA

0.5

RandomForest-PCA
lasso
lasso-PCA

0.4
recall0.4
recallAdaFeaSE
LR
LR-PCA
RandomForest

0.6

0.3

0.3

0.2

0.2

0.1

0.1
000100

200

round

300

400

500

0100

200

300

400500round

ToyotaScandal AdaFeaSE (red) performs best within these rounds.
 Others overtake when trained enough in later rounds.
 AdaFeaSE is quicker to ﬁnd e.g. 40 articles.
University of Tsukuba / Kyoto University

ECIR 2024

15/16

Discussion

Why binary?
 Lasso, which uses regularization, also worked well.
 Binary = more aggressive regularization.
 Our method can aggressively assign weight 0

because we can re-activate it later.
Why exploitaion-only?

 The feature sets were complete enough for ﬁndinge.g., 50 items.
 Exploring given candidate features must be enough.
Key: Noisy and complete enough feature set available
University of Tsukuba / Kyoto University

ECIR 2024

16/16