KNN and re-ranking
re ranking models for English
patent miningg at NTCIR-7
pTong Xiao, Feifei Cao, Tianning Li, Guolong Song, Ke Zhou, JingboZhu and Huizhen Wang
Natural Language Processing Lab,Northeastern University (P. R. China)
xiaotong@mail.neu.edu.cn

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummaryOutline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummaryIntroduction of our group• NaturalN t l Language
LPProcessing
i LLaboratory,b tCCollegelloff
information science and engineering, Northeastern University• Working on a variety of problems related to Natural Language
Processing– Statistical machine translation– Syntactic
Si parsingi– Applied semantics ontology learning– Text miningg• Focus on patent mining from 2007
• Welcome to our homepage http://www.nlplab.com

Patent mining task at NTCIR
NTCIR-77•

Patent mining taskk– Mapping research papers intopatent taxonomy(International PatentClassification)•<TITLE>End-ventilating adjustable pitch arcuate roof ventilator</TITLE><ABSTRACT>A roof ridge ventilator is provided, comprising preferably a molded ventilator, with openings
along the sides thereof for passage of air therethrough and with openings at ends thereof for passage of air
therethrough via gaps provided in pluralities of rows of tabs …</ABSTRACT>< IPC> F24F_7_02, F24F_7_007 </IPC><CLAIM>What is claimed is: 1. A roofing ridge ventilator for venting a roof for …</CLAIM>……

Three sub-tasks– English patent mining– Japanese patent mining– Cross language
g g patentpminingg• We participated in the
English patent mining
sub task
sub-task

patentdatatitle andabstract of thepaper to besearched

input

Patent miningsystem<TITLE>
Study on a Natural Ventilation System Using a Pitched
pof theRoof with Breathingg Walls Part 1 Proposal
System and Its Design for Ventilation</TITLE><ABSTRACT>We proposed a natural ventilation system using apitched roof with Breathing Walls, …
</ABSTRACT>

rankedlist of
IPC codes

output

IPC code
E04B_1_70
F24F_7_10
F24F_7_007
F24F_1_00
F24F_7_08
F24F_7_013
F24F_7_06
F24F_1_02…

Rank
12345678

Score
14.23
13.06
12.76
11.70
11.51
11.38
9.923
7.686

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummaryChallenges• Huge amount of training
dataUSPTO
patents– over 3 million trainingg
samples– how to train a supervisedclassifierl ifi or rankerk• Huge label set and multilabel– IPC is a hierarchicalclassification system
which consists of morethan 60,000 IPC codes.

Millionsof patents

PAJ……

patent

IPC taxonomy

Label (IPC)
F24F_7_08
F24F_7_10
E06B_7_02…

E…
…

F24F_7_10

F

G

F24F_7…

F24F_7_08…

F24F_7_06

Very large number of IPC codes…

Challenges• Class imbalance problem ofIPC

number ofpatents– The distribution of IPC codesis skewed• Different writing styles
between research papers
and patents– conflicts with thefoundational hypothesis ofsupervised documentclassification theoryy

IPC code
IPC1

IPC2

IPC3

IPC4

IPC5

IPC6

The same topicpatent

Similarity = 1.01 0?

Researchpaper

Motivation•

Difficult to apply sophisticated machine learning methods such as maximum
entropy methods and support vector machines on patent mining– great deal of memory space and time cost is required task
– no goodd solutionsl ti
tto multi-label
lti l b l classification
l ifi ti on very llarge classl sett•

K-Nearest
KNt Neighboring
N i hb i (KNN)
method is a comparatively easysolution– extracting similar examples andno training process is required– KNN is itself a rankingg

Test sample
Sample in class1Sample in class2

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• Summary

KNN based method
KNN-based• Key components– KNN-based ranking– Re-ranking
Rki• Each document isrepresented
d as avector in our system

Pre--pPre
processingg

Research
paper

Extracting
title and abstract
Tokenization and removingcase info.

stemming

KNN--based ranking
KNN
English patents(for training)

Similarity calculation

ranking

Re--ranking
ReRankcombination

Rank
SVMSimilarity calculation• Calculate the similarityy between
the test sample (research paper)and the training samples(patents)• State-of-the-art methods– Cosine + tfidf– BM25 ((Robertson et al,, 1998))– SMART (Buckley et al, 1996)– PIV (Singhal et al, 1996)– Or some other …

• Log-linear method– Combine different similarities(features) to generate a refinedsimilarity– Different weights to different
features

Test Sample
and training samples

cosineBM25SMART…

sim1

sim2

sim3…

exp( ∑ m =1 λ m ⋅ Score m ( c ))M

Score log-linear ( c ) =∑ exp( ∑cM
m =1Combinedsimilarity

λ m ⋅ Score m ( c ))

Ranking•

1. Original KNN ranking method:–•••the order of IPC codes follows the order of theirfirst occurrences in the extracted top-kp
documents

3. Sum/SumAver––4. Listweak/ListweakAver–

Score each IPC code by the number of its
occurrence in the extracted top-k documents

2. Naïve method–•score is calculated by summing up the similaritiesof all the extracted documents containing thegiven IPC codeF SSumAver,ForA
we average theh similarity
i il i ffor eachhsample

to emphasize the patents ranked in the frontier
part of the list, a new factor is introduced

5. Weak/WeakAver––

A drawback of KNN is the prediction of the input
document tends to be dominated byy the classes
with the more frequent examples due to theclass imbalance problem
Punish the classes which contain more training
samplesRanking – method 1•

1. Original KNN ranking method:–•

2. Naïve method–•

Score each IPC code by the number of its
occurrence in the extracted top-k documents

the order of IPC codes follows the order of theirfirst occurrences in the extracted top-kpdocuments

3. Sum/SumAver––score is calculated by summing up the similaritiesof all the extracted documents containing thegiven IPC code
F SSumAver,ForA
we average theh similarity
i il i ffor eachhsample

Suppose that we obtain the following list (top-5)
after similarity calculation
RankPatent(id)

IPC

sim12
3
4
5

p02
p03
p04
p05
p01

IPC1, IPC20.21IPC3, IPC40.11

IPC20.09

IPC20.09

IPC10.07

Occurred 3 times

IPCscore

IPC2
IPC1
IPC3
IPC43211

IPC list after ranking

Ranking – method 2•

1. Original KNN ranking method:–•

2. Naïve method–•

Score each IPC code by the number of its
occurrence in the extracted top-k documents

the order of IPC codes follows the order of theirfirst occurrences in the extracted top-kpdocuments

Suppose that we obtain the following list (top-5)
after similarity calculation
RankPatent(id)IPCsim12345p02
p03
p04p05p01

IPC1, IPC2

0.21

IPC3, IPC4

0.11

IPC2

0.09

IPC20.09

IPC10.07

first occurrence

3. Sum/SumAver––score is calculated by summing up the similaritiesof all the extracted documents containing thegiven IPC code
F SSumAver,ForA
we average theh similarity
i il i ffor eachhsample

secondoccurrence

IPC

score

IPC1
IPC2
IPC3
IPC4

0.21
0.21
0.11
0.11

IPC list after ranking

Ranking – method 3•

1. Original KNN ranking method:–•2. Naïve method–•

Score each IPC code by the number of its
occurrence in the extracted top-k documents

the order of IPC codes follows the order of theirfirst occurrences in the extracted top-kp
documents

3. Sum/SumAver––score is calculated by summing up the similaritiesof all the extracted documents containing thegiven IPC code
F SSumAver,ForA
we average theh similarity
i il i ffor eachhsample

Suppose that we obtain the following list (top-5)
after similarity calculation
RankPatent(id)IPCsim12345p02
p03
p04
p05
p01

IPC1, IPC20.21

IPC3, IPC40.11

IPC20.09

IPC20.09

IPC10.07

IPC

score

IPC2
IPC1
IPC3
IPC40.39
0.28
0.11
0.11

IPC list after ranking

0.21 + 0.09 + 0.09
= 0.390 39

Ranking – method 4
Suppose that we obtain the following list (top-5)
after similarity calculation
Rank

Patent(id)

IPC

sim12
3
45

p02
p03
p04
p05
p01

IPC1, IPC2

0.21

IPC3, IPC40.11

IPC20.09

IPC20.09

IPC10.07

IPC

score

IPC2
IPC1
IPC3IPC40.34

Sim = 0.21 × 0.91-1=0.21
Sim = 0.09 × 0.93-1=0.07
Sim = 0.09 × 0.94-1=0.06

Sim = 0.21 + 0.07 + 0.06 = 0.34

0.25
0.10
0.10

IPC list after ranking•

4. Listweak/ListweakAver– to emphasize the patents ranked in thefrontier part of the list, a new factor isintroduced•

5. Weak/WeakAver– A drawback of KNN is the prediction of theinput document tends to be dominated by
the classes with the more frequent
examples due to the class imbalance
problem– Punish the classes which contain moretraining samples

Ranking – method 5
Suppose that we obtain the following list (top-5)
after similarity calculation
RankPatent(id)IPC

sim12345

p02
p03
p04
p05
p01

IPC1, IPC2

0.21

IPC3, IPC4

0.11

IPC20.09

IPC20.09

IPC10.07

IPC

score

IPC2
IPC1
IPC3
IPC40.26

Suppose that there are 10 patentslabeled with IPC2
Sim = 0.21 × 0.9(1+10/5)=0.15
Sim = 0.09 × 0.9(2+10/5)=0.06
Sim = 0.09 × 0.9(3+10/5)=0.05

Sim = 0.15 + 0.06 + 0.05 = 0.26

0.19
0.07
0.07

IPC list after ranking•

4. Listweak/ListweakAver– to emphasize the patents ranked in thefrontier part of the list, a new factor isintroduced•

5. Weak/WeakAver– A drawback of KNN is the prediction of the
input document tends to be dominated by
the classes with the more frequent
examples due to the class imbalance
problem– Punish the classes which contain moretraining samples

Re ranking
Re-ranking•What have we had– Tens of ranked lists
generated bydifferent
combinations ofsimilarity calculation
method and ranking
method•Motivation– LearnLabbettertt
ranking fromindividual ranked
lists (basic ranker)

Similarity calculation:
obtaining thesimilarity between thetest sample and eachtraining sample

Ranking:
Assign each IPC code ascore in terms of the
document similarities

Combination

cosinePatent
P01
p02
P03
03

Sim
0.563
0.455
0.203
0 203

BM25
Patent
P02
p01
P03
03

Sim
3.161
2.942
0.235
0 23

SMART
PatentP03
p01
P0202…

Sim
0.999
0.452
0.135
0 13

Naïve

Sum

ListweakCosine+Sum

BM25 + Naïve

SMART+Listweak

IPC coded ScoreS
IPC13.321
IPC22.300
IPC31.982

IPC coded Score
S
IPC1
3.161
IPC33.161
IPC22.942

IPC coded Score
S
IPC1
1.237
IPC21.213
IPC30.942…

…

Rank combination• A linear combination of ranks in individual lists
List1Rank
123

List2

IPC code Score
IPC13.321
IPC22.300
IPC3
1.982

Rank
123

IPC code Score
IPC13.161
IPC33.161
IPC22.942

1 / (λ1× rank1 + λ2× rank2 + λ3× rank3)
Scorerank -combination ( c ) =1∑

hi =1

λ i ⋅ rankinlist ( c , li )List3Rank
123

IPC code Score
IPC1
1.237
IPC21.213
IPC30.942

RankSVM• Learn a ranking function– Each IPC is representp
as a vector,, in which the feature is
the score in each ranked list
List1Rank
12
3

IPC code Score
IPC1
3.321
IPC2
2.300
IPC3
1.982

List2
Rank
123

IPC code Score
IPC1
3.161
IPC33.161
IPC22.942

Feature vector of IPC3 : <1.982,1.982, 3.161, 0.942>
0.942List3Rank
123

IPC code Score
IPC1
1.237
IPC21.213
IPC30.942

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummaryExperiment• DataD t (t(training)i i )– Patent Abstracts of Japan (PAJ)• Settings– Bag-of-words model– No feature selection– K = 100 (for KNN)

• Evaluation– Mean average precision (MAP)• Re-ranking– UsedU d 6 basic
b i rankers
k ffor rankk combinationbi i– Used 5 basic rankers for RankSVM

Experiment (cont.)(cont )••••

KNN-based rankings (dry-run)Re-ranking (dry-ran)

Ranking ¥ Sim

Cosine

BM25

SMART

PIV

Log-linear

systemMAP

Original KNN

35.16

34.79

35.78

34.51

35.05

Rank combination

45.31

Naïve32 41
32.41

38 57
38.57

33 55
33.55

37 23
37.23

40 02
40.02

R kSVM
RankSVM

43 02
43.02

Sum

35.97

35.78

36.83

35.58

38.33

SumAver

35.05

35.92

36.46

34.13

38.05

Li t
Listweakk36 63
36.63

40 52
40.52

37 42
37.42

36 85
36.85

40 37
40.37

ListweakAver34.85

40.88

37.65

36.79

41.11

system

MAP

Weak

36.25

36.53

37.11

35.91

38.24

Rank combination

48.86

WeakAver

33.42

36.15

34.90

33.01

38.38

RankSVM

47.21•

Re-ranking (formal-ran)

Rankingg is a keyy factor that affects the performance
pof the basic KNNbased system
Re-ranking can improve the performance of the basic KNN-based
system significantly

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummaryDiscussion – Issue 1• Single label vs. multi-label– Both the training data of single label (USPTO data set) and multi-label(PAJ data set) are provided within this task.
task– However we found that the data of USPTO shows harmful to ouryThe performancepdegradesgwhen we trained the systemyonsystem.
USPTO data solely or a mixed data set of “USPTO+PAJ”, comparing totraining on PAJ data
Another problem:
H tto train
Howt i a system
ton hheterogeneoustddatat ?
NativeEnglishTranslation

Discussion – Issue 2• Two types of ranking techniques used– The first one is based on position of each candidate in theoutput
t t list,
li t suchh as Naïve,N ï Rank
R k combination.
bi ti– The second one is based on the similarity score of eachcandidate,
did t suchh as SumSanddRRankSVM.
kSVM• The first type of ranking is effective though they aresimple.

Discussion – Issue 3• Does patent structure
really help ?
– Make use of features indifferent sections, such as
titl abstract
title,
b t t andd claim.
l i– It seems not helpful– NeedN d further
f h studyd<TITLE>End-ventilating adjustable pitch arcuate roof
ventilator</TITLE><ABSTRACT>A roof ridge
g ventilator is provided,
pcomprising preferably a molded ventilator, withopenings along the sides thereof for passage of air
therethrough and with openings at ends thereof forpassagepg of air therethroughg via gaps
g p provided
pinpluralities of rows of tabs …</ABSTRACT>< IPC> F24F_7_02, F24F_7_007 </IPC><CLAIM>What is claimed is: 1. A roofing ridge
ventilator for venting a roof for air passage between
the interior of a roof and the outside ambient throughsides of the ventilator and through ends of theventilator…</CLAIM>……

Outline• Overviewi• Basic idea
• Methodology– KNN-based
KNN based method– Re-ranking• Experiment
Ei• Discussion• SummarySummary• We participatedi id iin NTCIR-7 English
li h patent mining
i isub-task– KNN-based method– Re-rankingg• In future– Try to apply our techniques to patent mining tasks
tasks,
such as patent prior art searching.

Thank you!