Machine Learning - �Basic Principles & Practice�4. When Nearest Neighbor Does Not Work

Cong Li 李聪

机器学习 - 基础原理与实践

4. 最近邻无效之时

Assumption in Nearest Neighbor 最近邻的假设

• Close Neighbors Come from the Same Class 邻近的数据来自同一个类
• Is the Assumption Valid 这个假设有效吗？
• Distance definition is the key 距离的定义很关键？
• Let’s start from a synthetic problem 让我们从一个人造问题开始

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Why Looking at Synthetic Problems? 为什么要看人造问题？

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Simple & well controlled 简单可控

Easy to analyze 易于分析

Cons: maybe not realistic

缺点：可能不够实际

Simple Synthetic Problem 简单的人造问题

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

20 random training samples 20个随机训练数据

Practice 4.1 实践4.1

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Practice time: perform nearest neighbor classification on the problem 实践时刻：用最近邻分类处理该问题

How the accuracy changes w/ more training samples?

当有更多的训练数据时，准确率如何变化？

Simple Analysis 简单分析

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Accuracy determined by the training samples close to the classification boundary 准确率由邻近分类边界的训练数据决定

Simple Analysis 简单分析

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Accuracy determined by the training samples close to the classification boundary 准确率由邻近分类边界的训练数据决定

Practice 4.2 实践4.2

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Compare the accuracy to that in the previous case

和前一个问题比较准确率

What Happened? 怎么回事？

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

The irrelevant attribute obscures the distance, that is, obscures the similarity 不相关的属性把距离（也把相似度）给弄乱了

What Happened? 怎么回事？

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

The irrelevant attribute obscures the distance, that is, obscures the similarity 不相关的属性把距离（也把相似度）给弄乱了

More data helps

更多的数据能帮助改善问题

Issue in Nearest Neighbor 最近邻的问题

• Sparse Data Cases 数据稀疏之时
• Similarity sensitive to attributes which are less relevant�相似度对于不那么相关的属性太敏感
• Breaking the Assumption 破坏了假设
• ‘Similar’ samples now do not come from the same class �“相似”的数据并非来自于同一类

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Potential Solutions 潜在的方案

• More Data 更多的数据
• Data is expensive 数据的代价高昂
• Better Feature Engineering 更好地处理特征属性
• Need additional skills & effort �需要额外的技能和投入

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

A Real World Problem 一个真实的问题

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Word ‘interest(s)’ as a noun

作为名词的单词“interest(s)”

Problem: determine the word sense based on the context

问题：根据上下文确定词义

Data 数据

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

From Wall Street Journal 1989 来自1989年华尔街日报

Example 示例

last/JJ month/NN ,/, judge/NP curry/NP set/VBD the/DT interest/NN rate/NN on/IN the/DT refund/NN at/IN 9/AB %/NN ./.

Six categories (senses) 六种词义

Part-of-speech tagged 词性已被标注

To Deal with the Problem 处理这个问题 (1)

• Common Questions 常规问题
• What’s the input? 输入是什么？
• What’s the output? 输出是什么？
• What’s the program? 程序是什么？
• What’s the Output? 输出是什么？
• Easiest to answer 最容易回答
• 6 categories: 1~6 6个类别：1~6

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

To Deal with the Problem 处理这个问题 (2)

• What’s the Program? 程序是什么？
• Supposed to be nearest neighbor 假定是最近邻吧
• Do we have any other choices? 我们学过别吗？
• What’s the Input? 输入是什么？
• A sentence w/ variable length? 一个不定长度的句子？
• How to deal w/ that using nearest neighbor? 最近邻能处理这样的输入吗？

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Convert the Input 变换输入 (1)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Create a ‘dictionary’ giving each unique ‘word’ an index 创建一本“字典”，为每个独一无二的“词”赋予一个下标

yields/NNS → 0,

on/IN → 1,

money-market/JJ → 2,

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

Convert to fixed length array w/ 9020 elements (0~9019): default values are 0

变换成一个固定长度为9020的数组，每一个元素缺省值填0

…

…

…

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

…

…

…

1

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

…

…

…

1

1

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

…

…

…

1

1

1

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

…

…

…

1

1

1

1

Convert the Input 变换输入 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dictionary

…

,/, → 8

…

last/JJ → 104,

month/NN → 105,

judge/NP → 106,

curry/NP → 107,

…

cent/NN → 9019

last/JJ month/NN ,/, judge/NP curry/NP …

Index

下标

104

105

106

107

8

…

…

…

1

1

1

1

1

Practice 4.3 实践4.3

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Try word sense disambiguation: randomly choose 50% data for training & remaining for testing

尝试词义消歧：随机选50%的数据用作训练，剩余用作测试

Does it perform well?

表现好吗？

How Does It Perform? 表现如何？

• Does It Perform Well? 表现好吗？
• Even worse than always choosing the majority 比永远选择最多数类别还差
• Why? 为什么？
• Too many attributes (9000+) vs low training samples (1000+) 属性太多（9000+），训练数据太少（1000+）
• Sparse vector: many 0s 稀疏向量：很多0
• Not easy to calculate similarity 计算相似度不容易
• Any potential improvement? 能改进吗？

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Different Similarity Definition 另一种相似度 (1)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Illustrative example 说明用例

3-word dictionary 仅包含三个单词的字典

rate → 0, my → 1, saving → 2

Which one is more similar to the new item? Data item 1 or 2?

那个数据和新数据更相似？1还是2？

Equally similar in Euclidean distance or Hamming distance

在欧氏距离或海明距离中，同等相似

Different Similarity Definition 另一种相似度 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my

saving

rate

1

1

Different Similarity Definition 另一种相似度 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my

saving

rate

Euclidean distances are the same

欧氏距离相同

Different Similarity Definition 另一种相似度 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my

saving

rate

Cosine similarity discriminates

余弦相似度得以区分

How to Calculate 如何计算

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Cosine similarity

余弦相似度

Dot Product 点乘 (1)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dot Product 点乘 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my saving interest rate

rate

my

saving

interest rate

1

0

0

1

1

1

1

0

0

Dot Product 点乘 (3)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my interest

rate

my

saving

interest rate

1

0

0

0

1

0

0

0

0

In the illustrative example, the dot product extracts the extent of overlapping in the context

在这个说明用例中，点乘抽取出了上下文的重合度

Dot Product 点乘 (4)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Dot product in a higher dimensional case is similar

更高维度的点乘也是类似的

Vector Length 向量长度 (1)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

The dot product has extracted the extent of overlapping in the context. Why do we need vector lengths in denominator?

点乘已经抽取出了上下文的重合度，为什么我们还要在分母里的向量长度？

Consider the case below 看看下面的例子

Which one of the two is more similar to ‘interest rate’? ‘my saving interest rate’ or ‘interest rate’?

两者中的哪个和“interest rate”比更相似？“my saving interest rate”还是“interest rate”

Intuitively, ‘interest rate’ is more similar to ‘interest rate’, since they are identical 直观而言，“interest rate”和“interest rate”更相似，因为他们完全相同

Vector Length 向量长度 (2)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

If we only have dot product

如果我们只有点乘

By nature, longer context is more likely to yield overlapping

自然，更长的上下文更容易产生重合

We need to penalize the context length by introducing the vector lengths in the denominator

我们需要在分母中引入向量长度，削弱长的上下文的优势

Vector Length 向量长度 (3)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my

saving

rate

Vector length: distance from the origin

向量长度：离原点的距离

Vector Length 向量长度 (3)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

my

saving

rate

1

1

1

Vector Length 向量长度 (4)

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Vector length in a higher dimensional case is similar

更高维度的向量长度也是类似的

Practice 4.4 实践4.4

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Try word sense disambiguation using cosine similarity

用余弦相似度尝试词义消歧

Does it perform better?

表现好点了吗？

Result 结果

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

Still Not Satisfied? 仍不满意？

• Better but Not Satisfactory 好一点，但仍不够令人满意
• Too many attributes vs low training samples 属性太多，训练数据太少
• To Do Better 想要做得更好
• Carefully select relevant attributes 仔细地选择合适的属性
• Switch to something radically different 换上全然不同的手段

Machine Learning – Basic Principles & Practice: 4. When Nearest Neighbor Does Not Work

机器学习 – 基础原理与实践： 4. 最近邻无效之时

The End