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

NLP=NLU+NLG

NLU：通过文本理解含义（语义理解）
NLG：语义生成

为什么NLP比计算机视觉（CV）？

一个意思有多个表达方式
一词多义（Ambiguity）

如何解决Abiguity：参考上下文（content）

案例：机器翻译

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

如何保证语法通顺

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

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

如何避免这个问题呢？(这里希望降低时间复杂度)
能不能同时考虑两个问题一起（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(x₁, x₂) = p(x₁)·p(x₂|x₁)

NLP的应用场景

Question Answering(问答系统)

语料库-》知识库

问题-》知识库-》答案

Sentiment Analysis（情感分析）

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

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

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

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

Chatbot（聊天机器人）

闲聊型（Seq2Seq）
任务导向型（意图识别）

Information Extraction（信息抽取）

NLP的最深层领域

NER 命名体识别
Relation Extraction

NLP的关键技术

Semantic（语义）

NLU：意义理解

是最上层的技术

Syntax（句子结构，语法）

句法分析（讲一个句子分成主谓宾等等内容）

使用CYK算法（和动态规划有关）

依存分析（Depending），分析单词之间有没有潜在的联系性

Morphology（单词）

关注单词层面的技术，如分词、pos（词性识别）、NER（命名体识别）

Phonetics（声音）

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

算法负责度介绍

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)

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

这个例子中，时间复杂度为O(log₂^N)

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

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 * log₂^N)

解释：外层循环的时间复杂度为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(n^{log_b^a})和f(n)之间的关系，其有着如下的对应关系：

O(n^{log_b^a}) > f(n) => O(n^{log_b^a})
O(n^{log_b^a}) = f(n) => O(n^{log_b^a}log^k+1n)
O(n^{log_b^a}) < f(n) => f(n)

例题

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

n^{log_b^a} = n^log₂³ ≈ n^1.6

f(n) = n²

因此：n^{log_b^a} ≈ n^1.6 < n² = f(n)，即 n^{log_b^a} < f(n)。此时满足第三种情况，即T(n) = f(n) = O(n²)

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

n^{log_b^a} = n^log₂⁴ = n²

f(n) = n²

因此：n^{log_b^a} = n² = f(n)，即 n^{log_b^a} = f(n)。此时满足第二种情况，即T(n) = O(n^{log_b^a}log^k+1n)

在这道题中f(n) = n² = n²log⁰n，所以k=0。

综上：T(n) = O(n^{log_b^a}log^k+1n) = O(n^log₂⁴log⁰⁺¹n) = O(n²log n)

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

此时：a = 2, b = 2

n^{log_b^a} = n^log₂² = n = f(n) => Case 2

在这道题中f(n) = n = n·log⁰n，所以k=0。

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

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

关于K值得计算方法

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

此时：a = 2, b = 2

n^{log_b^a} = n^log₂² = n = f(n) => Case 2

在这道题中f(n) = n·log¹n，所以k=1。

综上：T(n) = O(n·log² n)

斐波那契数列（Fibonanci Number）

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

使用尾递归

尾递归版本

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

$T(n) = T(n - 2) + T(n - 1)$
$T(n) = 2^n$

时间复杂度？ $O(2^n)$

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

那么如何计算空间复杂度

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

斐波那些数列的改进版本

版本1

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

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

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(p^n)$ $O (p^{n})$ ——> 无法解决的问题
- 对于小型的问题，仍然可以解决
- Approximate Algorithm（近似算法）：不保证获得精确的解，但是是目前为止唯一的解决方法
  - 提出近似算法
  - 指出时间复杂度
  - 给出近似算法最后的解离最优解的距离
- 使用量子计算机进行计算
多项式复杂度，如： $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

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

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

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

# %%
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)

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

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

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

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

维特比算法（Viterbi）

本质上还是DP算法。

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

词典	“经常”	“经”	“有”	“有意见”	“意见”	“分歧”	“见”	“意”	“见分歧”	“分”
概率	0.1	0.05	0.1	0.1	0.2	0.2	0.05	0.05	0.05	0.1
$-log(x)$	2.3	3	2.3	2.3	1.6	1.6	3	3	3	2.3

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

设定其他（没有出现的组合方式）其出现的概率为 $P(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.6$ 从第5个节点到第8个节点
$f(8) = f(6)_{min} + 1.6 = 6.2$ 🉑 从第6个节点到第8个节点
$f(8) = f(7)_{min} + 20 = 26.9$ 从第7个节点到第8个节点

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

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

$f(6) = f(3)_{min} + 2.3 = 4.6$ 🉑 从第3个节点到第6个节点
$f(6) = f(4)_{min} + 1.6 = 6.2$ 从第4个节点到第6个节点
$f(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)
0	3	2.3	4.6	7.6	4.6	6.9	6.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，也就是 $\widehat c\;=\;argmax_{c\in candidates}p(C\vert 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

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

最大子序和

目标：

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

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

做法：

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

子问题：

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

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

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

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: Sequence $A_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)\;=\;max_{\underset{i<j}{A[i]<A[j]}}\{L(i)\}+1$

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，则可能性为 $2^n$

零钱规划

目标：

Input: n denominations of coins of values $l=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)=\underset{i}{min}\{M(j-v_i)\}+1$

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(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]数组

0	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0	8	8	8	8	8	8	8	8	8
2	0	0	0	8	8	10	10	10	10	18	18	18
3	0	6	6	8	8	14	14	16	16	18	18	24
4	0	6	6	9	9	14	14	17	17	19	19	24
5	0	6	6	9	9	14	14	17	17	19	21	24
6	2	6	8	9	11	14	16	17	19	19	21	24

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

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:

$C_i$ -> insertion
$C_d$ -> deletion
$C_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 \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.$

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 = |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(S_1, S_2) = \sqrt{1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2} = \sqrt 6$

$d(S_1, S_3) = \sqrt{1^2 + 2^2 + 1^2 + 1^2 + 1^2} = \sqrt 8$

$d(S_2, S_3) = \sqrt{2^2 + 2^2 + 1^2 + 1^2} = \sqrt 10$

$Sim_{(S_1, S_2)} > Sim_{(S_2, S_3)}$

$Sim_{(S_1, S_3)} > Sim_{(S_2, S_3)}$

计算余弦相似度(Cosine Similarity)

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

计算距离（余弦相似度）： $d = \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(S_1, S_2) = \frac{0}{A} = 0$

$d(S_1, S_3) = \frac{(2+1)}{\sqrt{3}\cdot\sqrt{11}}=\frac{3}{\sqrt{33}}$

$d(S_2, S_3) = \frac{(2)}{\sqrt{3}\cdot\sqrt{11}}=\frac{2}{\sqrt{33}}$

余弦相似度越大，相关性越好，因此： $Sim_{(S_1, S_3)} > Sim_{(S_2, S_3)} > Sim_{(S_1, S_2)}$

注：并不是出现的越多就越重要，也并不是出现的越少就越不重要（如主语在句子中并不是非常重要，但是有可能会出现多次）

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

TF-IDF方法

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

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

文档d中w的词频

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

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

举例

定义词典

词典：[今天, 上, NLP, 课程, 的, 有, 意思, 数据, 也] （9个单词）

句子转换为tfidf向量

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

句子1： $（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(\frac{3}{2}), log3, log3, log1, 0, 0, 0, 0, 0)$ => 9维 = |词典|

句子2： $（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(\frac{3}{2}), 0, 0, log1, log3, log\frac{3}{2}, log\frac{3}{2}, 0, 0)$ => 9维 = |词典|

句子3： $（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(\frac{3}{2}), log(\frac{3}{2}), log3, log3)$ => 9维 = |词典|

词向量

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

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

Words	OneHot Representation	Distributed 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(我们, 爬山) = $\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(运动, 爬山) = $\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，那么也可以有 $2^{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(w_1, w_2, w_3, w_4, w_5, ..., w_n)$

Chain Rule

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

$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})$

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

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

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

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

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

马尔科夫假设（Markov Assumption）

First Order Markov Assumption

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

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

$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(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(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 2^nd Order）

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

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

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

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

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

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

语言模型（Language Model）

Unigram（联合概率）

$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(今天)\cdot p(是)\cdot p(春节)\cdot p(我们)\cdot p(都)\cdot p(休息)$

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

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

Bigram

来自于First Order Markov Assumption

$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})}$

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

N-gram

更高阶的语言模型统称

这里假设N为3

$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})}$

评估语言模型的概率（Estimating Probability）

Unigram

$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（单词总数）

$P_{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}$

$P_{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(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_{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}$

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

N-gram

举例：

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

V = 19（单词总数）

$P_{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}$

$P_{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)}$

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

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

因此对于perplexity越小，LM约好

举例：

训练好的Bigram

计算：

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

由上表可以计算出

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

再带入Perplexity的公式得到

Training 38 million words, test 1.5 million words, WSJ

N-gram Order	Unigram	Bigram	Trigram
Perplexity	962	170	109

Recap

举例：

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

仍然采用Bigram模型

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

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

平滑(Smoothing)

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

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

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

$P_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+1}{c(w_i)+V}$

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

举例：

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

V词典库大小为17（排除掉重复的单词）

$P_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+1}{c(w_i)+V}$

$P_{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（排除掉重复的单词）

$P_{Add-1}(w_i|w_{i-1})=\frac{c(w_{i-1}, w_i)+k}{c(w_i)+kV}$

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

在这里令k=3

$P_{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)

因此：

$Minimize Perplexity <==> minimize f(k) <==> \hat{k}=argmin_k f(k)$

(Interpolation Smoothing)

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

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

核心思路

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

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

$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)$

其中 $\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

定义 $N_c$ ，代表出现c词的单词的个数
例：Sam I am I am Sam I do not eat

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

没有出现过的单词

$P_{MLE} = 0$
$P_{GT} = \frac{N_1}{N}$

$P_{MLE}(飞鱼) = \frac{0}{18} = 0$
$P_{GT}(飞鱼) = \frac{N_1}{N} = \frac{3}{18} = \frac{1}{6}$

出现过的单词

$P_{MLE} = \frac{c}{N}$
$P_{GT} = \frac{(c+1)N_{c+1}}{N_c}$

$P_{MLE}(草鱼) = \frac{1}{18}$
$P_{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

NLP	I	like	studying	course	yesterday
0.1	0.3	0.2	0.2	0.35	0.05

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

(I, like, studying, NLP)

Bigram Model

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

	NLP	I	like	studying	course	yesterday
NLP	0.001	0.001	0.01	0.01	0.989	0.001	-
I	0.01	0.001	0.95	0.01	0.01	0.099	-
like	0.4	0	0	0.5	0.1	0	-
studying	0.3	-	-	-	0.4	0.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,y|z)=p(x|z)\cdot p(y|z)$ 。

参考

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

https://cloud.tencent.com/developer/article/1150386 （非常简明易懂！！五星推荐）

0	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0	8	8	8	8	8	8	8	8	8
2	0	0	0	8	8	10	10	10	10	18	18	18
3	0	6	6	8	8	14	14	16	16	18	18	24
4	0	6	6	9	9	14	14	17	17	19	19	24
5	0	6	6	9	9	14	14	17	17	19	21	24
6	2	6	8	9	11	14	16	17	19	19	21	24

0	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0	8	8	8	8	8	8	8	8	8
2	0	0	0	8	8	10	10	10	10	18	18	18
3	0	6	6	8	8	14	14	16	16	18	18	24
4	0	6	6	9	9	14	14	17	17	19	19	24
5	0	6	6	9	9	14	14	17	17	19	21	24
6	2	6	8	9	11	14	16	17	19	19	21	24

【NLP】学习笔记

案例：机器翻译

简单机器翻译的系统架构

Language Model（语言模型）

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

NLP的应用场景

Question Answering(问答系统)

Sentiment Analysis（情感分析）

Chatbot（聊天机器人）

Information Extraction（信息抽取）

NLP的关键技术

Semantic（语义）

Syntax（句子结构，语法）

Morphology（单词）

Phonetics（声音）

算法负责度介绍

归并排序（Merge Sort）

Master Theorem（主方法）

例题

关于K值得计算方法

斐波那契数列（Fibonanci Number）

尾递归版本

斐波那些数列的改进版本

版本1

版本2

思考题

P vs NP vs NP Hard vs NP Complete

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

常见问题（FAQ）

相似度计算

给予检索的问答系统

问答系统

NLP项目的识别用Pipeline

分词（Word Segmentation）

最大匹配（Max Matching）

前项最大匹配

后项最大匹配

缺点

考虑语义（Incorporate Semantic）

维特比算法（Viterbi）

拼写纠错（Spell Correction）

计算编辑距离（edit distance）

可选择的方式（Alternative Way）

怎样过滤

停用词移除（Stop Words Removal）

Stemming（词的标准化操作）

参考链接

动态规划算法（Dynamic Programming, DP）

最大子序和

最长上升子序列

零钱规划

0-1背包问题

编辑距离

文本表示（Word Representation）

OneHot 独热编码表示

句子表示（Sentence Representation(bollean)）

基于(bollean)的

基于(count)的

文本相似度计算（Sentence Similarity）

计算欧式距离（即两个向量之间的距离）

计算余弦相似度(Cosine Similarity)

TF-IDF方法

举例

定义词典

句子转换为tfidf向量

词向量

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

QNA

如何学习词向量

学习词嵌入（Learn Word Embeddings)

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

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

方法①Averging法则

倒排表

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

如何降低复杂度？

介绍倒排表（Introducing Inverted Index）

语言模型

Noisy Channel Model

机器翻译

语言模型（LM, Use 2^nd Order）

0	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0	8	8	8	8	8	8	8	8	8
2	0	0	0	8	8	10	10	10	10	18	18	18
3	0	6	6	8	8	14	14	16	16	18	18	24
4	0	6	6	9	9	14	14	17	17	19	19	24
5	0	6	6	9	9	14	14	17	17	19	21	24
6	2	6	8	9	11	14	16	17	19	19	21	24