AI工程师必备的核心技能:如何将现实生活中的问题转换为数学优化的问题,然后寻找到适合的工具以解决这个问题

NLP=NLU+NLG

NLU:通过文本理解含义(语义理解)
NLG:语义生成

为什么NLP比计算机视觉(CV)?

  • 一个意思有多个表达方式
  • 一词多义(Ambiguity)

如何解决Abiguity:参考上下文(content)

案例:机器翻译

基于统计的机器翻译系统有哪些缺点:慢、语义、上下文、语法

如何保证语法通顺

首先分词并且一对一翻译:
今晚|的|课程|有意思-》Tonight, of, the course, intersting
然后进行排列组合,找到最合适的概率(使用的是选择器:language Modle,语言模型)(判断哪一个组合最通顺

那么这样分两步的有哪些缺点呢?
如果一句话的单词过多,比如100个单词,那么其排列组合的数量将会是100!(100的阶乘)。。此时的算法复杂度将会是O(n2)

如何避免这个问题呢?(这里希望降低时间复杂度)
能不能同时考虑两个问题一起(Decoding Algorithm)
这里可以使用维特比算法(Viterbi)

简单机器翻译的系统架构

语言模型(LM,Language Model)

  • 给定一句英文e,计算概率(e)
  • 如果是符合英文语法的,p(e)会比较高
  • 如果是随机语句,p(e)会比较低

翻译模型

  • 给定一对<c, e>,计算p(f|e)
  • 语义相似度高,则p(f|e)高
  • 语义相似度低,则p(f|e)低

Decoding Algorithm (Vithvbi)语言模型+翻译模型同时找到最优的解

  • 给定语言模型,翻译模型和f,找出最优的是的p(e)p(f|e)最大

Language Model(语言模型)

对于一个的语言模型:(训练好)

  • p(He is studying AI) > p(He studying AI is)
  • p(nlp is an interesting course) > p(interesting course nlp is an)

怎么计算p(.)

  • p(He is studying AI) = p(He)p(is)p(studying)p(AI)
  • p(He is studying AI) = p(He)p(is|He)p(studying|is)p(AI|studying)
  • p(He is studying AI) = p(He)p(is|He)p(studying|He is)p(AI|is studying)
  • ……

分别可以向前看1,2,……,n个单词

关于怎样计算每个单词的概率

使用p(x1, x2) = p(x1)·p(x2|x1)

NLP的应用场景

Question Answering(问答系统)

语料库-》知识库

问题-》知识库-》答案

Sentiment Analysis(情感分析)

学习如何调参数和如何进行特征提取

  • 股票价格预测
  • 舆情监控
  • 产品评论
  • 事件监测

输入语句-》特征工程-》模型-》情感值

输入语句-》深度学习模型-》情感值

Chatbot(聊天机器人)

  • 闲聊型(Seq2Seq)
  • 任务导向型(意图识别)

Information Extraction(信息抽取)

NLP的最深层领域

  • NER 命名体识别
  • Relation Extraction

NLP的关键技术

Semantic(语义)

NLU:意义理解

是最上层的技术

Syntax(句子结构,语法)

句法分析(讲一个句子分成主谓宾等等内容)

  • 使用CYK算法(和动态规划有关)

依存分析(Depending),分析单词之间有没有潜在的联系性

Morphology(单词)

关注单词层面的技术,如分词、pos(词性识别)、NER(命名体识别)

Phonetics(声音)

这个内容在NLP本身并不重要,但是如果做语音识别就非常有用,在这里不涉及,因此不过多赘述

算法负责度介绍

1
2
3
4
5
6
7
8
int a = 0, b = 0;
for(i = 0; i < N; i++){
a = a + 1;
b = b - a;
}
for(i = 0; i< N/2; i++){
a = a+b;
}

上边这个例子中,因为无论循环的N是多少,其空间只有分配了a和b两个

因此空间复杂度为2个单位的内存空间 = O(1)

而时间复杂度为O(N)

1
2
3
4
5
int a = 0, i = N;
while(i > 0){
a += i;
i /= 2;
}

这个例子中,时间复杂度为O(log2N)

解释:由于I的变化为每次除以2,因此其变化应该为看除以2多少次之后跳出循环,因此使用对数运算

1
2
3
4
5
6
int i, j, k = 0;
for(i = n / 2; i <= n; i++){
for(j = 2; j<= n; j = j * 2){
k = k + n / 2;
}
}

这个例子中时间复杂度为O(N * log2N)

解释:外层循环的时间复杂度为N,内层循环时间复杂度同上一例子,由于嵌套循环,因此应该使用相乘的关系,。

问答:我们每当说算法X的效率要高于Y时指的是?

时间复杂度X要小于Y

但是不代表在相同情况下,X的执行时间一定会小于Y;只能说明在当N足够大的时候,X的执行时间会小于同样情况下Y的执行时间


归并排序(Merge Sort)

数组A = [3,4,1,6,7,2,5,9]

分为两个部分[3,4,1,6]和[2,5,7,9],然后排序,排序后两个数组对比找到相应位置小的放在前边

假设排序数组A的时间复杂度为T(n),那么将其分为两个则每组的复杂度会变成T(n/2)。两组合并时候由于要循环检测一遍之后插入相应的值,因此还应该再加一个复杂度为n。最终:T(n) = 2T(n/2) + n

Master Theorem(主方法)

该页面主方法为课程所讲解内容,如果需要看更详尽的内容可以查看这篇文章:Master Theorem 主定理的相关内容。因此本课程的笔记内容将会被隐藏,您也可以点击下边的箭头来展开该内容

主方法的笔记内容

定理:形如T(n)=aT(n/b)+f(n)的一个形式,即一个方法可以写成若干个子方法所组成时候适用

判断递归形式的复杂度,相当于计算O(nlogba)和f(n)之间的关系,其有着如下的对应关系:

  • O(nlogba) > f(n) => O(nlogba)
  • O(nlogba) = f(n) => O(nlogbalogk+1n)
  • O(nlogba) < f(n) => f(n)

例题

1、T(n) = 3T(n/2) + n2

nlogba = nlog23 ≈ n1.6

f(n) = n2

因此:nlogba ≈ n1.6 < n2 = f(n),即 nlogba < f(n)。此时满足第三种情况,即T(n) = f(n) = O(n2)

2、T(n) = 4T(n/2) + n2

nlogba = nlog24 = n2

f(n) = n2

因此:nlogba = n2 = f(n),即 nlogba = f(n)。此时满足第二种情况,即T(n) = O(nlogbalogk+1n)

在这道题中f(n) = n2 = n2log0n,所以k=0

综上:T(n) = O(nlogbalogk+1n) = O(nlog24log0+1n) = O(n2log n)

3、T(n) = 2T(n/2) + n

此时:a = 2, b = 2

nlogba = nlog22 = n = f(n) => Case 2

在这道题中f(n) = n = n·log0n,所以k=0

综上:T(n) = O(n·log n)

一句话总结:两个相比较,谁大取谁,两个相等时候找一个求出K值带入公式

关于K值得计算方法

T(n) = 2T(n/2) + n·log b

此时:a = 2, b = 2

nlogba = nlog22 = n = f(n) => Case 2

在这道题中f(n) = n·log1n,所以k=1

综上:T(n) = O(n·log2 n)

斐波那契数列(Fibonanci Number)

序列依次为1, 1, 2, 3, 5, 8, 13, 21, …… 问题:如何求出序列中第N个数?

使用尾递归

尾递归版本

1
2
3
4
5
6
def fib(n):
# base case
if(n < 3):
return 1
return fib(n - 2) + fib(n - 1)
print(fib(30))

T(n)=T(n2)+T(n1)T(n) = T(n - 2) + T(n - 1)
T(n)=2nT(n) = 2^n

时间复杂度?O(2n)O(2^n)

解:将树画出来,可以得到第一层为1,第二层为2,第三层为4,第四层为8,……,第n层为2n12^{n-1}

那么如何计算空间复杂度

在运行递归的时候最多是占用N个内存空间,因此空间复杂度为O(N)

斐波那些数列的改进版本

版本1

1
2
3
4
5
6
7
8
import numpy as np
def fib(n):
tmp - np.zeros(n)
tmp[0] = 1
tmp[1] = 1
for i in range(2, n):
tmp[i] = tmp[i - 2] + tmp[i - 1]
return tmp[n - 1]

复杂度O(N),但是占用了无关的内存空间(用空间换时间)

版本2

由于该问题只需要存储前两个值,因此可以从这一点下手进行修改

1
2
3
4
5
6
7
8
def fib(n):
a, b = 1, 1
c = 0
for i in range(2, n):
c = a + b
a = b
b = c
return c

思考题

怎样在O(1)
的时间复杂度夏计算fib(n)?

套公式:——通项公式

这个公式怎样得到?提示:转换成矩阵的连城形式,矩阵连城可以简化(比如使用Matrix Decomposition,矩阵分解)

P vs NP vs NP Hard vs NP Complete

时间复杂度根据复杂度的形式可以分为两类:

  • 指数级复杂度,如:O(pn)O(p^n) ——> 无法解决的问题
    • 对于小型的问题,仍然可以解决
    • Approximate Algorithm(近似算法):不保证获得精确的解,但是是目前为止唯一的解决方法
      • 提出近似算法
      • 指出时间复杂度
      • 给出近似算法最后的解离最优解的距离
    • 使用量子计算机进行计算
  • 多项式复杂度,如:O(np)O(n^p) ——> 可以解决的问题

NP:任意一个问题,可以在多项式复杂度内能够定义出的解是否满足要求,就认为这个判断问题叫做NP问题

问题P ∈ NP

项目:搭建一个简单的智能客服系统

常见问题(FAQ)

1、本课程是线上课程还是线下课程

本课程是线上课程

2、课程有助教吗

每门课程都配备专业助教

3、学习周期是多久啊

通常来讲在3-4个月不等

4、如果不满意可以退款吗

前两周提供无条件退款

5、老师都是什么背景啊

绝大部分都是全美前10学校的博士

6、课程会有考试吗

有的,一般包括其中和期末

7、我只有编程基础,可以报名吗

对于初级的项目班只要求编程基础

8、课程有实操吗

大部分都是实操,动手能力是最重要的

9、课程为什么那么贵

跟别的知识付费不一样,我们会提供很多教学服务,辅助完成学院做完所有的项目

10、课程学完了能做什么

可以找相关岗位的工作问题不大

11、下次期班是什么时候

我们每个月开一期,但价格通常会不断升高

相似度计算

正则方法:最适合在没有任何数据的情况下使用

字符串相似度匹配

给予检索的问答系统

首先需要知识库,即问答一一对应的对

拿到一个问题,首先需要做

  • 分词预处理
  • 预处理
    • 拼写检查和纠错
    • Stemming、Lemmazation(标准化,转换将词的变形换回原形)
    • 停用词的过滤
    • 词语过滤(去除无用内容,如html标签等内容)
    • 使用同义词进行替换
  • 文本表示 -> 将文本转换为向量文本(特征提取)
    • 转换为古典向量
    • 转换为次数的向量
    • 转换为tf-idf方式
    • 转换为词向量形式
    • Seq2Seq
    • ……
  • 计算相似度
    • 计算欧氏距离
    • 计算余弦距离
    • ……
  • 根据相似度进行排序
  • 再做一层过滤
  • 返回结果

问答系统

  • 现代方法
    • 文本表示
    • 相似度计算
  • 知识图谱
    • 实体抽取
    • 关系抽取

NLP项目的识别用Pipeline

  • 原始文本(raw data)
    • 网页文本
    • 新闻
    • 报告
    • ……
  • 分词(Segmentation)
    • 中文 -> ……
    • 英文 -> ……
  • 清洗(Cleaning)
    • 无用的标签,如
    • 特殊符号,如!、……
    • 停用词(Stop Word, a the等)
    • 大写转小写
  • 标准化(Normalization,尤其是英文)(如将apples变成apple,went变成go)
    • Stemming
    • Lemmazation
  • 特征提取(Feature Extraction)(由字符文本变成向量)
    • tf-idf
    • word2vec
  • 建模(Modeling)
    • 相似度算法
    • 分类算法
    • AI等
    • ……
  • 评估

分词(Word Segmentation)

最大匹配(Max Matching)

前项最大匹配

例子:我们经常有意见分歧

词典:[“我们”, “经常”, “有”, “有意见”, “意见”, “分歧”]

分词结果:我们, 经常,有意见,分歧

过程:首先规定一个最大窗口,如max_len = 5,查看是否有最大匹配,如果没有就减小一个字进行匹配查找

  • [我们经常有]意见分歧 ×
  • [我们经常]有意见分歧 ×
  • [我们经]常有意见分歧 ×
  • [我们]经常有意见分歧 √

  • [经常有意见]分歧 ×
  • [经常有意]见分歧 ×
  • [经常有]意见分歧 ×
  • [经常]有意见分歧 √

  • [有意见分歧] ×
  • [有意见分]歧 ×
  • [有意见]分歧 √

  • [分歧] √

后项最大匹配

例子:我们经常有意见分歧

词典:[“我们”, “经常”, “有”, “有意见”, “意见”, “分歧”]

分词结果:我们, 经常,有意见,分歧

过程:首先规定一个最大窗口,如max_len = 5,查看是否有最大匹配,如果没有就减小一个字进行匹配查找

  • [有意见分歧] ×
  • [意见分歧] ×
  • [见分歧] ×
  • [分歧] √

  • [经常有意见] ×
  • [常有意见] ×
  • [有意见] √

  • [我们经常] ×
  • [们经常] ×
  • [经常] √

  • [我们] √

缺点

细分,有可能是更好

只能找到局部最优解而不是全局最优解

效率低

歧义(不能考虑语义

考虑语义(Incorporate Semantic)

假定有一个工具箱可以判断语义的概率

例子:我们经常有意见分歧

词典:[“我们”, “经常”, “有”, “有意见”, “意见”, “分歧”]

输入 -> 生成所有可能的分割 -> 选择其中最好的(工具:Language Model, 即语言模型)

如P(“经常”, “有”, “意见”, “分歧”) = p(“经常”)·p(“有”)·p(“意见”)·p(“分歧”) = 0.3
P(“经常”, “有意见”, “分歧”) = p(“经常”)·p(“有意见”)·p(“分歧”) = 0.35

每个词出现的概率可以提前进行统计,最可靠的统计方式应该是靠人工进行统计

联合概率假象为独立概率连乘

当每一个概率都非常小的时候(10n10^{-n}形式),这个时候需要都换成log形式(logp(N)log {p(N)}形式)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# %%
def segments_value_conts(segments=[[],]):
'''统计词频'''
dict = {}
for segment in segments:
for seg in segment:
dict[seg] = dict.get(seg, 0) + 1
return dict
# %%
def split_word_with_dic_front_max(dic=[], input_str=""):
'''前项最大分词'''
input_str_tmp = input_str
segments = []
while(input_str_tmp!=""):
tmp_length = 0
tmp_dic_content = ""
for word in dic:
# print("单词长度:"+str(len(word))+" === 单词:"+word +"==""=== 划分:"+input_str_tmp[:len(word)])
if(word == input_str_tmp[:len(word)]):
if(tmp_length < len(word)):
tmp_dic_content = word
tmp_length = len(word)
segments.append(tmp_dic_content)
# print(tmp_dic_content)
input_str_tmp = input_str_tmp[tmp_length:]
return segments

# %%

# %%
def split_word_with_dic_front_min(dic=[], input_str=""):
'''前项最小分词'''
input_str_tmp = input_str
segments = []
while(input_str_tmp!=""):
tmp_length = len(input_str)
tmp_dic_content = ""
for word in dic:
# print("单词长度:"+str(len(word))+" === 单词:"+word +"==""=== 划分:"+input_str_tmp[:len(word)])
if(word == input_str_tmp[:len(word)]):
if(tmp_length > len(word)):
tmp_dic_content = word
tmp_length = len(word)
segments.append(tmp_dic_content)
# print(tmp_dic_content)
input_str_tmp = input_str_tmp[tmp_length:]
return segments
# %%
def split_word_with_dic_back_max(dic=[], input_str=""):
'''后项最大分词'''
input_str_tmp = input_str
segments = []
while(input_str_tmp!=""):
tmp_length = 0
tmp_dic_content = ""
for word in dic:
if(word == input_str_tmp[-len(word):]):
if(tmp_length < len(word)):
tmp_dic_content = word
tmp_length = len(word)
segments.append(tmp_dic_content)
input_str_tmp = input_str_tmp[:-tmp_length]
return segments[::-1]
# %%
def split_word_with_dic_back_min(dic=[], input_str=""):
'''后项最小分词'''
input_str_tmp = input_str
segments = []
while(input_str_tmp!=""):
tmp_length = len(input_str)
tmp_dic_content = ""
for word in dic:
if(word == input_str_tmp[-len(word):]):
if(tmp_length > len(word)):
tmp_dic_content = word
tmp_length = len(word)
segments.append(tmp_dic_content)
input_str_tmp = input_str_tmp[:-tmp_length]
return segments[::-1]


# %%
def word_segment_naive(dic, input_str):
"""
1、对于输入字符串做分词,并返回所有可行的分词之后的结果。
2、针对于每一个返回结果,计算句子的概率。
3、返回概率最高的作为最后结果
input_str: 输入字符串 输入格式:"今天天气真好"
"""
# TODO:第一步:计算所有可能的分词结果,要保证每个分完的词存在于字典里,这个结果有可能会非常多。
segments = [] # 存储所有分词的结果。如果此字符串不可能被完全切分,则返回空列表(list)
# 格式为:segments = [["今天", "天气", "好"], ["今天", "天", "气", "好"], ["今", "天", "天气", "好"], ...]
segments.append(split_word_with_dic_front_max(dic, input_str))
segments.append(split_word_with_dic_front_min(dic, input_str))
# TODO:第二步:循环所有的分词结果,并计算出概率最高的分词结果,并返回
best_segment = segments_value_conts(segments)
best_score = max(best_segment)
best_segment = max(best_segment, key=best_segment.get)
return best_segment
# %%
dic = ["我们", "经常", "有", "有意见", "意见", "分歧"]
input_str = "我们经常有意见分歧"
# %%
word_segment_naive(dic, input_str)

1
2
3
4
# 测试
print(word_segment_naive("北京的天气真好啊"))
print(word_segment_naive("今天的课程内容很有意思"))
print(word_segment_naive("经常有意见分歧"))

注:这里由于没有采用大量的字典,所以无法测试部分内容

由于中华文化博大精深,生成的话会出现非常庞大的计算量,需要解决这个问题

如果将生成和选择放在一起而不是分开的话,就会产生一种新的算法

维特比算法(Viterbi)

本质上还是DP算法。

例子:我们经常有意见分歧

词典“经常”“经”“有”“有意见”“意见”“分歧”“见”“意”“见分歧”“分”
概率0.10.050.10.10.20.20.050.050.050.1
log(x)-log(x)2.332.32.31.61.63332.3

// 注: 这里log值添加了一个符号,这样就将寻找最大值变换为寻找最小值

设定其他(没有出现的组合方式)其出现的概率为P(other)=108=20P(other) = 10^{-8} = 20

如上图所示,用如下表示方式

F(8): 从节点1到8的最短路径的值
F(7): 从节点1到7的最短路径的值
F(6): 从节点1到6的最短路径的值

由图可知:

  • P(经常, 有, 意见) > P(经常, 有意见)
  • log p(经常, 有, 意见) > log p(经常, 有意见)
  • -(log p(经常)+log p(有) + log p(意见)) > -(log p(经常)+log p(有意见)

其实这个问题就是动态规划的问题

f(8)=f(5)min+3=10.6f(8) = f(5)_{min} + 3 = 10.6 从第5个节点到第8个节点
f(8)=f(6)min+1.6=6.2f(8) = f(6)_{min} + 1.6 = 6.2 🉑 从第6个节点到第8个节点
f(8)=f(7)min+20=26.9f(8) = f(7)_{min} + 20 = 26.9 从第7个节点到第8个节点

再从上述三个方式中选择最小的一个,再考虑f(7)

由图可知f(7)=f(6)min+2.3=6.9f(7) = f(6)_{min} + 2.3 = 6.9

f(6)=f(3)min+2.3=4.6f(6) = f(3)_{min} + 2.3 = 4.6 🉑 从第3个节点到第6个节点
f(6)=f(4)min+1.6=6.2f(6) = f(4)_{min} + 1.6 = 6.2 从第4个节点到第6个节点
f(6)=f(5)min+3=10.6f(6) = f(5)_{min} + 3 = 10.6 从第5个节点到第6个节点

为了减小使用递归造成的过于庞大的资源开销,这里可以使用动态规划算法进行

需要维护一个数组保存每一个节点之前到达该节点的最短路径权值

f(1)f(2)f(3)f(4)f(5)f(6)f(7)f(8)
032.34.67.64.66.96.2

同样逆推可以得到过来的路径是什么样子的,即上述最短的路径为:经常 -> 有意见 -> 分歧

可以得到index的值为1368,这样就可以据此划分字符串

拼写纠错(Spell Correction)

计算编辑距离(edit distance)

假设通过n个操作可以转换为目标单词

①insert
②delete
③replace

therr:

  • there: ther|r ->e => there: replace x 1 => 1成本
  • their: the|r -> e|r => their: replace x 1 => 1成本
  • thesis: the|r -> s|r -> i|+s => thesis: replace x 2 + insert x 1 => 3成本
  • thesis: the|r -> i|+s => theirs: replace x 1 + insert x 1 => 2成本
  • the: the|r -x> |r -x> | => the: delete x 2 => 2成本

用户输入 -> 从词典中寻找编辑距离最小的 -> 返回

这样的时间复杂度为O(V)·Edit()

可选择的方式(Alternative Way)

用户输入 -> 生成编辑距离为1,2的字符串 -> 过滤 -> 返回

appl:

首先生成编辑距离1的操作:

  • Replace: bppl, cppl, …
  • Add: aappl, bappl, …
  • Delete: ppl, apl, app

上述操作为编辑距离为1的操作,在此操作的基础上再次生成编辑距离为1的操作,此时编辑距离就变成了2

即通过两层循环即可生成编辑距离分别为0, 1, 2的字符串

为什么只生成编辑距离为012的字符串:在实际使用的场景下绝大多数的输入都可以被这样子覆盖到

怎样过滤

定义问题:给定一个字符串s,我们要找出最优可能成为正确的字符串c,也就是c^  =  argmaxccandidatesp(CS)\widehat c\;=\;argmax_{c\in candidates}p(C\vert S)

通过贝叶斯定理可以转化为下式子

c^  =  argmaxccandidatesp(SC)P(C)P(S)\widehat c\;=\;argmax_{c\in candidates}\frac{\displaystyle p(S\vert C)\cdot P(C)}{P(S)}

停用词移除(Stop Words Removal)

停用词:在文档中语句中没有什么实际帮助的词,或者是出现频率非常低的词汇

其过程类似于特征筛选的过程

在英文中,比如"the", “an”, "their"这些词都可以作为停用词来处理。但是,也需要考虑自己的应用场景。

比如在情感分析(Sentiment Analysis)中,“好”、“很好”等词是非常重要的词,不能够被删掉

Stemming(词的标准化操作)

对于英文会常用,但是对于中文并不需要

如goes变成go

但是对于stemming这项技术,还原的时候有可能出现还原后不是一个有效的单词,但是还原出来的非有效单词在计算机中是合法的,并且所有同类单词都会转化为这个单词,如:fly, flies -> fli

规则一般由语言学家进行构建,由程序员逐渐转化为代码表示

参考链接

【邻接表的python实现】: https://www.cnblogs.com/chay/articles/10259422.html

【数据结构:图的存储结构之邻接表】: https://blog.csdn.net/jnu_simba/article/details/8866844

动态规划算法(Dynamic Programming, DP)

核心:

Big Problem => Smaller Problems

  1. 问题目标
  2. 状态的定义:opt[n]
  3. 状态转移方程:opt[n] = best_of(opt[n-1], opt[n-2], …)

最大子序和

目标:

Input: Array A[1…n] of real numbers

输入的是一些数字构成的数组,求一个以j为结束的最大和的子串

做法:

Maxl=ijA[l]Max\displaystyle\sum^j_{l=i}A[l]

子问题:

M(j): max sum overall windows ending at j.

M(j)=max{M(j1)+A[j],a[j]}M(j)=max\{M(j-1)+A[j], a[j]\}

即:当求第j项的时候只需要比较当前项和到其上一项为止的值哪一项更大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxSubArray(self, nums):
'''
:type nums: List[int]
:rtype: int
'''
if len(nums) == 1: return nums[0]
max_ret = nums[0] # 存储最大子串和
cur_max = last_max = nums[0] # 临时:当前和最大
for i in range(1, len(nums)):
if last_max + nums[i] < nums[i]: cur_max = nums[i] # 当前元素和上次+当前
else: cur_max = last_max + num[i] # 当前最大
if cur_max > max_ret: max_ret = cur_max
last_max = cur_max
return max_ret

最长上升子序列

目标:

Input: SequenceA1,...,AnA_1, ..., A_n

Goal: Find a longest strictly increasing sbusequence (not necessarily contiguous).

比如1,3,2,5,1,6。其中最长的子序列为1256,可以跳过一定的数字,但是要找到最长的上升子序列

子问题:

定义的最优解:以j为结尾的最长子串是多少个

L(j): Longest strictly increasing subsequence ending at position j.

L(j)  =  maxA[i]<A[j]i<j{L(i)}+1L(j)\;=\;max_{\underset{i<j}{A[i]<A[j]}}\{L(i)\}+1

1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1: return len(nums) # 判断数组是否异常
mem = [1 for _ in range(len(nums))] # 临时:存储之前的L(j)的过程
for j in range(1, len(nums)):
for i in range(0, j):
if nums[i] < nums[j]:
mem[j] = max(mem[j], mem[i] + 1)
return max(mem)

很多动态规划的问题实际就是树的遍历过程,如果树的深度是N,则可能性为2n2^n

零钱规划

目标:

Input: n denominations of coins of valuesl=v1<v2<v3<...<vnl=v_1<v_2<v_3<...<v_n

Goal: make change for amount of money C. Use as few coins as possible.

子问题:

M(j): minimun # coins required to make change for amount of money j.

给了各种各样面值的硬币,找到最少硬币的组成方式来组成给定数值

M(j)=mini{M(jvi)}+1M(j)=\underset{i}{min}\{M(j-v_i)\}+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0: return 0
if len(coins) == 0: return 01
if len(coins) == 1 and coins[0] > amount: return -1
mem = [-1 for _ in range(amount + 1)] # 建立存储空间并初始化
mem[0] = 0
for i in range(1, amount + 1):
cur_min = amount + 1
for c in coins:
if c <= i: # 当钱币面值小于当前需要凑的金额时
cur_min = mem[i - c] if mem[i - c] < cur_min else cur_min
mem[i] = cur_min + 1 if cur_min < amount + 1 else amount + 1
if mem[-1]==amount + 1: return -1
else: return mem[-1]

0-1背包问题

目标:

Input: n items, with integer sizes si and values vi, knapsack of capacity C.

子问题:

M(i, j): optimal value for filling exactly a capacity j knapsack with some subset of items l…i

M(i,j)=max{M(i1,j),M(i1,jSi)+vi}M(i, j) = max\{M(i-1, j), M(i-1, j-S_i)+v_i\}

假设:

价值数组v = {8, 10, 6, 3, 7, 2}

重量数组w = {4, 6, 2, 2, 5, 1}(可以理解为背包容量)(行)

背包容量C = 12时对应的m[i][j]数组

0123456789101112
1000888888888
20008810101010181818
30668814141616181824
40669914141717191924
50669914141717192124
626891114161719192124

上表中行代表背包容量,列代表考虑的物品数量

1
2
3
4
5
6
7
8
def knapsack(w, v, C):
mem = np.zeros((len(w) + 1, C + 1))
for i in range(1, len(w) + 1):
for j in range(1, C + 1):
if w[i - 1] <= j:
mem[i, j] = max(mem[i, j], mem[i - 1, j], mem[i - 1, j - w[i - 1]] + v[i - 1])
else: mem[i, j] = mem[i - 1, j]
return mem

编辑距离

目标:

Input: strings A[1…n] and B[1…m]

Costs:

  • CiC_i -> insertion
  • CdC_d -> deletion
  • CRC_R -> replacement

Goal: Commpute minimum cost of transforming A -> B.

子问题:

T(i, j): minimum cost to transform A[1…i] into B[1…j]

T(i,j)=min{Cd+T(i1,j)T(i,j1)+Ci{T(i1,j1)if  A[i]=B[j]T(i1,j1)if  A[i]B[j]T(i,j)=min \left\{ \begin{array}{l} C_d+T(i-1,j)\\ T(i,j-1)+C_i\\ \left\{ \begin{array}{lc} T(i-1,j-1)&{if\;A[i]=B[j]}\\ T(i-1,j-1)&{if\;A[i]≠B[j]} \end{array} \right. \end{array} \right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if(word1 == word2): return 0
m, n = len(word1), len(word2)
mem = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): mem[i][0] = i
for i in range(n + 1): mem[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if(word1[i - 1] == word2[j - 1]):
mem[i][j] = min(mem[i - 1][j] + 1, mem[i][j - 1] + 1, mem[i - 1][j - 1], mem[i - 1][j -1] + 1)
else: mem[i][j] = min(mem[i -1] + 1, mem[i][j - 1] + 1, mem[i - 1][j - 1] + 1)
return mem[-1][-1]

文本表示(Word Representation)

词典:[我们, 去, 爬山, 今天, 你们, 昨天, 跑步]

OneHot 独热编码表示

每个单词的表示:

  • 我们: (1, 0, 0, 0, 0, 0, 0) -> 7维度 = |词典|
  • 爬山: (0, 0, 1, 0, 0, 0, 0) -> 7维度 = |词典|
  • 跑步: (0, 0, 0, 0, 0, 0, 1) -> 7维度 = |词典|
  • 昨天: (0, 0, 0, 0, 0, 1, 0) -> 7维度 = |词典|

句子表示(Sentence Representation(bollean))

词典:[我们, 又, 去, 爬山, 今天, 你们, 昨天, 跑步]

基于(bollean)的

一个句子中只要出现就设定为1,

每个句子的表示:

  • 我们 今天 去 爬山:(1, 0, 1, 1, 1, 0, 0, 0) -> 8维 = |词典|
  • 你们 昨天 跑步: (0, 0, 0, 0, 0, 1, 1, 1) -> 8维 = |词典|
  • 你们 又 去 爬山 又 去 跑步:(0, 1, 1, 1, 0, 1, 0, 1) -> 8维 = |词典|

基于(count)的

相比于Bollean方法,这个方法增加了统计

每个句子的表示:

  • 我们 今天 去 爬山:(1, 0, 1, 1, 1, 0, 0, 0) -> 8维 = |词典|
  • 你们 昨天 跑步: (0, 0, 0, 0, 0, 1, 1, 1) -> 8维 = |词典|
  • 你们 又 去 爬山 又 去 跑步:(0, 2, 2, 1, 0, 1, 0, 1) -> 8维 = |词典|

文本相似度计算(Sentence Similarity)

计算欧式距离(即两个向量之间的距离)

计算距离(欧氏距离):d=S1S2=(x1y1)2+(x2y2)2+(x3y3)2d = |S_1 - S_2| = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + (x_3-y_3)^2}

  • S1: “我们 今天 去 爬山” =(1, 0, 1, 1, 1, 0, 0, 0) -> 8维 = |词典|
  • S1: “你们 昨天 跑步” = (0, 0, 0, 0, 0, 1, 1, 1) -> 8维 = |词典|
  • S1: “你们 又 去 爬山 又 去 跑步” = (0, 2, 2, 1, 0, 1, 0, 1) -> 8维 = |词典|

d(S1,S2)=12+12+12+12+12+12=6d(S_1, S_2) = \sqrt{1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2} = \sqrt 6

d(S1,S3)=12+22+12+12+12=8d(S_1, S_3) = \sqrt{1^2 + 2^2 + 1^2 + 1^2 + 1^2} = \sqrt 8

d(S2,S3)=22+22+12+12=10d(S_2, S_3) = \sqrt{2^2 + 2^2 + 1^2 + 1^2} = \sqrt 10

Sim(S1,S2)>Sim(S2,S3)Sim_{(S_1, S_2)} > Sim_{(S_2, S_3)}

Sim(S1,S3)>Sim(S2,S3)Sim_{(S_1, S_3)} > Sim_{(S_2, S_3)}

计算余弦相似度(Cosine Similarity)

余弦相似度既可以表示方向,又可以表示大小

计算距离(余弦相似度):d=S1S2(S1S2)=x1y1+x2y2+x3y3x12+x22+x32y12+y22+y32d = \frac{S_1 \cdot S_2}{(|S_1| * |S_2|)} = \frac{x_1y_1 + x_2y_2 + x_3y_3}{\sqrt{x_1^2 + x_2^2 + x_3^2} \sqrt{y_1^2 + y_2^2 + y_3^2}}

d(S1,S2)=0A=0d(S_1, S_2) = \frac{0}{A} = 0

d(S1,S3)=(2+1)311=333d(S_1, S_3) = \frac{(2+1)}{\sqrt{3}\cdot\sqrt{11}}=\frac{3}{\sqrt{33}}

d(S2,S3)=(2)311=233d(S_2, S_3) = \frac{(2)}{\sqrt{3}\cdot\sqrt{11}}=\frac{2}{\sqrt{33}}

余弦相似度越大,相关性越好,因此:Sim(S1,S3)>Sim(S2,S3)>Sim(S1,S2)Sim_{(S_1, S_3)} > Sim_{(S_2, S_3)} > Sim_{(S_1, S_2)}

注:并不是出现的越多就越重要,也并不是出现的越少就越不重要(如主语在句子中并不是非常重要,但是有可能会出现多次)

说明上述表示方法有所缺陷

TF-IDF方法

这种方法解决了上述方法的问题:解决了表示次数多的词有可能并不重要这个问题

tfidf(w)=tf(d,w)idf(w)tfidf(w)=tf(d, w) * idf(w)

文档d中w的词频

idf(w)=logNN(w)idf(w) = log\frac{N}{N(w)}, 指的是考虑单词的重要性

N:语料库中的文档总数
N(w): 词语w出现在多少个文档中

举例

定义词典

词典:[今天, 上, NLP, 课程, 的, 有, 意思, 数据, 也] (9个单词)

句子转换为tfidf向量

句子1:今天 上 NLP 课程
句子2:今天 的 课程 有 意思
句子3:数据 课程 也 有 意思

句子1:1log(32),1log(31),1log(31),1log(33),0,0,0,0,0)(1·log(\frac{3}{2}), 1·log(\frac{3}{1}), 1·log(\frac{3}{1}), 1·log(\frac{3}{3}), 0, 0, 0, 0, 0) =(log(32),log3,log3,log1,0,0,0,0,0)(log(\frac{3}{2}), log3, log3, log1, 0, 0, 0, 0, 0) => 9维 = |词典|

句子2:1log(32),0,0,1log(33),1log(31),1log(32),1log(32),0,0)(1·log(\frac{3}{2}), 0, 0, 1·log(\frac{3}{3}), 1·log(\frac{3}{1}), 1·log(\frac{3}{2}), 1·log(\frac{3}{2}), 0, 0) =(log(32),0,0,log1,log3,log32,log32,0,0)(log(\frac{3}{2}), 0, 0, log1, log3, log\frac{3}{2}, log\frac{3}{2}, 0, 0) => 9维 = |词典|

句子3:0,0,0,1log(33),0,1log(32),1log(32),1log(31),1log(31))(0, 0, 0, 1·log(\frac{3}{3}), 0, 1·log(\frac{3}{2}), 1·log(\frac{3}{2}), 1·log(\frac{3}{1}), 1·log(\frac{3}{1})) =(0,0,0,log1,0,log(32),log(32),log3,log3)(0, 0, 0, log1, 0, log(\frac{3}{2}), log(\frac{3}{2}), log3, log3) => 9维 = |词典|

词向量

OneHot表示方法的缺点:不能表示语义相似度,并且过于稀疏

OneHot表示方法到分布式表示方法

WordsOneHot RepresentationDistributed Representation
我们[1, 0, 0, 0, 0, 0, 0][0.1, 0.2, 0.4, 0.2]
爬山[0, 0, 1, 0, 0, 0, 0][0.2, 0.3, 0.7, 0.1]
运动[0, 0, 0, 0, 0, 0, 1][0.2, 0.3, 0.6, 0.2]
昨天[0, 0, 0, 0, 0, 1, 0][0.5, 0.9, 0.1, 0.3]
长度|词典长度|可自定义(100, 200, …)

特点:

  • 长度不依赖于词典
  • 向量中每一个位置都有一个非零的数值

假设将每一个单词都表示为一个思维的响亮

我们:[0.1, 0.2, 0.4, 0.2]
爬山:[0.2, 0.3, 0.7, 0.1]
运动:[0.2, 0.3, 0.6, 0.2]
昨天:[0.5, 0.9, 0.1, 0.3]

①欧式距离

d(我们, 爬山) =0.12+0.12+0.32+0.12=0.01+0.01+0.09+0.01=0.12\sqrt{0.1^2+0.1^2+0.3^2+0.1^2}=\sqrt{0.01+0.01+0.09+0.01}=\sqrt{0.12}

d(运动, 爬山) =0.12+0.12=0.02\sqrt{0.1^2+0.1^2}=\sqrt{0.02}

∴ d(运动, 爬山) < d(我们, 爬山)
∴ sim(运动, 爬山) > sim(我们, 爬山)

分布式表示方法是针对于单词的也可以叫做词向量(Word Vectors)

QNA

Q: 100维的OneHot表示法最多可以表达多少个不同的单词?

向量大小 = 100

我们 = (1, 0, …, 0)
运动 = (0, 0, …1, 0, …, 0)

因此最多可以表达100个单词

Q: 100维的分布式表示法最多可以表达多少个不同的单词?

我们 = (0.1, 0.2, 0.15, …)

理论上可以表达无穷个。。即使限制了每个位置仅允许0/1,那么也可以有21002^{100}个单词

如何学习词向量

学习词嵌入(Learn Word Embeddings)

对于输入非常多(如10~100Billions)的时候,可以将其拼接在一起,然后进行训练

训练词向量可以用深度学习模型(如:Skip-Gram、Glove、CBow、RNN/LSTM、MF)

训练的时候有一个最重要的参数:dim/D(即训练维度)

由于训练维度和时间空间等资源消耗是非常非常大的,所以可以使用现有第三方的词向量

词嵌入的本质(Essence of Word Embedding)

词向量代表单词的意思(Meaning)

简单可以理解为:词向量在某种意义(理想情况下)上可以理解为此的意思

由词嵌入表达句子嵌入(From Word Embedding to Esentence Embedding)

例如

  • 我们: (0.1, 0.2, 0.1, 0.3)
  • 去: (0.3, 0.2, 0.15, 0.2)
  • 运动: (0.2, 0.15, 0.4, 0.7)

由上述词向量表达句子“我们去运动”

方法①Averging法则

对应位相加求平均得到(0.2, 0.18, 0.22, 0.4)

可以认定为句子“我们去运动”的向量为:(0.2, 0.18, 0.22, 0.4)

计算句子的相似度可以计算不同句子向量的余弦距离和欧式距离

倒排表

基于检索的知识问答库系统

首先需要一个知识库,包括问题和对应答案的知识库

每当用户提出问题之后,系统对问题进行处理,然后返回相似度最高的问题和回答

复杂度为:O(N)·每次相似度计算复杂度

如何降低复杂度?

核心思路:“层次过滤思想”(遇到一个问题可以通过层层减小的方式进行递减)

使用多层过滤器依次减小数量级

要求复杂度(过滤器1)< 复杂度(过滤器2)< …

介绍倒排表(Introducing Inverted Index)

假设4个文档

  • Doc1:我们,今天,运动
  • Doc2:我们昨天运动
  • Doc3:你们上课
  • Doc4你们上什么课

词典:[我们, 今天, 运动, 昨天, 上, 课, 什么]

我们:[Doc1, Doc2]
今天:[Doc1]
运动:[Doc1, Doc2]
昨天:[Docq2]
上:[Doc3, Doc4]
课:[Doc3, Doc4]
什么:[Docq2]

例如检索内容为“运动”,此时应返回[Doc1, Doc2]

使用倒排表之后先对问答库进行构建来抽取关键词

对输入的问题进行分词,在倒排表中寻找关键词相关的问题,然后再计算相似度查找最相关的内容

语言模型

Noisy Channel Model

p(text|source)∝P(source|text)p(text) (∝,正比于,propostional)

应用场景:语音识别,机器翻译,拼写纠错,OCR,密码破解(共同点:将一个信号转换为文本模式)

机器翻译

假设: 英文翻译为中文

P(中文|英文)∝P(英文|中文)·P(中文)

P(英文|中文) => 翻译模型(Translation Model)
P(中文) => 语言模型(LM)

拼写纠错(Spell-correction)

P(正确的写法|错误的写法)∝P(错误的写法|正确的写法)·P(正确的写法)

查找编辑距离(找到正确写法和错误写法的距离)

对于错误的写法可以采取完全枚举的方式进行

错误的输入:S

正确的写法:C

目标函数:P(C|S)

Max{P(C|S)}

语音识别

输入是波形(语音信号) -》 输出是 文本

P(文本|语音信号)∝ P(语音信号|文本)·P(文本)

P(语音信号|文本) =》 翻译、记录模型

P(文本) =》 语言模型(LM)

密码破解

输入是加密后的字符串

P(明文|加密后)∝ P(加密后|明文)·P(明文)

需要保证用于转化的语言模型转化后一定要符合一定的规则

语言模型(Language Model)

语言模型用来判断:是否一句话从语法上通顺

比较:

  • 今天是周日 VS 今天周日是
  • 全民AI是趋势 VS 趋势全民AI是

模型是已经训练好的

语言模型的目标

Compute the probability of a sentence or sequence of words.p(s)=p(w1,w2,w3,w4,w5,...,wn)p(s) = p(w_1, w_2, w_3, w_4, w_5, ..., w_n)

Chain Rule

功能:将联合概率分布通过条件概率方式表达

p(A,B,C,D)=P(A)P(BA)P(CAB)P(DABC)=P(A,B)P(CA,B)P(DABC)=P(ABC)P(DABC)=P(ABCD)p(A, B, C, D) = P(A)\cdot P(B|A)\cdot P(C|A\cdot B)\cdot P(D|A\cdot B\cdot C) \\=P(A, B)\cdot P(C|A, B)\cdot P(D|A\cdot B\cdot C)\\=P(A\cdot B\cdot C)\cdot P(D|A\cdot B\cdot C) \\= P(A\cdot B\cdot C\cdot D)

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w1w2)p(w4w1w2w3)p(w5w1w2w3w4)...p(wnw1w2...wn1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_1w_2)\cdot p(w_4|w_1w_2w_3)\cdot p(w_5|w_1w_2w_3w_4)...\cdot p(w_n|w_1w_2...w_{n-1})

p(,,,,,)=p()p()p(,)p(,,)p(,,,)p(,,,,)p(今天, 是, 春节, 我们, 都, 休息)\\=p(今天)\cdot p(是|今天)\cdot p(春节|今天, 是)\cdot p(我们|今天, 是, 春节)\cdot p(都|今天, 是, 春节, 我们)\cdot p(休息|今天, 是, 春节, 我们, 都)

语言模型的概率可通过ChainRule来计算出来

那么如何计算条件概率呢?

假设有一个文档,其中有一句话“今天是春节我们都休息”、“今天是春节我们都放假”

要扫描整个文档,找到“今天是春节我们都”这句话,然后查看后边是什么词,对于上述的例子有“春节”和“放假”。。因此知道p(,,,,)=12p(休息|今天, 是, 春节, 我们, 都)=\frac{1}{2}

但是这句话过长,因此不容易找到,这个问题就叫做稀疏性问题(sparsity),而且语料库不一定能找得到

马尔科夫假设(Markov Assumption)

First Order Markov Assumption

p(,,,,)p()p(休息|今天, 是, 春节, 我们, 都)\\≈p(休息|都)

举例:电商网站
只推荐举例最近的物品

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2)p(w4w3)p(w5w4)...p(wnwn1)=p(w1)i=2np(wiwi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2)\cdot p(w_4|w_3)\cdot p(w_5|w_4)...\cdot p(w_n|w_{n-1})\\\displaystyle=p(w_1)\cdot\prod^{n}_{i=2}{p(w_i|w_{i-1})}

Second Order Markov Assumption

p(,,,,)p(,)p(休息|今天, 是, 春节, 我们, 都)\\≈p(休息|我们, 都)

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2w1)p(w4w3w2)p(w5w4w3)...p(wnwn1wn2)=p(w1)p(w2w1)i=3np(wiwi2wi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2w_1)\cdot p(w_4|w_3w_2)\cdot p(w_5|w_4w_3)...\cdot p(w_n|w_{n-1}w_{n-2})\\\displaystyle=p(w_1)\cdot p(w_2|w_1)\cdot\prod^{n}_{i=3}{p(w_i|w_{i-2}w_{i-1})}

Third Order Markov Assumption

p(,,,,)p(,,)p(休息|今天, 是, 春节, 我们, 都)\\≈p(休息|春节, 我们, 都)

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2w1)p(w4w3w2w1)p(w5w4w3w2)...p(wnwn1wn2wn3)=p(w1)p(w2w1)p(w3w2w1)i=4np(wiwi3wi2wi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2w_1)\cdot p(w_4|w_3w_2w_1)\cdot p(w_5|w_4w_3w_2)...\cdot p(w_n|w_{n-1}w_{n-2}w_{n-3})\\\displaystyle=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2w_1)\cdot\prod^{n}_{i=4}{p(w_i|w_{i-3}w_{i-2}w_{i-1})}

语言模型(LM, Use 2nd Order)

p()=0.01p()=0.002p()=0.001p()=0.0001p()=0.02p()=0.0002p(是|今天)=0.01\\ p(今天)=0.002\\ p(周日|是)=0.001\\ p(周日|今天)=0.0001\\ p(周日)=0.02\\ p(是|周日)=0.0002

比较:今天是周日 VS 今天周日是

PLM()=p()p()p()=0.0020.010.001=2×108P_{LM}(今天是周日)\\=p(今天)\cdot p(是|今天)\cdot p(周日|是)\\=0.002\cdot0.01\cdot0.001\\=2\times10^{-8}

PLM()=p()p()p()=0.0020.00010.0002=4×1010P_{LM}(今天周日是)\\=p(今天)\cdot p(是|周日)\cdot p(周日|今天)\\=0.002\cdot0.0001\cdot0.0002\\=4\times10^{-10}

PLM()>PLM()P_{LM}(今天是周日) > P_{LM}(今天周日是)

因此可以判断概率前者大于后者

语言模型(Language Model)

Unigram(联合概率)

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2)p(w3)...p(wn)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2)\cdot p(w_3)...p(w_n)

p(,,,,,)=p()p()p()p()p()p()p(今天, 是, 春节, 我们, 都, 休息)\\=p(今天)\cdot p(是)\cdot p(春节)\cdot p(我们)\cdot p(都)\cdot p(休息)

p(,,,,,)=p()p()p()p()p()p()p(今天, 春节, 是, 都, 我们, 休息)\\=p(今天)\cdot p(春节)\cdot p(是)\cdot p(都)\cdot p(我们)\cdot p(休息)

一个好的语言模型,要可以为第二句赋值比第三句赋值要大很多

Bigram

来自于First Order Markov Assumption

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2)...p(wnwn1)=p(w1)i=2np(wiwi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2)...p(w_n|w_{n-1})\\=p(w_1)\cdot\displaystyle\prod^{n}_{i=2}{p(w_i|w_{i-1})}

p(,,,,,)=p()p()p()p()p()p()p(今天, 是, 春节, 我们, 都, 休息)\\=p(今天)\cdot p(是|今天)\cdot p(春节|是)\cdot p(我们|春节)\cdot p(都|我们)\cdot p(休息|都)

p(,,,,,)=p()p()p()p()p()p()p(今天, 春节, 是, 都, 我们, 休息)\\=p(今天)\cdot p(春节|今天)\cdot p(是|春节)\cdot p(都|是)\cdot p(我们|都)\cdot p(休息|我们)

这种模型相比于Unigram的方式考虑了两个单词之间的关系

N-gram

更高阶的语言模型统称

这里假设N为3

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2w1)...p(wnwn2wn1)=p(w1)p(w2w1)i=3np(wiwi2wi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2w_1)...p(w_n|w_{n-2}w_{n-1})\\=p(w_1)\cdot p(w_2|w_1)\cdot\displaystyle\prod^{n}_{i=3}{p(w_i|w_{i-2}w_{i-1})}

p(,,,,,)=p()p()p(,)p(,)p(,)p(,)p(今天, 是, 春节, 我们, 都, 休息)\\=p(今天)\cdot p(是|今天)\cdot p(春节|是, 今天)\cdot p(我们|是, 春节)\cdot p(都|我们, 春节)\cdot p(休息|都, 我们)

p(,,,,,)=p()p()p(,)p(,)p(,)p(,)p(今天, 春节, 是, 都, 我们, 休息)\\=p(今天)\cdot p(春节|今天)\cdot p(是|今天, 春节)\cdot p(都|春节, 是)\cdot p(我们|是, 都)\cdot p(休息|都, 我们)

评估语言模型的概率(Estimating Probability)

Unigram

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2)p(w3)...p(wn)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2)\cdot p(w_3)...p(w_n)

那么如何计算每一个概率?

在语料库中进行统计,统计每个词出现的次数

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

V = 19(单词总数)

PLM()=PLM()PLM()PLM()PLM()=219119119119=2194P_{LM}(今天 开始 训练营 课程)\\=P_{LM}(今天)\cdot P_{LM}(开始)\cdot P_{LM}(训练营)\cdot P_{LM}(课程)\\=\frac{2}{19}\cdot\frac{1}{19}\cdot\frac{1}{19}\cdot\frac{1}{19}=\frac{2}{19^4}

PLM()=PLM()PLM()PLM()PLM()=219019119119=0P_{LM}(今天 没有 训练营 课程)\\=P_{LM}(今天)\cdot P_{LM}(没有)\cdot P_{LM}(训练营)\cdot P_{LM}(课程)\\=\frac{2}{19}\cdot\frac{0}{19}\cdot\frac{1}{19}\cdot\frac{1}{19}=0

如第二句,“没有”这个词没有出现在语料库中,整个句子虽然语句通顺,但是其结果却为0

欲解决这个问题,可以采用一种平滑算法

Bigram

p(w1,w2,w3,w4,w5,...,wn)=p(w1)p(w2w1)p(w3w2)...p(wnwn1)=p(w1)i=2np(wiwi1)p(w_1, w_2, w_3, w_4, w_5, ..., w_n)\\=p(w_1)\cdot p(w_2|w_1)\cdot p(w_3|w_2)...p(w_n|w_{n-1})\\=p(w_1)\cdot\displaystyle\prod^{n}_{i=2}{p(w_i|w_{i-1})}

那么如何计算每一项的概率呢?

在语料库中搜索相应的单词,然后找出现相应组合的概率的大小

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

PLM()=PLM()PLM()PLM()PLM()PLM()=21912111211=138P_{LM}(今天 上午 想 出去 运动)\\=P_{LM}(今天)\cdot P_{LM}(上午|今天)\cdot P_{LM}(想|上午)\cdot P_{LM}(出去|想)\cdot P_{LM}(运动|出去)\\=\frac{2}{19}\cdot\frac{1}{2}\cdot\frac{1}{1}\cdot\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{38}

PLM()=PLM()PLM()PLM()PLM()PLM()PLM()=0P_{LM}(今天 上午 的 天气 很好 呢)\\=P_{LM}(今天)\cdot P_{LM}(上午|今天)\cdot P_{LM}(的|上午)\cdot P_{LM}(天气|的)\cdot P_{LM}(很好|天气)\cdot P_{LM}(呢|很好)\\=0

N-gram

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

V = 19(单词总数)

PLM()=PLM()PLM()PLM(,))PLM(,)=2191191211=1192P_{LM}(今天 上午 有 课程)\\=P_{LM}(今天)\cdot P_{LM}(上午|今天)\cdot P_{LM}(有|今天, 上午))\cdot P_{LM}(课程|上午, 有)\\=\frac{2}{19}\cdot\frac{1}{19}\cdot\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{19^2}

PLM()=PLM()PLM()PLM(,)PLM(,)=0P_{LM}(今天 没有 训练营 课程)\\=P_{LM}(今天)\cdot P_{LM}(没有|今天)\cdot P_{LM}(训练营|今天, 没有)\cdot P_{LM}(课程|没有, 训练营)\\=0

这种方法并不合理,一旦出现一个概率为0,那个整个句子的概率就是0

评估语言模型(Evaluation of Language Model)

Q: 训练出来的语言模型效果好坏?

  • 理想情况下
    1. 假设有两个语言模型A, B
    2. 选定一个特定的任务比如拼写纠错
    3. 吧两个模型A, B都应用在此任务中
    4. 最后比较准确率,从而判断A, B的表现

核心思路:

使用预测的方式来评估一个语言模型的准确性

Perplexity(混乱、困惑)

对于无监督的学习方式很多都会使用这种方式

Perplexity=2(x)Perplexity = 2^{-(x)}

x: anerage log likelihood(平均可信度)

好的语言模型其x会越大,加上负数之后就会变小

因此对于perplexity越小,LM约好

举例:

训练好的Bigram

p()=0.01p()=0.02p()=0.1p()=0.01p()=0.02p()=0.1p(天气|今天)=0.01\\ p(今天)=0.02\\ p(很好|天气)=0.1\\ p(适合|很好)=0.01\\ p(出去|适合)=0.02\\ p(运动|出去)=0.1

计算:

题目概率(likelihood)AverageLog(likelihood)
今天P()=0.002P(今天)=0.002logP()=a1log {P(今天)}=a_1
今天天气P()=0.01P(天气\|今天)=0.01logP()=2log P(天气\|今天)=-2
今天天气很好P()=0.1P(很好\|天气)=0.1logP()=1log P(很好\|天气)=-1
今天天气很好,适合P()=0.01P(适合\|很好)=0.01logP()=2log P(适合\|很好)=-2
今天天气很好,适合出去P()=0.02P(出去\|适合)=0.02logP()=a2log P(出去\|适合)=a_2
今天天气很好,适合出去运动P()=0.1P(运动\|出去)=0.1logP()=1log P(运动\|出去)=-1

由上表可以计算出

x=a1212+a216x = \frac{a_1-2-1-2+a_2-1}{6}

再带入Perplexity的公式得到

Training 38 million words, test 1.5 million words, WSJ

N-gram OrderUnigramBigramTrigram
Perplexity962170109

Recap

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

仍然采用Bigram模型

PLM()=PLM()PLM()PLM()=0P_{LM}(今天 训练营 没有)\\=P_{LM}(今天)\cdot P_{LM}(训练营|今天)\cdot P_{LM}(没有|训练营)\\=0

PLM()=PLM()PLM()PLM()PLM()=0P_{LM}(今天 没有 训练营 课程)\\=P_{LM}(今天)\cdot P_{LM}(没有|今天)\cdot P_{LM}(训练营|没有)\cdot P_{LM}(课程|训练营)\\=0

平滑(Smoothing)

拉普拉斯平滑(Add-one Smoothing)

PMLE(wiwi1)=c(wi1,wi)c(wi)P_{MLE}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)}{c(w_i)} (最大似然方法)

即便分子位出现0,也不能使概率为零,可以改进为下边的方法

PAdd1(wiwi1)=c(wi1,wi)+1c(wi)+VP_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+1}{c(w_i)+V}

其中V是所有词的出现的概率

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

V词典库大小为17(排除掉重复的单词)

PAdd1(wiwi1)=c(wi1,wi)+1c(wi)+VP_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+1}{c(w_i)+V}

PAdd1()=2+12+17=319PAdd1()=0+12+17=119PAdd1()=0+12+17=119P_{Add-1}(上午|今天)=\frac{2+1}{2+17}=\frac{3}{19}\\P_{Add-1}(的|今天)=\frac{0+1}{2+17}=\frac{1}{19}\\P_{Add-1}(天气|今天)=\frac{0+1}{2+17}=\frac{1}{19}

(Add-K Smoothing)

这种情况可以理解为Add-one是Add-K的一个特例

举例:

语料库:今天 的 天气 很好 啊 我 很 想 出去 运动 但 今天 上午 有 课程 训练营 明天 才 开始

V词典库大小为17(排除掉重复的单词)

PAdd1(wiwi1)=c(wi1,wi)+kc(wi)+kVP_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+k}{c(w_i)+kV}

k可以理解为模型的一种超参数

在这里令k=3

PAdd1()=2+32+317=553PAdd1()=0+32+317=353PAdd1()=0+32+317=353P_{Add-1}(上午|今天)=\frac{2+3}{2+3\cdot17}=\frac{5}{53}\\P_{Add-1}(的|今天)=\frac{0+3}{2+3\cdot17}=\frac{3}{53}\\P_{Add-1}(天气|今天)=\frac{0+3}{2+3\cdot17}=\frac{3}{53}

如何优化k

①k=1, 2, 3, …, 100
②优化f(k)…

假设有一个在训练集上训练好的语言模型,将训练好的语言模型来应用在验证集语料库然后计算perplexity=f(k)

因此:

MinimizePerplexity<==>minimizef(k)<==>k^=argminkf(k)Minimize Perplexity <==> minimize f(k) <==> \hat{k}=argmin_k f(k)

(Interpolation Smoothing)

语料库的结果
C(inthekitchen)=0C(thekitchen)=3C(kitchen)=4C(arboretum)=0C(in the kitchen) = 0\\ C(the kitchen) = 3\\ C(kitchen) = 4\\ C(arboretum) = 0, C代表count

求得
{p(kitchenin  the)=0p(arboretumin  the)=0\left\{ \begin{array}{l} p(kitchen|in\;the)=0\\ p(arboretum|in\;the)=0 \end{array} \right.

核心思路

在计算Trigram概率时同时考虑Unigram,Bigram,Trigram出现的频次

最简单的方法,好的方法给到更多的权重,不靠谱的方法给最简单的权重

p(wnwn1,wn2)=λ1p(wnwn1,wn2)+λ2p(wnwn1)+λ3p(wn)p(w_n|w_{n-1}, w_{n-2})=\\\lambda_1p(w_n|w_{n-1}, w_{n-2})\\+\lambda_2p(w_n|w_{n-1})\\+\lambda_3p(w_n)

其中λ1+λ2+λ3  =  1\lambda_1+\lambda_2+\lambda_3\;=\;1

(Good-Turning Smoothing)

假设在钓鱼,已经钓到18条🐟<・)))><<
10条鲤鱼,3条黑鱼,2条刀鱼,1条鲨鱼,1条草鱼,1条鳗鱼

Q1:下一个钓到的是鲨鱼的概率是多少
A1:1/18

Q2:下一条鱼是新鱼种的高绿是多少
A2:3/18

Q3:既然如此,下一条鱼钓到鲨鱼的概率是多少
A3:结果 < 1/18

定义NcN_c,代表出现c词的单词的个数
例:Sam I am I am Sam I do not eat

N3=1N_3 = 1 (有多少个出现3次的单词)
N2=3N_2 = 3
N1=3N_1 = 3

没有出现过的单词

PMLE=0P_{MLE} = 0
PGT=N1NP_{GT} = \frac{N_1}{N}

PMLE()=018=0P_{MLE}(飞鱼) = \frac{0}{18} = 0
PGT()=N1N=318=16P_{GT}(飞鱼) = \frac{N_1}{N} = \frac{3}{18} = \frac{1}{6}

出现过的单词

PMLE=cNP_{MLE} = \frac{c}{N}
PGT=(c+1)Nc+1NcP_{GT} = \frac{(c+1)N_{c+1}}{N_c}

PMLE()=118P_{MLE}(草鱼) = \frac{1}{18}
PGT()=(1+1)N1+1N1N=21318=127P_{GT}(飞鱼) = \frac{(1+1)N_{1+1}}{N_1\cdot N} = \frac{2\cdot 1}{3\cdot18}=\frac{1}{27}

缺点

计算前一项的时候是依赖后一项的次数,但是对于最多一项的时候没有更多一项,所以不知道该如何计算

解决方式:利用机器学习的非线性回归模型拟合前面的点,然后计算最后一些点

利用语言模型生成句子Use Language Model to Generate Sentence

生成模型:利用训练好的模型可以生产成本一种新的数据

Unigram Model

NLPIlikestudyingcourseyesterday
0.10.30.20.20.350.05

(I, studying, NLP, course, I, yesterday)

(I, like, studying, NLP)

Bigram Model

生成的是一个7*7的矩阵。

NLPIlikestudyingcourseyesterday
NLP0.0010.0010.010.010.9890.001-
I0.010.0010.950.010.010.099-
like0.4000.50.10-
studying0.3---0.40.2-
course-----0.95-
yesterday------0.99
-------

使用上述矩阵

(I, like, studying, course, yesterday, .)

每次找到规律最大的即可

学习 Learning

根据拥有的数据量不同,应当选择不同的系统

当没有数据或者仅有很少量数据的时候 => 专家系统
当数据量非常多或者有海量数据的时候 => 概率统计的系统

专家系统

专家系统 = 推理引擎 + 知识 (类似于程序 = 数据结构 + 算法)

  • 利用知识和推理来解决决策问题(Decision Making Problem)
  • 全球第一个专家系统叫做DENDRAL,由斯坦福大学学者开发与70年代

专家系统工作流(Expert System’s Working Flow)

知识是专家系统中最核心的部分

由专家输出相应领域的经验

专家系统的特点(Properties of Expert Systems)

  • 处理不确定性
  • 知识可以表示
  • 可解释性
  • 可以做知识推理

专家系统的缺点(Drawbacks of Expert Systems)

  • 需要设计大量的规则(Design Lots of Rules)
  • 需要领域专家来主导(Heavily Reeply on Domain Expert)
  • 可移植性差(Limited Transferablity to other Domain)
  • 学习能力差(Inability to Learn)
  • 人能考虑的范围是有限的(Human Capacity is Limited)

机器学习(ML)

定义:自动从已有的数据中找出一些规律,然后把学到的这些规律应用到对未来数据的预测中,或者在不确定的环境下自动地做一些决策。

机器学习分类:生成模型和判别模型

  • 生成模型:可以用来生成一些数据 联合概率训练

  • 判别模型:可以做一些数据的分类 条件概率训练

  • 监督学习:提前知道标签

  • 无监督学习:不知道分类

监督学习(Supervised Learning)无监督学习(Unsupervised Learning)
生成模型(Generative Model)朴素贝叶斯(Naïve Bayes)HMM(语音识别)、LDA、GMM
判别模型(Discriminative Model)逻辑回归(Logistic )、CRF模型不存在

监督学习和无监督学习

监督学习算法(Supervised Learning Algorithms)

  • 线性回归(Linear Regression)
  • 逻辑回归(Logistic Regression)
  • 朴素贝叶斯(Naïve Bayes)
  • 神经网络(Neural Network)
  • SVM(Support Vector Machine)
  • 随机森林(Random Forest)
  • Adaboost
  • CNN(Convolutional Neural Network)

无监督学习算法(Unsupervised Learning Algorithms)

  • K-means
  • PCA(Principal Component Analysis)
  • ICA(Independent Component Analysis)
  • MF(Matrix Factorization)
  • LSA(Latent Semantic Analysis)
  • LDA(Latent Dirichlet Allocation)

生成模型和判别模型

用猫狗大战举例子,生成模型需要记住猫和狗的全部特征,每次做判别的时候只需要做简单比较即可判别猫和狗的概率是多少。

而判别模型只是记住了猫和狗的区别在哪里。

生成模型相当于最大化P(x)和P(XY)函数,而判别模型相当于条件概率模型P(y|x)

搭建模型

数据 -> 清洗数据 -> 特征工程☆ -> 建模 -> 预测

Naive Bayes(朴素贝叶斯)

条件独立:x和y条件独立于z,则有P(x,yz)=p(xz)p(yz)P(x,y|z)=p(x|z)\cdot p(y|z)

参考

关于聊天机器人、LSTM、RNN等概念的理解的最棒的参考来源如下

https://cloud.tencent.com/developer/article/1150386 (非常简明易懂!!五星推荐)