1.NLP实战处理过程

2.word Segmentation Tools

  • Jieba分词
  • SnowNLP
  • LTP
  • HanNLP

3.Segmentation Method

前向最大匹配(forward-max matching)

  • 设置一个max_len（类似于窗体大小）

  • 查看max_len长度的字符串，对比词典库看是否存在

    • 若不存在，max_len - 1，继续对比

    • 若存在，存储该匹配项，从下一个字符处开始max_len匹配

  • 贪心算法，匹配到后便不再细分

后向最大匹配(backward-max matching)

  • 从后开始的匹配过程

Incorporate Semantic(考虑语义)

动态规划

  • f(m):从结点1到m的最短路径值
  • f(m) = min{f(1,n) + Wnm} 到m的最短路径为1到n的路径加上n到m的路径的最小值

4.Spell Correction (拼写错误纠正)

编辑距离(edit distance)

  • insert,delete,replace 三种操作

  • 原方法：将原单词转换为词库单词的操作次数（复杂度O(v),v为词库的单词数目）

  • 改进方法：根据原单词生成编辑举例为1、2的字符串，然后对词库的单词过滤

    • 过滤方法：

    $$
    x = argmaxc∈candidatesP( c | s ) , s 输入 , c 正确的
    $$

  • 贝叶斯定理 P(x|y) = P(y|x)*P(x) / P(y)

  • P(x,y) = P(x|y) * P(y) = P(y|x) * P(x)

    • 过滤方法：

    $$
    x = argmaxc∈candidatesP( c | s ) , s 输入 , c 正确的
    $$

Filtering Words

  • 对于NLP的应用，通常先把停用词、出现频率很低的词汇过滤掉

Normalize（词的标准化）

  • stemming

5.Word Representation（文本表示）

One-hot representation

  • len(向量) = len(词典)
  • 对应词位置为1，其他为0

boolean representation

  • 只要出现就标记1

count-based representation

  • 出现多少次就标记几

分布式表示法 (Distributed Representation)

6.文本相似度

计算距离（欧氏距离）: d = |s1 - s2|

  • $$
    s1 = (x1,x2,x3) ; s2 = (y1,y2,y3)
    $$
  • $$
    d = sqrt( (x1-y1)^2 + (x2-y2)^2 + (x3-y3)^2 )
    $$
  • 距离越小相似度越大

计算相似度（余弦相似度）: d = s1 点乘 s2 / (|s1|*|s2|)

  • $$
    s1 = (x1,x2,x3) ; s2 = (y1,y2,y3)
    $$
  • $$
    d = ( x1y1 + x2y2 + x3y3 ) / ( sqrt(x1^2 + x2 ^ 2 + x3^2) * sqrt(y1^2 + y2 ^ 2 + y3^2) )
    $$
  • 距离越小相似度越小

并不是出现的越多就越重要，并不是出现的越少就越不重要

TF-IDF

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

    前者为文档d中w的词频
    后者为log(N/N(w)),N:语料库中的文档总数,N(w):词语w出现在多少个文档

7.词向量

Average 法则

8.倒排表 (Inverted Index)

针对多个文档，每个单词分别属于哪个或哪几个文档

对用户输入的关键词，查找对应的倒排表，返回其交集。若不存在，则全部返回。

9.语言模型

目标：p(text|source) -> p(source|text)p(text)
$$
P(A,B,C,D) = P(A) * P(B|A) * P(C|A,B) * P(D|A,B,C)
$$

$$
Perplexity = 2^(-x),x : average log likelihood
$$

10.平滑Smoothing

对于训练数据集中未出现的，而测试数据集中出现的

Add-one Smoothing（Laplace Smoothing）

  • $$
    PMLE(Wi|Wi-1) = c(Wi-1,Wi) / c(Wi)
    $$
  • $$
    PAdd-1(Wi|Wi-1) = (c(Wi-1,Wi) + 1) / (c(Wi) + V)
    $$

  • 加1避免出现0,加V是为了满足对同一个Wi做概率计算时不存在的部分加上存在的部分得到V

  • Wi为i词语出现的次数

Add-K Smoothing

  • 类似Add-one Smoothing,分子加k,分母加kv
  • K的取值方法:
    • K =1 ,2 ,3 ,…
    • 优化 F(k)

Interpolation

Good-Turning Smoothing

Dynamic Programming

最大自序和

def maxSubArray(self, nums):
    """数组不全为负"""
    sum = 0
    MaxSum = nums[0]
    for i in range(len(nums)):
        sum += nums[i]
        if sum > MaxSum:
            MaxSum = sum
        if sum < 0:
            sum = 0
    return MaxSum

最长上升子序列

def lenthOfLIS(self, nums):
    if len(nums) <= 1:
        return len(nums)
    mem = [1 for _ in range(len(nums))]
    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)

零钱兑换

def coinChange(coins, amount):
	"""
	:type coins: List[int]
	:type amount: int
	:rtype: int
	"""
	coins.sort() #给硬币从小到大排序
	dp = {0:0} #生成字典dp，并且当总金额为0时，最少硬币个数为0
	for i in range(1,amount + 1):
		dp[i] = amount + 1 #因为硬币个数不可能大于amount，所以赋值amount + 1便于比较
		for j in coins:
			if j <= i:
				dp[i]=min(dp[i],dp[i-j]+1)
	if dp[amount] == amount + 1: #当最小硬币个数为初始值时，代表不存在硬币组合能构成此金额
		return -1
	else:
		return dp[amount]

0-1背包问题

def knapsack(w, v, C):
    mem = np.zeros((len(w)+1, C+1))
    for i in range(1, len(w)+1):
        for i 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

Good-Turning Smoothing

没有出现过的单词

  • PGT = N1 / N

出现过的单词

  • PGT = (c+1)Nc+1 / Nc

####Cross-validation

  • LR:

$$
minimize - \sum^n_{i=1}y*logP(y|x_iw)+(1-y)log[1-P(y|x_iw)]+\lambda||w||^2_2
$$