《智能搜索和推荐系统原理、算法和应用》读书笔记，主要记录了搜索推荐中常用的算法，具体的算法流程需要单独记录笔记。书中代码https://github.com/michaelliu03/Search-Recommend-InAction。

搜索和推荐系统的基础

概率论统计与应用数学基础知识

概率论基础

古典概率：可重复的实验次数N趋于无穷时，事件A发生的频率Q无限接近概率P。$$lim_{N\rightarrow \infty}Q(A)=P(A)$$
条件概率：已知事件B发生的情况下事件A发生的概率。$$P(A|B)=\frac{P(AB)}{P(B)}$$
全概率公式：将事件A分割成小事件，先求小事件的概率，相加求得事件A的概率$$P(A)=P\left(A\bigcap(\bigcup^n_{i=1}B_i)\right)=\sum^n_{i=1}P(AB_i)=\sum^n_{i=1}P(B_i)P(A|B_i)$$
贝叶斯公式：在大事件A发生的条件下求分割的小事件$B_i$发生的概率。$$P(B_i|A)=\frac{P(B_i)P(A|B_i)}{P(A)}=\frac{P(B_i)P(A|B_i)}{\sum^n_{i=1}P(B_i)P(A|B_i)}$$

$$后验=\frac{先验·似然}{P(A)}$$
基础的概率分布：
- 0-1分布：$P(X=k)=p^k(1-p)^{1-k},k=0,1$
- 二项分布$B(n,p)$：$P(X=k)=C^k_np^k(1-p)^{n-k},k=0,1…n$
- 正态分布$N(\mu,\sigma^2)$：$\psi(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$
- 柏松分布
- 均匀分布
- 指数分布
- 几何分布
- 超几何分布

import numpy as np
from scipy import stats
import matplotlib.pyplot as plt

def binom_pmf_test():
  '''
  离散分布
  二项分布的例子：抛掷100次硬币，恰好两次正面朝上的概率是多少？
  '''
  n = 100   # 独立实验次数
  p = 0.5   # 每次正面朝上概率
  k = np.arange(0, 100)  # 0-100次正面朝上概率
  binomial = stats.binom.pmf(k, n, p)
  print(sum(binomial))  # 概率和为1
  plt.plot(k, binomial, 'o-')
  plt.title('Binomial: n=%i , p=%.2f' % (n, p), fontsize=15)
  plt.xlabel('Number of successes')
  plt.ylabel('Probability of success', fontsize=15)
  plt.show()

def normal_distribution():
    '''
    正态分布是一种连续分布，其函数可以在实线上的任何地方取值。
    正态分布由两个参数描述：分布的平均值μ和方差σ2 。
    '''
    mu = 0  # mean
    sigma = 1  # standard deviation
    x = np.arange(-10, 10, 0.1)
    y = stats.norm.pdf(x, 0, 1)
    plt.plot(x, y)
    plt.title('Normal: $\mu$=%.1f, $\sigma^2$=%.1f' % (mu, sigma))
    plt.xlabel('x')
    plt.ylabel('Probability density', fontsize=15)
    plt.show()

if __name__ =="__main__":
    binom_pmf_test()        # 二项分布
    normal_distribution()   # 正态分布

二项分布

正态分布

期望$E(X)$
方差$D(X)$
标准差$\sqrt{D(X)}$
协方差$Cov(X,Y)=E[(X-E(X))(Y-E(Y))]$

线性代数基础

矩阵
向量
张量
特征向量和特征值：矩阵A的特征向量指与A相乘后相当于对该向量进行缩放的非0向量x，$\lambda$是相应的特征值。$$Ax=\lambda x$$

$$x^TA=\lambda x^T$$

假设A有n个线性无关的特征向量${v^{(1)},…,v^{(n)}}$，V是每一列是一个特征向量的矩阵，将A特征值分解：$$A=Vdiag(\lambda)V^{-1}$$

不是每一个矩阵都能分解为特征值和特征向量，特征分解可能会涉及复数和非实数。每一个实对称矩阵都能分解为实特征向量和实特征值。$$A=Q\Lambda Q^{-1}$$

其中Q是A的特征向量组成的正交矩阵（若 $AA^T=E$，n阶实矩阵A是正交矩阵），$\Lambda$是对角矩阵。
奇异值分解：可以将非方阵分解为奇异向量和奇异值。$$A_{m\times n}=U_{m\times m}D_{m\times n}V^T_{n\times n}$$

U和V是正交阵，D是对角阵，对角阵上的元素称为矩阵A的奇异值，U的列向量为左奇异向量，V的列向量为右奇异向量。

机器学习基础

导数
梯度（矢量）
最大似然估计：已知某个总体下的随机样本满足某种概率分布，概率分布的参数是未知的，经过反复试验，若某个参数使得样本出现概率最大，则这个参数值当作最大似然估计值。
随机过程与隐马尔可夫模型
信息熵：熵是对不确定性和无序程度的预测。熵越大信息越混乱越不确定。
- 熵：$H(X)=-\sum_{x\in R}p(x)log_2p(x)$，均匀概率分布时熵最大
- 联合熵：一对离散随机变量的不确定性$H(X,Y)=\sum_{x\in \Omega}\sum_{y\in \Psi}p(x,y)log_2p(x,y)$
- 条件熵：给定随机变量X条件下Y的条件熵$H(Y|x)=\sum_{y\in \Phi}p(y|x)log_2p(y|x)$
- 自信息：事件X发生的不确定性或事件包含的信息量$I(X)=-log_2P(x)$
- 互信息：$I(X;Y)=H(X)-H(X|Y)=log_2\frac{P(X,Y)}{P(X)P(Y)}$

搜索系统和推荐系统常识

ACM推荐系统大会

搜索引擎分类：
- 全文搜索引擎
- 元搜索引擎
- 垂直搜索引擎
- 目录搜索引擎
推荐系统分类：
- 基于内容的推荐
- 基于协同过滤的推荐
- 混合推荐方法
推荐系统问题：
- 冷启动
- 稀疏性
- 马太效应和长尾理论

知识图谱相关理论

知识图谱：用图模型描述知识和建模世界万物之间关联关系的一种技术方法。组成三要素：实体、关系、属性

信息抽取
- 命名实体识别（Named Entity Recognition, NER）
  - CRF
  - BiLSTM-CRF
- 关系抽取
  - 基于RNN
  - 基于CNN
知识融合
- 实体对齐
- 实体消歧
知识加工
- 知识推理
  - 演绎推理
    - 基于规则的推理
    - 马尔可夫逻辑网
    - 概率软逻辑
  - 归纳推理
    - 归纳逻辑程序设计
    - 关联规则挖掘
    - 路径排序算法
  - 基于分布式的知识推理
    - Trans模型
    - 语义模型
质量评估

搜索系统的基本原理

搜索系统框架及原理

数据收集及预处理
- 爬虫
- 数据清洗（去重算法SimHash）
- 存储空间及分布式设计（Trie树）
文本分析
- 查询处理
  - 分词方法：基于字符串、基于理解、基于统计的分词方法
  - 查询建议
  - 查询更正（若样本类别不均衡，可采用上下采样）
- 意图理解
- 其他方法
  - 层次聚类
    - 分类：凝聚式（自底向上）、分裂式（自顶向下）
    - 求距离/相似度方法：闵可夫斯基距离（P范数）、马氏距离、相关系数、夹角余弦
  - K均值聚类：采用欧式距离，初始聚类中心可考虑采用层次聚类
  - LDA主题模型
    - LSA（Latent Senmantic Analysis）
    - PLSA（Probability LSA）
    - LDA（Latent Dirichlet Allocation）
基于知识图谱的搜索系统

搜索系统中的主要算法

信息检索基本模型
- 布尔模型
- 向量空间模型（权重计算：TF-IDF）
- 概率检索模型（二元独立概率模型BIM）
- 其他模型：基于集合论、基于代数论、基于概率统计的模型
搜索和机器学习
- 排序学习：单文档方法（CTR）、文档对方法（Boost、SVM、NN）、文档列表方法
- 示例：LR、AdaBoost、随机森林（海森矩阵：多元函数的二阶偏导构成的矩阵）
搜索和深度学习
- DNN
- DSSM（Deep Structured Semantic MOdels）
- Transformer：编码、解码、Softmax与线性变换