Bagging

bagging：bootstrap aggregating，每个分类器随机从原样本 中做有放回的随机抽样，在抽样结果上训练基模型，最后根据 多个基模型的预测结果产生最终结果

• 核心为bootstrap重抽样自举

步骤

• 建模阶段：通过boostrap技术获得k个自举样本 $S_1, S_2,…, S_K$，以其为基础建立k个相同类型模型 $T_1, T_2,…, T_K$

• 预测阶段：组合K个预测模型

  • 分类问题：K个预测模型“投票”
  • 回归问题：K个预测模型平均值

模型性质

• 相较于单个基学习器，Bagging的优势
  • 分类Bagging几乎是最优的贝叶斯分类器
  • 回归Bagging可以通过降低方差（主要）降低均方误差

预测误差

总有部分观测未参与建模，预测误差估计偏乐观

• OOB预测误差：out of bag，基于袋外观测的预测误差， 对每个模型，使用没有参与建立模型的样本进行预测，计算预测 误差

• OOB观测比率：样本总量n较大时有

  $$r = (1 - \frac 1 n)^n \approx \frac 1 e = 0.367$$
  • 每次训练样本比率小于10交叉验证的90%

Random Forest

随机森林：随机建立多个有较高预测精度、弱相关（甚至不相关） 的决策树（基础学习器），多棵决策树共同对新观测做预测

• RF是Bagging的扩展变体，在以决策树为基学习器构建Bagging 集成模型的基础上，在训练过程中引入了随机特征选择

• 适合场景

  • 数据维度相对较低、同时对准确率有要求
  • 无需很多参数调整即可达到不错的效果

步骤

• 样本随机：Bootstrap自举样本

• 输入属性随机：对第i棵决策树通过随机方式选取K个输入变量 构成候选变量子集$\Theta_I$

  • Forest-Random Input：随机选择$k=log_2P+1或k=\sqrt P$ 个变量

  • Forest-Random Combination

    • 随机选择L个输入变量x
    • 生成L个服从均匀分布的随机数$\alpha$
    • 做线性组合 $vj = \sum{i=1}^L \alpha_i x_i, \alpha_i \in [-1, 1]$
    • 得到k个由新变量v组成的输入变量子集$\Theta_i$

• 在候选变量子集中选择最优变量构建决策树

  • 生成决策树时不需要剪枝

• 重复以上步骤构建k棵决策树，用一定集成策略组合多个决策树

  • 简单平均/随机森林投票

优点

• 样本抽样、属性抽样引入随机性

  • 基学习器估计误差较大，但是组合模型偏差被修正
  • 不容易发生过拟合、对随机波动稳健性较好
  • 一定程度上避免贪心算法带来的局部最优局限

• 数据兼容性

  • 能够方便处理高维数据，“不用做特征选择”
  • 能处理分类型、连续型数据

• 训练速度快、容易实现并行

• 其他

  • 可以得到变量重要性排序
  • 启发式操作
  • 优化操作

缺点

• 决策树数量过多时，训练需要资源多
• 模型解释能力差，有点黑盒模型

推荐系统架构

Matching

召回算法Match：包含多个渠道的召回模型，希望从资源库中选取 多样性偏好内容，缩小排序目标

• 协同过滤
• 主题模型
• 内容召回
• 热点召回

Ranking

排序：对多个召回渠道内容打分、排序、选出最优的少量结果

• 若召回结果仍包含大量数据，可以考虑分为两个阶段
  • 粗排：进一步剔除召回结果
  • 精排：对粗排结果再次打分、排序，得到最终推荐结果

Collaborative Filtering-Based Recommendation

基于协同过滤推荐算法：推荐算法中主流

• 模型一般为n个物品、m个用户的表

  • 只有部分用户、物品之间有评分数据
  • 要用已有部分稀疏数据预测空白物品、数据之间评分关系， 推荐高评分物品

• 无需太多特定领域的知识，可通过基于统计的机器学习算法得到 较好推荐效果，可以分为

  • 基于用户
  • 基于物品
  • 基于模型

• 现在指推荐算法一般指协同过滤，其他基于内容、规则、人口 统计信息等都被包含/忽略

User-based

基于用户协同过滤：主要考虑用户之间相似度，找出相似用户、相似 用户喜欢的物品，预测目标用户对对应物品的评分，推荐高评分物品

• 特点：（相较于Item-Based）推荐更社会化

  • 反映用户所在小型兴趣群体中物品热门程度
  • 可帮助用户找到新类别、惊喜物品

• 适合场景

  • 用户数量较少、变化慢场合，否则更新、计算用户相似度矩阵 代价大
  • 时效性强、用户个性化兴趣不明显领域
  • 无需给出推荐解释
  • 示例
    • 新闻推荐：注重热门、时效、item更新快
    • 热点视频推荐

• 方法

  • 基于规则：大众型推荐方法，如：最多用户点击、浏览
  • 基于人口统计信息：简单根据用户基本信息发现用户相关 程度、推荐
  • 混合推荐
    • 结合多个推荐算法，集成算法推荐结果
    • 复杂度高

Item-Based Collaborative Filtering

基于项目协同过滤：考虑物品和物品之间的相似度，找到目标用户 对某些物品的评分，预测用户对相似度高的类似物品评分，推荐高 评分相似物品

• 特点：（相较于User-Based）推荐更个性化

  • 反映用户自身的兴趣传承
  • 可帮助用户深入挖掘自身兴趣
  • 准确度一般
  • 推荐多样性弱，难以带来惊喜

• 适合场景

  • 物品数量较少、变化慢场合，否则更新、计算物品相似度 矩阵代价大
  • 长尾物品丰富、个性化需求不明显
  • 需要向用户给出推荐理由
  • 示例
    • 电商
    • 电影：兴趣持久、更个性化

Model-Based Collaborative Filtering

基于模型：目前最主流的协同过滤类型

• 关联算法：找出用户-物品数据里频繁出现的项集，作频繁集 挖掘，推荐频繁集、序列中其他物品

  • Apriori
  • FPTree
  • PrefixSpan

• 聚类算法：按照用户、物品基于一定距离度量聚类，推荐高评分 同类物品、同类人群 （类似于基于用户、物品协同过滤）

  • K-means
  • BIRCH
  • DBSCAN
  • Spectral Clustering

• 分类算法：使用分类模型划分物品

  • 逻辑回归
  • 朴素贝叶斯

• 回归算法：使用回归模型给物品预测打分，较分类更平滑

  • 线性回归
  • 决策树
  • SVM

• 矩阵分解：对用户-物品评分矩阵进行分解

  • FunkSVD
  • BiasSVD
  • SVD++

• 还有基于图模型、神经网络等新模型
• 还有依赖于自然语言处理NLP，通过挖掘文本内容特征，得到 用户的偏好，进而做推荐，同样可以找到用户独特的小众喜好

Hash Function

• hash：散列/哈希，将任意类型值转换为关键码值
• hash function：哈希/散列函数，从任何数据中创建小的数字“指纹”的方法
• hash value：哈希值，哈希函数产生关键码值
• collision：冲突，不同两个数据得到相同哈希值

• 哈希函数应该尽可能使得哈希值均匀分布在目标空间中
  • 降维：将高维数据映射到低维空间
  • 数据应该低维空间中尽量均匀分布

数据相关性

• Data Independent Hashing：数据无关哈希，无监督，哈希函数基于某种概率理论

  • 对原始的特征空间作均匀划分
  • 对分布不均、有趋向性的数据集时，可能会导致高密度区域哈希桶臃肿，降低索引效率

• Data Dependent Hashing：数据依赖哈希，有监督，通过学习数据集的分布从而给出较好划分的哈希函数

  • 得到针对数据密度动态划分的哈希索引
  • 破坏了传统哈希函数的数据无关性，索引不具备普适性

应用

• 查找数据结构：cs_algorithm/data_structure/hash_table
  • 哈希表
• 信息安全方向：cs_algorithm/specification/info_security
  • 文件检验
  • 数字签名
  • 鉴权协议

哈希函数

• 简单哈希函数主要用于提升查找效率（构建哈希表）

  • 要求哈希函数的降维、缩小查找空间性质
  • 计算简单、效率高

• 复杂哈希函数主要用于信息提取

  • 要求哈希函数的信息提取不可逆、非单调映射
  • 查表哈希
    • CRC 系列算法：本身不是查表，但查表是其最快实现
    • Zobrist Hashing
  • 混合哈希：利用以上各种方式
    • MD5
    • Tiger

单值输入

• 直接寻址法：取关键字、或其某个线性函数值 $hash(key) = (a * key + b) \% prime$

  • $prime$：一般为质数，以使哈希值尽量均匀分布，常用的如：$2^{32}-5$

• 数字分析法：寻找、利用数据规律构造冲突几率较小者

  • 如：生日信息前 2、3 位大体相同，冲突概率较大，优先舍去

• 平方取中法：取关键字平方后中间几位

• 折叠法：将关键字分割为位数相同部分，取其叠加和

• 随机数法：以关键字作为随机数种子生成随机值

  • 适合关键字长度不同场合

• 常用于之前哈希结果再次映射为更小范围的最终哈希值

序列输入

加法哈希

加法哈希：将输入元素相加得到哈希值

• 标准加法哈希

  1 2 3 4 5 6

  AddingHash(input): hash = 0 for ele in input: hash += ele # prime 为任意质数，常用 2^32 - 5 hash = hash % prime

  • 最终哈希结果 $\in [0, prime-1]$

位运算哈希

位运算哈希：利用位运算（移位、异或等）充分混合输入元素

• 标准旋转哈希

  1 2 3 4 5

  RotationHash(input): hash = 0 for ele in input: hash = (hash << 4) ^ (hash >> 28) ^ ele return hash % prime

• 变形 1

  1	hash = (hash<< 5) ^ (hash >> 27) ^ ele

• 变形2

  1 2 3

  hash += ele hash ^= (hash << 10) hash ^= (hash >> 6)

• 变形3

  1 2 3 4

  if (ele & 1) == 0: hash ^= (hash << 7) ^ ele ^ (hash >> 3) else: hash ^= ~((hash << 11) ^ ele ^ (hash >> 5))

• 变形4

  1	hash += (hash << 5) + ele

• 变形5

  1	hash = ele + (hash << 6) + (hash >> 16) - hash

• 变形6

  1	hash ^= (hash << 5) + ele + (hash >> 2)

乘法哈希

乘法哈希：利用乘法的不相关性

• 平方取头尾随机数生成法：效果不好

• Bernstein 算法

  1 2 3 4 5

  Bernstein(input): hash = 0 for ele in input: hash = 33 * hash + ele return hash

  • 其他常用乘数：31、131、1313、13131、131313

• 32位 FNV 算法

  1 2 3 4 5 6 7

  M_SHIFT = M_MASK = FNVHash(input): hash = 2166136261; for ele in input: hash = (hash * 16777619) ^ ele return (hash ^ (hash >> M_SHIFT)) & M_MASK

• 改进的 FNV 算法

  1 2 3 4 5 6 7 8 9 10

  FNVHash_2(input): hash = 2166136261; for ele in input: hash = (hash ^ ele) * 16777619 hash += hash << 13 hash ^= hash >> 7 hash += hash << 3 hash ^= hash >> 17 hash += hash << 5 return hash

• 乘数不固定

  1 2 3 4 5 6 7

  RSHash(input): hash = 0 a, b = 378551, 63689 for ele in input: hash = hash * a + ele a *= b return hash & 0x7FFFFFFF

• 除法也类似乘法具有不相关性，但太慢

定长序列

• 两步随机数

  1 2 3 4 5 6

  main_rand_seq = randint(k) TwoHashing(input[0,...,k]): hash = 0 from i=0 to k: hash += input[i] * main_rand_seq[i] hash = hash mod prime

Universal Hashing

• 全域哈希：键集合 $U$ 包含 $n$ 个键、哈希函数族 $H$ 中哈希函数 $h_i: U \rightarrow 0..m$，若 $H$ 满足以下则为全域哈希 $$

    \forall x \neq y \in U, | \{h|h \in H, h(x) = h(y) \} | = \frac {|H|} m
  

  $$

  • $|H|$：哈希函数集合 $H$ 中函数数量

• 独立与键值随机从中选择哈希函数，避免发生最差情况
• 可利用全域哈希构建完美哈希

性质

• 全域哈希 $H$ 中任选哈希函数 $h_i$，对任意键 $x \neq y \in U$ 冲突概率小于 $\frac 1 m$

  • 由全域哈希函数定义，显然

• 全域哈希 $H$ 中任选哈希函数 $hi$，对任意键 $x \in U$，与其冲突键数目期望为 $\frac n m$，即 $E{[collision_x]}=\frac n m$

  $$\begin{align*} E(C_x) &= E[\sum_{y \in U - \{x\}} C_{xy}] \\ &= \sum_{y \in U - \{x\}} E[C_{xy}] \\ &= \sum_{y \in U - \{x\}} \frac 1 m \\ &= \frac {n-1} m \end{align*}$$

  • $C_x$：任选哈希函数，与 $x$ 冲突的键数量
  • $C_{xy} = \left { \begin{matrix} 1, & h_i(x) = h_i(y) \ 0, & otherwise \end{matrix} \right.$：指示 $x,y$ 是否冲突的指示变量

  • $m = n^2$ 时，冲突期望小于 0.5
    • $n$ 个键两两组合数目为 $C_n^2$
    • 则 $E_{total} < C_n^2 \frac 1 n < 0.5$

例

• 以下构造 $[0,p-1] \rightarrow [0,m-1]$ 全域哈希

• $p$ 为足够大素数使得所有键值 $\in [0,p-1]$

  • 记 $Z_p = { 0,1,\cdots,p-1 }$
  • 记 $Z_p^{*}={ 1,2,\cdots,p-1 }$
  • 且哈希函数映射上限（哈希表长度） $m < max(U) < p$

• 记哈希函数

  $$\forall a \in Z_p^{*}, b \in Z_p, h_{a, b}(k) = ((a k + b) \% p) \% m$$

• 则以下哈希函数族即为全域哈希

  $$H_{p,m} = {h_{a,b}|a \in Z_p^{*}, b \in Z_p}$$

Locality Sensitive Hashing

LSH：局部敏感哈希

• $(r_1,r_2,P_1,P_2)-sensitive$ 哈希函数族 $H$ 需满足如下条件 $$ \begin{align*}

    Pr_{H}[h(v) = h(q)] \geq P_1, & \forall q \in B(v, r_1) \\
    Pr_{H}[h(v) = h(q)] \geq P_2, & \forall q \notin B(v, r_2) \\
  

  \end{align*}$$

  • $h \in H$
  • $r_1 < r_2, P_1 > P_2$：函数族有效的条件
  • $B(v, r)$：点 $v$ 的 $r$ 邻域
  • $r_1, r_2$：距离，强调比例时会表示为 $r_1 = R, r_2 = cR$

• 此时 相似目标（距离小）有更大概率发生冲突

LSH查找

思想

• 相似目标更有可能映射到相同哈希桶中

  • 则只需要在目标所属的哈希桶中进行比较、查找即可
  • 无需和全集数据比较，大大缩小查找空间

• 可视为降维查找方法

  • 将高维空间数据映射到 1 维空间，寻找可能近邻的数据点
  • 缩小范围后再进行精确比较

概率放大

• 期望放大局部敏感哈希函数族 $Pr_1, Pr_2$ 之间差距

• 增加哈希值长度（级联哈希函数中基本哈希函数数量） $k$

  • 每个哈希函数独立选择，则对每个级联哈希函数 $g_i$ 有 $Pr[g_i(v) = g_i(q)] \geq P_1^k$
  • 虽然增加哈希键位长会减小目标和近邻碰撞的概率，但同时也更大程度上减少了和非近邻碰撞的概率、减少搜索空间

  • 级联哈希函数返回向量，需要对其再做哈希映射为标量，方便查找

• 增加级联哈希函数数量（哈希表数量） $L$

  • $L$个哈希表中候选项包含真实近邻概率 至少 为 $1 - (1 - P_1^k)^L$
  • 增加哈希表数量能有效增加候选集包含近邻可能性
  • 但同时也会增大搜索空间

搜索近似最近邻

• 使用 $L$ 个级联哈希函数分别处理待搜索目标
• 在 $L$ 个哈希表分别寻找落入相同哈希桶个体作为候选项
• 在所有候选项中线性搜索近邻

基于汉明距离的 LSH

• 在汉明距离空间中搜索近邻
  • 要求数据为二进制表示
  • 其他距离需要嵌入汉明距离空间才能使用
    • 欧几里得距离没有直接嵌入汉明空间的方法
      • 一般假设欧几里得距离和曼哈顿距离差别不大
      • 直接使用对曼哈顿距离保距嵌入方式

设计哈希函数族

• 考虑哈希函数族 $H = { h_1, h_2, \cdots, h_m }$

  • 其中函数 $h_i$ 为 ${0, 1}^d$ 到 ${0, 1}$ 的映射：随机返回特定比特位上的值

• 从 $H$ 中随机的选择哈希函数 $h_i$

  • 则 $Pr[h_i(v) = h_i(q)]$ 等于 $v, q$ 相同比特数比例，则
    • $Pr_1 = 1 - \frac R d$
    • $Pr_2 = 1 - \frac {cR} d$
  • 考虑到 $Pr_1 > Pr_2$，即此哈希函数族是局部敏感的

基于 Jaccard 系数的 LSH

• 考虑 $M * N$ 矩阵 $A$，元素为 0、1

  • 其中
    • $M$：集合元素数量
    • $N$：需要比较的集合数量
  • 目标：寻找相似集合，即矩阵中相似列

• 用 Jaccard 系数代表集合间相似距离，用于搜索近邻

  • 要求各数据向量元素仅包含 0、1：表示集合是否包含该元素

定义 Min-hashing 函数族

• 对矩阵 $A$ 进行 行随机重排 $\pi$，定义 Min-hashing 如下

  $$h_{\pi}(C) = \min \pi(C)$$

  • $C$：列，表示带比较集合
  • $\min \pi(C)$：$\pi$ 重排矩阵中 $C$ 列中首个 1 所在行数

• 则不同列（集合） Min-hashing 相等概率等于二者 Jaccard 系数

  $$\begin{align*} Pr(h_{\pi}(C_1) = h_{\pi}(C_2)) & = \frac a {a + b} \\ & = Jaccard_d(C_1, C_2) \end{align*}$$

  • $a$：列 $C_1, C_2$ 取值均为 1 的行数
  • $b$：列 $C_1, C_2$ 中仅有一者取值为 1 的行数
  • 根据 Min-hashing 定义，不同列均取 0 行被忽略

Min-hashing 实现

• 数据量过大时，对行随机重排仍然非常耗时，考虑使用哈希函数模拟行随机重排

  • 每个哈希函数对应一次随机重排
    • 哈希函数视为线性变换
    • 然后用哈希函数结果对总行数取模
  • 原行号经过哈希函数映射即为新行号

• 为减少遍历数据次数，考虑使用迭代方法求解

  1 2 3 4 5 6

  for i from 0 to N-1: for j from 0 to M-1: if D[i][j] == 1: for k from 1 to K: # 更新随机重拍后，第 `j` 列首个 1 位置 DD[k][j] = min(h_k(i), DD[k][j])

  • $D$：原始数据特征矩阵
  • $DD$：$Min-hashing* 签名矩阵
  • $N$：特征数量，原始特征矩阵行数
  • $M$：集合数量，原始特征矩阵列数
  • $K$：模拟的随机重排次数，Min-hashing 签名矩阵行数
  • $h_k,k=1,…,K$：$K$ 个模拟随机重排的哈希函数，如 $h(x) = (2x + 7) mod N$

  • 初始化 Min-hashing 签名矩阵所有值为 $\infty$
  • 遍历 $N$ 个特征、$M$ 个集合
    • 查看每个对应元素是否为 1
    • 若元素为 1，则分别使用 $K$ 个哈希函数计算模拟重排后对应的行数
    • 若计算出行数小于当前 *Min-hash$ 签名矩阵相应哈希函数、集合对应行数，更新
  • 遍历一遍原始数据之后即得到所有模拟重排的签名矩阵

Exact Euclidean LSH

• $E^2LSH$：欧式局部LSH，LSH Based-on P-stable Distribution

  • 使用内积将向量随机映射到哈希值
  • p-stable 分布性质将欧式距离同哈希值相联系，实现局部敏感

• $E^2LSH$ 特点

  • 基于概率模型生成索引编码结果不稳定
  • 随编码位数 $k$ 增加的，准确率提升缓慢
  • 级联哈希函数数量 $L$ 较多时，需要大量存储空间，不适合大规模数据索引

p-stable 哈希函数族

$$h_{a, b}(v) = \lfloor \frac {av + b} r \rfloor$$

• $v$：$n$ 维特征向量
• $a = (X_1,X_2,\cdots,X_n)$：其中分量为独立同 p-stable 分布的随机变量
• $b \in [0, r]$：均匀分布随机变量

p-stable 哈希函数碰撞概率

• 考虑$|v_1 - v_2|_p = c$的两个样本碰撞概率

• 显然，仅在 $|av1 - av_2| \leq r$ 时，才存在合适的 $b$ 使得 $h{a,b}(v1) = h{a,b}(v_2)$

  • 即两个样本碰撞，不失一般性可设 $av_1 \leq av_2$
  • 此 $r$ 即代表局部敏感的 局部范围

• 若 $(k-1)r \leq av_1 \leq av_2 < kr$，即两个样本与 $a$ 内积在同一分段内

  • 易得满足条件的 $b \in [0,kr-av_2) \cup [kr-av_1, r]$
  • 即随机变量 $b$ 取值合适的概率为 $1 - \frac {av_2 - av_1} r$

• 若 $(k-1)r \leq av_1 \leq kr \leq av_2$，即两个样本 $a$ 在相邻分段内

  • 易得满足条件的 $b \in [kr-av_1, (k+1)r-av_2)$
  • 即随机变量 $b$ 取值合适的概率同样为 $1 - \frac {av_2 - av_1} r$

• 考虑 $av_2 - av_1$ 分布为 $cX$，则两样本碰撞概率为

  $$\begin{align*} p(c) & = Pr_{a,b}(h_{a,b}(v_1) = h_{a,b}(v_2)) \\ & = \int_0^r \frac 1 c f_p(\frac t c)(1 - \frac t r)dt \end{align*}$$

  • $c = |v_1 - v_2|_p$：特征向量之间$L_p$范数距离
  • $t = a(v_1 - v_2)$
  • $f$：p稳定分布的概率密度函数

  • $p=1$ 柯西分布

    $$p(c) = 2 \frac {tan^{-1}(r/c)} \pi - \frac 1 {\pi(r/c)} ln(1 + (r/c)^2)$$

  • $p=2$ 正态分布

    $$p(c) = 1 - 2norm(-r/c) - \frac 2 {\sqrt{2\pi} r/c} (1 - e^{-(r^2/2c^2)})$$

性质、实现

限制近邻碰撞概率

• $r$ 最优值取决于数据集、查询点

  • 根据文献，建议$r = 4$

• 若要求近邻 $v \in B(q,R)$以不小于$1-\sigma$ 概率碰撞，则有

  $$\begin{align*} 1 - (1 - p(R)^k)^L & \geq 1 - \sigma \\ \Rightarrow L & \geq \frac {log \sigma} {log(1 - p(R)^k)} \end{align*}$$

  则可取

  $$L = \lceil \frac {log \sigma} {log(1-p(R)^k)} \rceil$$

• $k$ 最优值是使得 $T_g + T_c$ 最小者

  • $T_g = O(dkL)$：建表时间复杂度
  • $T_c = O(d |collisions|)$：精确搜索时间复杂度
  • $T_g$、$T_c$ 随着 $k$ 增大而增大、减小

• 具体实现参考https://www.mit.edu/~andoni/LSH/manual.pdf

限制搜索空间

• 哈希表数量 $L$ 较多时，所有碰撞样本数量可能非常大，考虑只选择 $3L$ 个样本点

• 此时每个哈希键位长 $k$、哈希表数量 $L$ 保证以下条件，则算法正确

  • 若存在 $v^{ }$ 距离待检索点 $q$ 距离小于 $r_1$，则存在 $g_j(v^{ }) = g_j(q)$

  • 与 $q$ 距离大于 $r_2$、可能和 $q$ 碰撞的点的数量小于 $3L$

    $$\sum_{j=1}^L |(P-B(q,r_2)) \cap g_j^{-1}(g_j(q))| < 3L$$

• 可以证明，$k, L$ 取以下值时，以上两个条件以常数概率成立 （此性质是局部敏感函数性质，不要求是 $E^2LSH$）

  $$\begin{align*} k & = log_{1/p_2} n\\ L & = n^{\rho} \\ \rho & = \frac {ln 1/p_1} {ln 1/p_2} \end{align*}$$

• $\rho$ 对算法效率起决定性作用，且有以下定理

  • 距离尺度 $D$ 下，若 $H$ 为 $(R,cR,p1,p_2)$-敏感哈希函数族，则存在适合 (R,c)-NN 的算法，其空间复杂度为 $O(dn + n^{1+\rho})$、查询时间为 $O(n^{\rho})$ 倍距离计算、哈希函数计算为 $O(n^{\rho} log{1/p_2}n)$， 其中 $\rho = \frac {ln 1/p_1} {ln 1/p_2}$

  • $r$ 足够大、充分远离 0 时，$\rho$ 对其不是很敏感
  • $p1, p_2$ 随 $r$ 增大而增大，而 $k = log{1/p_2} n$ 也随之增大，所以 $r$ 不能取过大值

Scalable LSH

Scalable LSH：可扩展的 LSH

• 对动态变化的数据集，固定哈希编码的局部敏感哈希方法对数据 动态支持性有限，无法很好的适应数据集动态变化

  • 受限于初始数据集分布特性，无法持续保证有效性
  • 虽然在原理上支持数据集动态变化，但若数据集大小发生较大变化，则其相应哈希参数（如哈希编码长度）等需要随之调整，需要从新索引整个数据库

• 在 $E^2LSH$ 基础上通过 动态增强哈希键长，增强哈希函数区分能力，实现可扩展 LSH

Gredient Boosting

GB：（利用）梯度提升，将提升问题视为优化问题，前向分步算法 利用最速下降思想实现

• 一阶展开拟合损失函数，沿负梯度方向迭代更新

  • 损失函数中，模型的样本预测值$f(x)$是因变量
  • 即$f(x)$应该沿着损失函数负梯度方向变化
  • 即下个基学习器应该以负梯度方向作为优化目标，即负梯度 作为伪残差

  • 类似复合函数求导

• 对基学习器预测值求解最优加权系数

  • 最速下降法中求解更新步长体现
  • 前向分布算法中求解基学习器权重

损失函数

基学习器拟合目标：损失函数的负梯度在当前模型的值

$$-\left [ \frac {\partial L(y, \hat y_i)} {\partial y_i} \right ]_{\hat y_i=\hat y_i^{(t-1)}}$$

平方损失

平方损失：$L(y, f(x)) = \frac 1 2 (y - f(x))^2$（回归）

• 第m-1个基学习器伪残差为

  $$r_{m,i} = y_i - f_{m-1}(x_i), i=1,2,\cdots,N$$

  • $N$：样本数量

• 第m个基学习器为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N \frac 1 2 (y_i - (f_{m-1}(x_i) + h(x)))^2 \\ & = \arg\min_h \sum_{i=1}^N \frac 1 2 (C_{m,i} - h(x))^2 \\ C_{m,i} & = y_i - f_{m-1}(x_i) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

  • $\alpha_m$：学习率，留给之后基模型学习空间

  • 这里只是形式上表示模型叠加，实际上树模型等不可加， 应该是模型预测结果叠加

指数损失

指数损失：$L(y, f(x)) = e^{-y f(x)}$（分类）

• 第m-1个基学习器伪残差

  $$r_{m,i} = -y_i e^{-y_i f_{m-1}(x_i)}, i=1,2,\cdots,N$$

• 基学习器、权重为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha f(x_i))) \\ & = \arg\min_h \sum_{i=1}^N C_{m,i} exp(-y_i \alpha f(x_i)) \\ C_{m,i} & = exp(-y_i f_{m-1}(x_i)) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 损失函数$L(y, f(x))$

  • $x_i \in \mathcal{X \subset R^n}$
  • $y_i \in \mathcal{Y} = {-1, +1 }$

• 输出：回归树$\hat f(x)$

• 初始化模型

  $$\hat y_i^{(0)} = \arg\min_{\hat y} \sum_{i=1}^N L(y_i, \hat y)$$

• 对$m=1,2,\cdots,M$（即训练M个若分类器）

  • 计算伪残差

    $$r_i^{(t)} = -\left [ \frac {\partial L(y, \hat y_i)} {\partial y_i} \right ]_{\hat y_i=\hat y_i^{(t-1)}}$$

  • 基于${(x_i, r_i^{(t)})}$生成基学习器$h_t(x)$

  • 计算最优系数

    $$\gamma = \arg\min_\gamma \sum_{i=1}^N L(y_i, \hat y_i^{(t-1)} + \gamma h_t(x_i))$$

  • 更新预测值

    $$\hat y_i^{(t)} = \hat y_i^{(t-1)} + \gamma_t h_t (x)$$

• 得到最终模型

  $$\hat f(x) = f_M(x) = \sum_{t=1}^M \gamma_t h_t(x)$$

Gradient Boosted Desicion Tree

GBDT：梯度提升树，以回归树为基学习器的梯度提升方法

• GBDT会累加所有树的结果，本质上是回归模型（毕竟梯度）

  • 所以一般使用CART回归树做基学习器
  • 当然可以实现分类效果

• 损失函数为平方损失（毕竟回归），则相应伪损失/残差

  $$r_{t,i} = y_i - f_{t-1}(x_i), i=1,2,\cdots,N$$

特点

• 准确率、效率相较于RF有一定提升
• 能够灵活的处理多类型数据
• Boosting类算法固有的基学习器之间存在依赖，难以并行训练 数据，比较可行的并行方案是在每轮选取最优特征切分时，并行 处理特征

XGBoost

Extreme Gradient Boost/Newton Boosting：前向分步算法利用 Newton法思想实现

• 二阶展开拟合损失函数

  • 损失函数中，模型的样本预测值$\hat y_i$是因变量
  • 将损失函数对$\hat y_i$二阶展开拟合
  • 求解使得损失函数最小参数

• 对基学习器预测值求解最优加权系数

  • 阻尼Newton法求解更新步长体现
  • 前向分布算法中求解基学习器权重
  • 削弱单个基学习器影响，让后续基学习器有更大学习空间

损失函数

• 第t个基分类器损失函数

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & = \sum_i^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \Omega(f_t) \\ & = \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ \Omega(f_t) & = \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \end{align*}$$

  • $f_t$：第t个基学习器
  • $f_t(x_i)$：第t个基学习器对样本$x_i$的取值
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $\Omega(f_t)$：单个基学习器的复杂度罚
  • $T_t$：第t个基学习器参数数量，即$L_0$罚

    • 线性回归基学习器：回归系数数量
    • 回归树基学习器：叶子节点数目

  • $\gamma$：基学习器$L_0$罚系数，模型复杂度惩罚系数
  • $w_j = f_t$：第t个基学习器参数值，即$L_2$罚

    • 线性回归基学习器：回归系数值
    • 回归树基学习器：叶子节点

  • $\lambda$：基学习器$L_2$罚系数，模型贡献惩罚系数
  • $\approx$：由二阶泰勒展开近似

• 对损失函数进行二阶泰勒展开（类似牛顿法）拟合原损失函数， 同时利用一阶、二阶导数求解下个迭代点

• 正则项以控制模型复杂度

  • 降低模型估计误差，避免过拟合
  • $L_2$正则项也控制基学习器的学习量，给后续学习器留下 学习空间

树基学习器

XGBoost Tree：以回归树为基学习器的XGBoost模型

• 模型结构说明

  • 基学习器类型：CART
  • 叶子节点取值作惩罚：各叶子节点取值差别不应过大，否则 说明模型不稳定，稍微改变输入值即导致输出剧烈变化
  • 树复杂度惩罚：叶子结点数量

• XGBoost最终损失（结构风险）有

  $$\begin{align*} R_{srm} & = \sum_{i=1}^N l(y_i, \hat y_i) + \sum_{t=1}^M \Omega(f_t) \end{align*}$$

  • $N, M$：样本量、基学习器数量
  • $\hat y_i$：样本$i$最终预测结果

损失函数

• 以树作基学习器时，第$t$基学习器损失函数为

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ & = \sum_{j=1}^{T_t} [(\sum_{i \in I_j} g_i) w_j^{(t)} + \frac 1 2 (\sum_{i \in I_j} h_i + \lambda) {w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda){w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda)(w_j^{(t)})^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ \end{align*}$$

  • $f_t, T_t$：第t棵回归树、树叶子节点
  • $f_t(x_i)$：第t棵回归树对样本$x_i$的预测得分
  • $w_j^{(t)} = f_t(x)$：第t棵树中第j叶子节点预测得分
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $I_j$：第j个叶结点集合
  • $Gj = \sum{i \in I_j} g_i$
  • $Hj = \sum{i \in I_j} h_i$

  • 对回归树，正则项中含有$(w_j^{(t)})^2$作为惩罚，能够 和损失函数二阶导合并，不影响计算

  • 模型复杂度惩罚项惩罚项是针对树的，定义在叶子节点上， 而平方损失是定义在样本上，合并时将其改写

• 第t棵树的整体损失等于其各叶子结点损失加和，且 各叶子结点取值之间独立

  • 则第t棵树各叶子结点使得损失最小的最优取值如下 （$G_j, H_j$是之前所有树的预测得分和的梯度取值，在 当前整棵树的构建中是定值，所以节点包含样本确定后， 最优取值即可确定）

    $$w_j^{(*)} = -\frac {\sum_{i \in I_j} g_i} {\sum_{i \in I_j} h_i + \lambda} = -\frac {G_j} {H_j + \lambda}$$

  • 整棵树结构分数（最小损失）带入即可得

    $$obj^{(t)} = -\frac 1 2 \sum_{j=i}^M \frac {G_j^2} {H_j + \lambda} + \gamma T$$

  • 则在结点分裂为新节点时，树损失变化量为

    $$l_{split} = \frac 1 2 \left [ \frac {(\sum_{i \in I_L} g_i)^2} {\sum_{i \in I_L h_i} + \lambda} + \frac {(\sum_{i \in I_R} g_i)^2} {\sum_{i \in I_R h_i} + \lambda} - \frac {(\sum_{i \in I} g_i)^2} {\sum_{i \in I h_i} + \lambda} \right ] - \gamma$$

    • $I_L, I_R$：结点分裂出的左、右结点

• 则最后应根据树损失变化量确定分裂节点、完成树的分裂，精确 贪心分裂算法如下

  !xgb_exact_greedy_algorithm_for_split_finding

  • 对于连续型特征需遍历所有可能切分点

    • 对特征排序
    • 遍历数据，计算上式给出的梯度统计量、损失变化

  • 不适合数据量非常大、或分布式场景

模型细节

• shrinkage：对新学习的树使用系数$\eta$收缩权重

  • 类似SGD中学习率，降低单棵树的影响，给后续基模型留下 学习空间

• column subsampling：列抽样

  • 效果较传统的行抽样防止过拟合效果更好 （XGB也支持行抽样）
  • 加速计算速度

XGB树分裂算法

• 线性回归作为基学习器时，XGB相当于L0、L2正则化的 Logistic回归、线性回归

近似分割算法

XGB近似分割算法：根据特征分布选取分位数作为候选集，将连续 特征映射至候选点划分桶中，统计其中梯度值、计算最优分割点

!xgb_approximate_algorithm_for_split_finding

• 全局算法：在树构建初始阶段即计算出所有候选分割点，之后 所有构建过程均使用同样候选分割点

  • 每棵树只需计算一次分割点的，步骤少
  • 需要计算更多候选节点才能保证精度

• 局部算法：每次分裂都需要重新计算候选分割点

  • 计算步骤多
  • 总的需要计算的候选节点更少
  • 适合构建较深的树

• 分位点采样算法参见 ml_model/model_enhancement/gradient_boost

Sparsity-aware Split Finding

稀疏特点分裂算法：为每个树节点指定默认分裂方向，缺失值对应 样本归为该方向

• 仅处理非缺失值，算法复杂度和随无缺失数据集大小线性增加， 减少计算量

• 按照升许、降序分别扫描样本两轮，以便将缺失值样本分别归为 两子节点，确定最优默认分裂方向

  

XGB系统设计

Column Block for Parallel Learning

• 建树过程中最耗时的部分为寻找最优切分点，而其中最耗时部分 为数据排序

XGB对每列使用block结构存储数据

• 每列block内数据为CSC压缩格式

  • 特征排序一次，之后所有树构建可以复用（忽略缺失值）
  • 存储样本索引，以便计算样本梯度
  • 方便并行访问、处理所有列，寻找分裂点

• 精确贪心算法：将所有数据（某特征）放在同一block中

  • 可同时对所有叶子分裂点进行计算
  • 一次扫描即可得到所有叶子节点的分割特征点候选者统计 数据

• 近似算法：可以使用多个block、分布式存储数据子集

  • 对local策略提升更大，因为local策略需要多次生成分位点 候选集

Cache-aware Access

• 列block结构通过索引获取数据、计算梯度，会导致非连续内存 访问，降低CPU cache命中率

• 精确贪心算法：使用cache-aware prefetching

  • 对每个线程分配连续缓冲区，读取梯度信息存储其中，再 统计梯度信息
  • 对样本数量较大时更有效

• 近似算法：合理设置block大小为block中最多的样本数

  • 过大容易导致命中率低、过小导致并行化效率不高

Blocks for Out-of-core Computation

• 数据量过大不能全部存放在主存时，将数据划分为多个block 存放在磁盘上，使用独立线程将block读入主存 （这个是指数据划分为块存储、读取，不是列block）

• 磁盘IO提升

  • block compression：将block按列压缩，读取后使用额外 线程解压
  • block sharding：将数据分配至不同磁盘，分别使用线程 读取至内存缓冲区

分位点采样算法—XGB

Quantile Sketch

样本点权重

• 根据已经建立的$t-1$棵树可以得到数据集在已有模型上误差， 采样时根据误差对样本分配权重，对误差大样本采样粒度更大

• 将树按样本点计算损失改写如下

  $$\sum_{i=1}^N \frac 1 2 h_i(f_t(x_i) - \frac {g_i} {h_i})^2 + \Omega(f_t) + constant$$

• 则对各样本，其损失为$f_t(x_i) - \frac {g_i} {h_i}$ 平方和$h_i$乘积，考虑到$f_t(x_i)$为样本点在当前树预测 得分，则可以

  • 将样本点损失视为“二次损失”
  • 将$\frac {g_i} {h_i}$视为样本点“当前标签”
  • 相应将$h_i$视为样本点权重

• 样本权重取值示例

  • 二次损失：$h_i$总为2，相当于不带权
  • 交叉熵损失：$h_i=\hat y(1-\hat y)$为二次函数， 则$\hat y$接近0.5时权重取值大，此时该样本预测值 也确实不准确，符合预期

Rank函数

• 记集合$D={(x_1, h_1), \cdots, (x_n, h_n)}$

• 定义rank函数$r_D: R \rightarrow [0, +\infty)$如下

  $$r_D(z) = \frac 1 {\sum_{(x, h) \in D} h} \sum_{(x, h) \in D, x < z} h$$
  • 即集合$D$中权重分布中给定取值分位数
  • 即取值小于给定值样本加权占比，可视为加权秩

分位点抽样序列

• 分位点抽样即为从集合$D$特征值中抽样，找到升序点序列 $S = {s_1, \cdots, s_l}$满足

  $$|r_D(s_j - r_D(s_{j+1})| < \epsilon$$

  • $\epsilon$：采样率，序列长度$l = 1/\epsilon$
  • $s1 = \min{i} x_i$：特征最小值

  • $sl = \max{i} x_i$：特征最大值

  • 各样本等权分位点抽样已有成熟方法，加权分位点抽样方法 为XGB创新，如下

Weighted Quantile Sketch

Formalization

• 记$Dk={(x{1,k}, h1), \cdots, (x{n,k}, h_n)}$为各 训练样本第$k$维特征、对应二阶导数

  • 考虑到数据点可能具有相同$x, h$取值，$D_k$为可能包含 重复值的multi-set

• 对于多重集$D$，额外定义两个rank函数

  $$\begin{align*} r_D^{-}(y) & = \sum_{(x,h) \in D, x<y} h \\ r_D^{+}(y) & = \sum_{(x,h) \in D, x \leq y} h \end{align*}$$

  定义相应权重函数为

  $$w_D(y) = r_D^{+}(y) - r_D^{-}(y) = \sum_{(x,h) \in D, x=y} h$$

• 多重集$D$上全部权重和定义为

  $$w(D) = \sum_{(x, w) \in D} w$$

Quantile Summary of Weighted Data

• 定义加权数据上的quantile summary为 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • $S$为$D$中特征取值抽样升序序列，其最小、最大值分别 为$D$中特征最小、最大值

  • $\tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D$为定义在 $S$上的函数，满足

    $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \\ \tilde r_D^{-}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{-}(x_{i+1}) \\ \tilde r_D^{+}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{+}(x_{i+1}) \\ \end{align*}$$

• $Q(D)$满足如下条件时，称为 $\epsilon$-approximate quantile summary

  $$\forall y \in D_X, \tilde r_D^{+}(y) - \tilde r_D(y) - \tilde w_D(y) \leq \epsilon w(D)$$
  • 即对任意$y$的秩估计误差在$\epslion$之内

• $\phi-quantile$：秩位于$\phi * N$的元素（一般向下取整）
• $\epsilon-\phi-quantile$：秩位于区间 $[(\phi-\epsilon)N, (\phi+\epsilon)N]$的元素

构建$\epsilon$-Approximate Qunatile Summary

• 初始化：在小规模数据集 $D={(x_1,h_1), \cdots, (x_n,h_n)}$上构建初始 初始quantile summary $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 满足

  $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \end{align*}$$
  • 即初始化$Q(D)$为0-approximate summary

• merge operation：记 $Q(D1)=(S_1, \tilde r{D1}^{+}, \tilde r{D1}^{-}, \tilde w{D1})$、 $Q(D_2)=(S_2, \tilde r{D2}^{+}, \tilde r{D2}^{-}, \tilde w{D_2})$、 $D = D_1 \cup D_2$，则归并后的 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 定义为

  $$\begin{align*} S & S_1 \cup S_2 \\ \tilde r_D^{-}(x_i) & = \tilde r_{D_1}^{-}(x_i) + \tilde r_{D_2}^{-}(x_i) \\ \tilde r_D^{+}(x_i) & = \tilde r_{D_1}^{+}(x_i) + \tilde r_{D_2}^{+}(x_i) \\ \tilde w_D(x_i) & = \tilde w_{D_1}(x_i) + \tilde w_{D_2}(x_i) \end{align*}$$

• prune operation：从给定 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$， （其中$S = {x_1, \cdots, x_k }$），构建新的summary $\acute Q(D)=(\acute S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • 仅定义域从$S$按如下操作抽取 $\acute S={\acute x1, \cdots, \acute x{b+1}}$

    $$\acute x_i = g(Q, \frac {i-1} b w(D))$$

  • $g(Q, d)$为查询函数，对给定quantile summary $Q$、 秩$d$返回秩最接近$d$的元素

    

文本预处理

• 去除噪声文档、文档中垃圾数据
• 停用词去除
• 词根还原（英文）
• 分词（中文）
• 词性标注
• 短语识别
• 词频统计

汉语分词

分词：添加合适的显性词语边界标志，使所形成的词串反映句子本意

• 分词是正确处理中文信息的基础

  • 文本基于单字
  • 书面表达方式以汉字作为最小单位
  • 词之间没有显性界限标志

• 用单个汉字作特征，不考虑词语含义，直接利用汉字在文本中 出现的统计特性对文本进行划分

  • 直观明了
  • 操作简单
  • 对西语文本划分非常容易（使用空格划分）

• 使用词作为特征

  • 词是中文语义的最小信息单位，可以更好的反映句子中信息
  • 分析难度更高，中文文本中词之间没有分隔标记，正确分词 是关键

分词方法

• 基于词典

  • FMM：正向最大匹配分词
  • BMM：逆向最大匹配分词
  • BM法：双向扫描法
  • 逐词遍历

• 基于统计模型

  • N-最短路径
  • HMM
  • N元语法
  • 由字构词的汉语分词方法

分词难点

歧义切分

• 分词规范

  • 分词单位
    • 二字、三字以及结合紧密、使用稳定的
    • 四字成语
    • 四字词或结合紧密、使用稳定的四字词组
  • 五字、五字以上谚语、格言等，分开后如不违背原有组合 意义，应切分

• 歧义切分

  • 交集型切分歧义
  • 组合型切分歧义

未登录词识别

• 词表词：记录在词表中的词
• 未登录词：词表中没有的词、或已有训练语料中未曾出现词 （此时也称为out of vocabulary）

• 真实文本切分中，未登录词总数大约9成是专有名词，其余为 新词

• 未登录词对分词精度影响是歧义词的10倍

• 命名实体识别：实体名词、专业名词

  • 界定规则不存在太大分歧、构成形式有一定规律
  • 在文本中只占8.7%，引起分词错误率59.2%

词性标注

词性标注：在给定句子中判定每个词的语法范畴，确定词性并加以 标注的过程

• POS作为特征可以更好的识别词语之间关系

  • 词性标注计数为phrase chunking词组组块的界定、 entities and relationship实体与关系的识别打下良好 基础，有利于深入探索文本语义信息

  • 词组的形式提高了特征向量的语义含量，使得向量更稀疏

• 难点

  • 汉语缺乏词形态变化
  • 常用词兼类现象严重：占11%
  • 研究者主观原因：不同语料库有不同规定、划分方法

• part of speech：POS，词性

Forward Maximum Matching Method

FMM：正向最大匹配分词

• 步骤

  • 记词典中最长此表包含汉字数量为M
  • 从材料中选取前$m = M$个汉字去作为匹配字段，查找分词 词典
    • 若存在匹配词，则将其切分出
    • 否则$m = m - 1$，重复
  • 重复直至材料分词完毕

• 特点

  • 对交叉歧义、组合歧义没有解决办法
  • 错误切分率为$\frac 1 {169}$

Backward Maximum Matching Method

BMM：逆向最大匹配分词

• 步骤：类似FMM，仅从材料/句子末尾开始处理

• 特点

  • 错误切分率$\frac 1 {245}$，较FMM更有效

Bi-direction Matching Method

BM法：双向扫描法

• 步骤：比较FMM、BMM法切分结果，决定正确切分

• 特点

  • 可以识别分词中交叉语义

N-最短路径

• 思想

  • 考虑待切分字串$S=c_1 c_2 \cdots c_n$，其中$c_i$为 单个字、$n$为串长

  • 建立节点数为$n+1$的切分有向无环图，各节点编号为 $V_0, V_1, \cdots, V_n$

    • 相邻节点间存在边
    • 若$w=ci c{i+1} \cdots cj$是一个词，则节点 $v{i-1}, v_j$直接存在边
    • 所有边距离均为1

  • 求有图无环图中最短路径

特点

• 算法时间复杂度为$O(nNK)$

  • $n$：字串长度
  • $N$：最短路径数目
  • $k$：某个字作为词末端字的平均次数

改进—考虑噪声

基于统计信息的粗分模型

• 考虑词串$W$经过信道传输，由于噪声干扰丢失词界切分标志， 到输出端为字串$C$

• N-最短路径词语粗分模型可以改进为：求N个候选切分$W$，使得 概率$P(W|C)$为前N个最大值

  $$P(W|C) = \frac {P(W) P(C|W)} {P(C)}$$

  • $P(C)$：字串概率，常数
  • $P(C|W)$：仅有

• 采用一元统计模型，设$W=w_1w_2\cdots W_m$是字串 $S=c_1c_2\cdots c_n$的切分结果，则其切分概率为

  $$\begin{align*} P(W) & = \prod_{i=1}^m P(w_i) \\ P^{*}(W) = -ln P(w) = \sum_{i=1}^m (-ln P(W_i)) \end{align*}$$

  • $P(w_i)$：词$w_i$出现概率，在大规模预料训练的基础上 通过极大似然方法得到

• 则$-lnP(w_i)$可看作是词$w_i$在切分有向无环图中对应距离， 改进N-最短路径方法

由字构词

假设、背景

• 思想：将分词过程看作字分类问题，认为每个字在构造特定词语 时，占据确定的位置

• 中文词一般不超过4个字，字位数量很小
  • 首部B
  • 词中M
  • 词尾E
  • 单独成词S
• 部分汉字按一定方式分布，有规律
• 利用相对固定的字推断相对不定的字的位置问题
• 虽然无法将所有词列入词典，但字基本稳定

步骤

• 对所有字根据预定义的特征进行词位特征学习，获得概率 模型
• 在带待分字串上根据字与字之间的结合紧密程度得到词位的分类 结果
• 根据词位定义直接获得最终分词结果

Productivity

能产度：词$c_i$在词位$t_j$的能产度定义为

$$P_{c_i}(t_j) = \frac {count(c_i, t_j)} \sum_{t_j \in T} count(c_i, t_j)$$

• $T = {B, B_2, B_3, M, E, S}$

• 主词位：给定字在其上能产度高于0.5的词位

  |标记|B|B2|B3|M|E|S|总字量| |——-|——-|——-|——-|——-|——-|——-|——-| |字量|1634|156|27|33|1438|632|3920| |百分比|31.74|3.03|0.52|0.64|27.94|12.28|76.16|

  • MSRA2005语料库中有主词位的字量分布

• 自由字：没有主词位的字

  • 自由字是基于词位分类的分词操作得以有效进行的的基础 之一

• 字：不仅限于汉字，包括标点、外文字母、注音符号、数字等 任何可能文字符号

优势

• 能平衡词表词、未登录词
• 简化分词系统设计
  • 无需强调词表词信息
  • 无需设置特定未登录词识别模块

分词评价指标

• 正确率
• 召回率
• F-测度值

Vector Space Model

向量空间模型：自然语言处理常用模型

• document：文档，句子、段落、整篇文章
• term/feature：词根、词、短语、其他
• weight：项的权重，每个特征项在文档中重要程度

相似度比较

• 内积

  $$sim(D_1, D_2) = \sum_{k=1}^n w_{1,k} w_{2,k}$$

• Cosine相似度

  $$cos(D_1, D_2) = cos \theta = \frac {\sum_{k=1}^n w_{1,k} w_{2,k}} {\sqrt{\sum_{k=1}^n w_{1,k}^2 \sum_{k=1}^n w_{2,k}^2}}$$

权重

• 布尔权重：$bw_{t,d} = {0, 1}$
• TF：绝对词频，$TF{t,d} = \frac {n{t,d}} {n_d}$
• IDF：倒排文档频度，$IDF_{t,d} = log \frac M {m_t}$
• TF-IDF：$TF-IDF{t,d} = TF{t,d} * IDF_{t,d}$
• TF-IWF：$TFIWF{t,d}= TF{t,d} log \frac {\sum{t=1}^T \sum{d=1}^N n{t,d}} {\sum{t=1} n{t,d}}$

• $t_{t,d}$：文档$d$中出现特征$t$的次数
• $t_d$：文档$d$中出现总词数
• $m_t$：训练集中出现特征$t$文档数
• $M$：训练集中文档总数
• $K$：特征总数量

特征加权

• 特征加权主要包括三个部分（层次）

  • 局部加权：使用词语在文档中的统计量
  • 全局加权：词语在整个数据集中的统计量
  • 标准化

• 一般化特征加权表达式

  $$L_d(w) G(w) N_d$$

  • $L_d(w)$：词$w$在文档$d$中的局部权重
  • $G(w)$：词$w$在文档集合中的全局权重
  • $N_d$：文档d的标准化因子

Document Frequency

DF：文档频率，文本数据中包含某词条的文档数目

• 通过文档频率进行特征选择：按文档频率大小对词条进行排序

  • 将DF小于某阈值的词删除

    • 稀有词项全局影响力不大
    • 文档若有稀有词向，通常也会有常见词项

    • 和通常信息获取观念抵触：稀有更有代表性

  • 将DF大于某阈值的词删除

    • 太频繁词词项没有区分度

• 容易实现、可扩展性好

其他指标

• 信息增益/互信息

• 卡方统计量

Latent Semantic Analysis

LSA：潜在语义分析

• 文本分析中常用的降维技术

  • 特征重构方法
  • 很好解决了同义词、一词多义等现象给文本分析造成的困难

• 理论依据、假设

  • 认为有潜在语义结构隐含在文档中词语的上下文使用模式中
  • 而文档词频共现矩阵在一定程度可以反映词和不同主题之间 关系

• 以文档词频矩阵为基础进行分析

  • 得到向量空间模型中文档、词的高维表示
  • 并通过投影形成文档、词在潜在语义空间中的相对稠密的 低维表示，缩小问题规模
  • 通过这种低维表示解释出“文档-语义-词语”之间的联系

• 数学描述

  • LSA将每个文本视为以词语/特征为维度的空间的点，包含 语义的文本出现在空间中分布服从某种语义结构
  • LSA将每个词视为以文档为维度的空间中点
  • 文档由词语构成，词语需要放在文档中理解，体现词语和 文档之间的双重概率关系

应用SVD分解

• 词频共现矩阵$X=(x_{d,t})$：文档、词语的共现频率矩阵

  • 其中每行代表文档向量
  • 每列代表词语向量
  • 元素$x_{d,t}$表示文档$d$中词$t$出现的频率

• 对词频共现矩阵$X$进行SVD分解得到$X=U \Sigma V^T$

• 仅保留$\Sigma$中满足阈值要求的较大的前$r$特征值， 其余置为0，得到 $\tilde X = \tilde U \tilde \Sigma \tilde V^T$，达到信息 过滤、去除噪声的目的

  • $A = \tilde X$：矩阵特征分解后的文档词频矩阵近似
  • $T = \tilde U$：文档和潜在语义的关系矩阵近似
  • $S = \tilde V$：词语和潜在语义的关系矩阵近似
  • $D = \tilde \Sigma$：各潜在语义的重要程度

说明

• 从数据压缩角度：近似矩阵是秩为$K$的前提下，矩阵$X$的最小 二乘意义下最佳近似

• r值过大会增加运算量，一般选择K使得贡献率满足

  $$\sum_{i=1}^r d_i / \sum_{i=1}^K d_i \geq \theta$$

  • $\theta$：阈值
  • $K$：原始词频共现矩阵秩

• LSA缺点

  • SVD的向量元素有正、有负，性质难以解释
  • SVD的实际意义不够明确，难以控制词义据类的效果
  • 涉及高维矩阵运算

相似关系计算

• 潜在语义空间中存在：词-词、文本-文本、词-文本3种关系， 可以通过近似矩阵$T, S, D$计算

• 比较词汇两两相似度：“正向乘法”

  $$A A^T = T S D^T D S^T T^T = T S^2 T^T$$

• 比较文本两两相似度：“逆向乘法”

  $$A^T A = T^T S^T D D^T S T = T^T S^2 T$$

• 词汇、文本两两相似度：就是原始矩阵$X$的近似矩阵本身$A$

  $$A = T * S * D^T$$

混淆矩阵

• 对比实际类别值、预测类别值，编制混淆矩阵
• 基于混淆矩阵，计算各类错判率、总错判率（总错判率会受到数据不平衡性的影响）

F-Measure

F-测度：准率率和召回率综合值，越大越好

$$F-measure = \frac {(\beta^2 + 1) * P * R} {\beta^2 * P + R}$$

• $P = \frac {TP} {TP+FP}$：查准率、精确率
• $R = \frac {TP} {TP+FN}$：查全率、召回率、覆盖率

F1 值

F1值：$\beta=1$ 时的 F测度

$$\begin{align*} \frac {1} {F_{1}} &= \frac {1} {2} \left( \frac {1} {P} + \frac {1} {R} \right) \\ \Rightarrow F_{1} &= \frac {2 * P * R} {P + R} = \frac {2 * TP} {样例总数 + TP - TN} \end{align*}$$

TPR、FPR

• TPR、FPR 可视为对 TP、FP 用样本数量归一化的结果

  • 样本全体中正、负样本数量往往差距很大，直接比较 TP、FP 不合理
  • 考虑使用样本正、负数量归一化，即计算正比例 TPR、负比例 FPR

• TPR 越高越好，FPR 越低越好，但是这两个指标相互制约，两者同时增加、减小

  • 模型倾向于将样本 判定为 为正例，则 TP、FP 同时增加，TPR、FPR 同时变大
  • 即模型取不同阈值，会产生正相关的 TPR、FPR 的点列

Recevier Operating Characteristic Curve

ROC 曲线：不同 正样本概率 划分阈值下 TPR、FPR 绘制的折线/曲线

$$TPR = \frac {TP} {TP+FN} \\ FPR = \frac {FP} {FP+TN}$$

• ROC 曲线即以 FPR 为横坐标、TPR 为正坐标绘制曲线

  • FPR 接近 1 时，TPR 也接近 1，这是不可避免的
  • 而 FPR 接近 0 时，TPR 越大越好
  • 所以模型 ROC 曲线下方面积越大，模型判断正确效果越好

• 理解

  • 将正负样本的正样本概率值分别绘制在 x=1、x=-1 两条直线上
  • 阈值即为 y=threshold 直线
  • TPR、FPR 则为 x=1、x=-1 两条直线在阈值直线上方点数量，与各直线上所有点数量比值

Accuracy

准确率、误分率：评价分类器性能一般指标

$$\begin{align*} acc & = \frac 1 N sign(y_i = \hat y_i) \\ & = \frac {TP+TN} N \\ mis & = 1 - acc \end{align*}$$

• $y_i$：第 $i$ 样本实际类别
• $\hat y_i$：第 $i$ 样本预测类别
• $N$：样本数量

• 对给定测试集，分类器正确分类样本数与总样本数比值
• 即 0-1 损失函数时经验风险

Top PR

头部准召：评估模型头部性能

$$pr_{top} = \frac {TP_{top}} {TOP}$$

• $TOP$：指定的头部数量
• $TP_{top}$：头部中正例数量（正例指已知原 $TOP$ 样本）

Area Under Curve

AUC 值：ROC 曲线下方面积，越大越好

• AUC 值实际含义：随机抽取一对正、负样本，对其中正样本的正样本预测概率值、大于负样本的正样本预测概率值的概率

  • $=1$：完美预测，存在一个阈值可以让模型 TPR 为 1，FPR 为 0
  • $(0.5, 1)$ ：优于随机预测，至少存在某个阈值，模型 $TPR > FPR$
  • $=0.5$：同随机预测，无价值
  • $[0, 0.5)$：差于随机预测，但是可以反向取预测值

AUC 计算

• 绘制 ROC 曲线，计算曲线下面积

  • 给定一系列阈值（最精确时为样本数量），分别计算 TPR、FPR
  • 根据 TPR、FPR 计算 AUC

• 正负样本分别配对，计算正样本预测概率大于负样本比例

  $$\begin{align*} auc & = \frac {\sum I(P_P > P_N)} {M * N} \\ I(P_P, P_N) & = \left \{ \begin{array}{l} 1, & P_P > P_N, \\ 0.5, & P_P = P_N, \\ 0, & P_P < P_N \end{array} \right. \end{align*}$$

  • $M, N$：正、负样本数量

• Mann-Witney U 检验：即正、负样本分别配对的简化公式

  $$auc = \frac {\sum_{i \in Pos} rank(i) - \frac {M * (M+1)} 2} {M * N}$$

  • $Pos$：正样本集合
  • $rank(i)$：样本 $i$ 的按正样本概率排序的秩（对正样本概率值相同样本，应将秩加和求平均保证其秩相等）

Weighted-AUC

WAUC：给 每个样本 赋权，计算统计量时考虑样本权重

• FPR、TPR 绘图

  $$\begin{align*} WTPR & = \frac {\sum_{i \in Pos} w_i I(\hat y_i=1)} {\sum_{i \in Pos} w_i} \\ WFPR & = \frac {\sum_{j \in Neg} w_j I(\hat y_j=1)} {\sum_{j \in Neg} w_j} \end{align*}$$

  • $WTPR, WFPR$：加权 TPR、加权 FPR
  • $\hat y_i$：样本预测类别
  • $w_i$：样本权重

• Mann-Witney U 检验：考虑其意义，带入权重即可得

  $$\begin{align*} auc = \frac {\sum_{i \in Pos} w_i * rank(i) - \sum_{i \in Pos} w_i * rank_{pos}(i)} {\sum_{i \in Pos} w_i * \sum_{j \in Neg} w_j} \end{align*}$$

  • $rank_{pos}(i)$：正样本内部排序，样本$i$秩
  • $Neg$：负样本集合

多分类 AUC

• Micro-AUC：将每个类别视为样本标签，计算全体样本的正标签、负标签的 AUC

  • $n$ 个样本的 $m$ 维标签展平， 则其中有 $n$ 个正样本、$n * (m-1)$ 个负样本
  • $n$ 个样本的 $m$ 个分类器共 $n * m$ 个得分展平
  • 使用以上预测得分、标签计算 AUC

  1 2 3 4 5 6 7 8 9 10

  # one-vs-rest分类器得分 y_score = classifer.transform(X_test) # 展平后计算fpr、tpr fpr_micro, tpr_micro, threshhold_micro = \ skilearn.metrics.roc_curve(y_test.ravel(), y_score.ravel()) # 利用fpr、tpr计算auc auc_micro = skilearn.metrics.auc(fpr_micro, tpr_micro) # 等价于直接调用 auc_micro = skilearn.metrics.roc_auc_score(y_test, y_score, average="micro")

• Macro-AUC：对各类别，分别以计算 ROC 曲线（即 TPR、FPR），计算平均 ROC 曲线得到 AUC

  • 对各类别分别计算 TPR、FPR，共 $m$ 组 TPR、FPR

  • 平均合并 TPR、FPR，计算 AUC

    • 方法1：合并 FPR、去除重复值，使用 $m$ 组 TPR、FPR 分别求合并后 FPR 插值

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

      # 分别计算各类别fpr、tpr fprs, tprs = [0] * n_classes, [0] * n_classes for idx in range(n_classes): fprs[idx], tprs[idx], _ = sklearn.metrics.ruc_curve( y_test[:, i], y_score[:, i]) # 合并fpr all_fpr = np.unique(np.concatenate(fprs)) mean_tpr = np.zeros_like(all_fpr) # 计算合并后fpr插值 for idx in range(n_classes): mean_tpr += scipy.interp(all_fpr, fpr[idx], tpr[idx]) mean_tpr /= n_classes auc_macro = sklearn.metrics.auc(all_fpr, mean_tpr) # 但是和以下结果不同 auc_macro = sklearn.metrics.roc_auc_score(fprs)

• 以上分类器均为 one-vs-rest 分类器，$m$ 个类别则 $m$ 个分类器、每个样本 $m$ 个得分

Kolmogorov-Smirnov 统计量

KS 值：刻画区分正负样本能力

$$KS = max \{|TPR - FPR|\}$$

• KS 值体现 最理想情况 下，对正负样本区分能力
  • 即 ROC 曲线与 $TPR = FPR$ 直线的最远距离

Squared Error

Mean Squared Error

MSE：均方误差（偏差）

$$MSE = \frac 1 n \sum_{i=1}^{n} (y_{i} - \hat{y_{i}})^{2}$$

Mean Absolute Error

MAE：平均绝对误差

$$MAE = \frac 1 n \sum_{i=1}^n |y_i - \hat {y_i}|$$

Mean Absolute Percentage Error

MAPE：平均绝对百分比误差

$$MAPE = \frac 1 n \sum_{i=1}^n |\frac {y_i - \hat {y_i}} {y_i}|$$

Symmetric Mean Absolute Percentage Error

SMAPE：对称平均绝对百分比误差

$$MAPE = \frac 1 n \sum_{i=1}^n |\frac {y_i - \hat {y_i}} {(|y_i| + |\hat {y_i}|) / 2}|$$

$R^2$

$$\begin{align*} R^2 & = 1 - \frac {SSE} {SST} = \frac {SSR} {SST} \\ R^2_{adj} & = 1 - \frac {1 - R^2} {n - p - 1} \end{align*}$$

• $n, p$：样本量、特征数量
• $SSE$：残差平方和
• $SSR$：回归平方和、组内平方和
• $SST$：离差平方和
• $R^2_{adj}$：调整的$R^2$

Akaike Information Criterion

AIC ：赤池信息准则

$$\begin{align*} AIC & = -2log(L(\hat \theta, x)) + 2p \\ & = nln(SSE/n) + 2p \end{align*}$$

• $n, p$：样本量、特征数量
• $\theta$：带估参数
• $L(\theta, x)$：似然函数
• $SSE$：残差平方和

Bayesian Information Criterion

BIC：贝叶斯信息准则

$$\begin{align*} BIC & = -2log(L(\hat \theta, x)) + ln(n)p \\ & = nln(SSE/n) + ln(n)p \end{align*}$$

$C_p$

$$\begin{align*} C_p & = \frac {SSE} {\hat {\sigma^2}} - n + 2p \\ & = (n - m - 1) \frac {SSE_p} {SSE_m} - n + 2p \end{align*}$$

• $p$：选模型特征子集中特征数量
• $m$：所有特征数量
• $SSE_p$：选模型中残差平方和
• $SSE_m$：全模型中残差平方和

名词

Statistic - Frequentist and Bayesian

统计：数学分支，概率论和优化的交集，是数据科学其他分支的理论基础

• 分析方法：验证式分析

  • 统计建模：基于数据构建统计模型，并验证假设
  • 模型预测：运用模型对数据进行预测、分析

• 理论依据：模型驱动，严格的数理支撑

  • 理论体系
    • 概率论、信息论、计算理论、最优化理论、计算机学科等多个领域的交叉学科
    • 并在发展中形成独自的理论体系、方法论
  • 基本假设：同类数据具有一定的统计规律性，可以用概率统计方法加以处理，推断总体特征，如
    • 随机变量描述数据特征
    • 概率分布描述数据统计规律

• 分析对象：以样本为分析对象

  • 从数据出发，提取数据特征、抽象数据模型、发现数据知识，再回到对数据的分析与预测
  • 数据多种多样，包括数字、文字、图像、音视频及其组合
  • 假设数据独立同分布产生
  • 训练数据集往往是人工给出的

Data Mining

• 从现有的信息中提取数据的 pattern、model，即精选最重要、可理解的、有价值的信息

  • 核心目的在于找到 数据变量之间的关系
  • 不是证明假说的方法，而是构建假说的方法
  • 大数据 的发展，传统的数据分析方式无法处理大量“不相关”数据

• 常用技术

  • cluster analysis：聚类分析，揭示数据内在结构
  • classification：判别分析，数据预测
  • regression/decision trees：决策树，模型图形化展示
  • neural networks：神经网络

• 联系

  • 本质上看起来像是 ML、AI 的基础
  • 会使用大量机器学习算法，但是特定的环境、目的和ML不同

• 建模一般策略：类似机器学习

  • 将数据视为高维空间中的点，在高维空间中找到分类面、回归面

Artificial Intelligence

• 研究如何创造智能 agent，并不一定涉及学习、归纳
• 但是大部分情况下，智能 需要从过去的经验中进行归纳，所以 AI 中很大一部分是 ML

Machine Learning

机器学习：从有限观测数据中学习一般性规律，并将规律应用到未观测样本中进行预测（最基本的就是在不确定中得出结论）

• 分析方法：归纳式、探索式分析
• 理论依据：数据驱动，从数据中中学习知识，
• 分析对象：对样本要求低，样本往往不具有随机样本的特征
• 机器学习建模：不假设，通过对高维空间的搜索，找到数据隐藏规律的恰当概括

Shallow Learning

浅层学习：不涉及特征学习，特征抽取依靠人工经验、特征转换方法

• 传统机器学习可以视为浅层学习

• 步骤

  • 数据预处理
  • 特征提取
  • 特征转换
  • 预测

Deep Learning

深度学习：将原始数据特征通过多步特征转换得到更高层次、抽象的特征表示，进一步输入到预测函数得到最终结果

• 主要目的是从数据中自动学习到有效的特征表示

  • 替代人工设计的特征，避免“特征”工程
  • 模型深度不断增加，特征表示能力越强，后续预测更容易

• 相较于浅层学习：需要解决的关键问题是贡献度分配问题

  • 从某种意义上说，深度学习也可以视为强化学习
  • 内部组件不能直接得到监督信息，需要通过整个模型的最终监督信息得到，有延时

• 目前深度学习模型主要是神经网络模型

  • 神经网络可以使用反向传播算法，较好的解决贡献度分配问题

• credit assignment problem：贡献度分配问题，系统中不同组件、参数对最终系统输出结果的贡献、影响

• 深度：原始数据进行非线性特征转换的次数，将深度学习系统看作有向图结构，深度可以看作是从输入节点到输出节点经过最长路径长度

Representing Learning

表示学习：自动学习有效特征、提高最终机器学习模型性能的学习

• 好的学习标准

  • 较强的表示能力：同样大小向量可以表示更多信息
  • 简化后续学习任务：需要包含更高层次语义信息
  • 具有一般性，是任务、领域独立的：期望学到的表示可以容易迁移到其他任务

• 要学习好的高层语义（分布式表示），需要从底层特征开始，经过多步非线程转换得到

  • 深层结构的优点式可以增加特征重用性，指数级增加表示能力
  • 所以表示学习的关键是构建具有一定深度、多层次特征表示

• 传统机器学习中也有关于特征学习的算法，如：主成分分析、线性判别分析、独立成分分析

  • 通过认为设计准则，用于选取有效特征
  • 特征学习、最终预测模型的学习是分开进行的，学习到的特征不一定可以用于提升最终模型分类性能

• Semantic Gap：语义鸿沟，输入数据底层特征和高层语义信息之间不一致性、差异性

表示

• Local Representation：局部表示，离散表示/符号表示

  • 通常可以表示为 one-hot 向量形式
    • 每个特征作为高维局部表示空间中轴上点
  • 不足
    • one-hot 维数很高、不方便扩展
    • 不同特征取值相似度无法衡量

• Distributed Representation：分布式表示

  • 通常可以表示为 低维、稠密 向量
    • 分散在整个低维嵌入空间中中
  • 表示能力强于局部表示
    • 维数低
    • 容易计算相似度

• 神经网络可以用于将高维局部空间 $R^{|V|}$ 映射到非常低维分布式表示空间 $R^d$

End-to-End Learning

端到端学习/训练：学习过程中不进行分模块、分阶段训练，直接优化任务的总体目标

• 不需要给出不同模块、阶段功能，中间过程不需要认为干预
• 训练数据为“输入-输出”对形式，无需提供其他额外信息
• 和深度学习一样，都是要解决“贡献度分配”问题
  • 大部分神经网络模型的深度学习可以看作是端到端学习

Learning Components

Model/Hypothesis/Opimizee/Learner/Learning Algorithm

模型/假说/优化对象/学习器/学习算法：待学习的条件概率分布 $P(Y|X)$、决策函数 $Y=f(X)$

• 概率模型：适合用条件概率分布 $P(Y|X)$ 表示的模型
• 非概率模型：用决策函数 $Y=f(x)$ 表示的模型

• learner：某类模型的总称
• hypothesis：训练好的模型实例，有时也被强调作为学习器应用在某个样本集（如训练集）上得到的结果
• learning algorithm：模型、策略、算法三者的模型总体

Hypothesis Space

假设空间：特征空间（输入空间）到输出空间的映射集合

• 假设空间可以定义为决策函数/条件概率的集合，通常是由参数向量 $\theta$ 决定的函数/条件分布族

  • 假设空间包含所有可能的条件概率分布或决策函数
  • 假设空间的确定意味着学习范围的确定

• 概率模型假设空间可表示为：$F={P|P_{\theta}(Y|X), \theta \in R^n}$

• 非概率模型假设空间可表示为：$F={f|Y=f(x),\Theta \in R^n }$

• 以下大部分情况使用决策函数，同时也可以代表概率分布

Strategy/Goal

策略/目标：从假设空间中，根据 evaluation criterion 选择最优模型，使得其对已知训练数据、未知训练数据在给定评价准则下有最优预测

• 选择合适策略，监督学习问题变为经验风险、结构风险函数 最优化问题

• 在某些学习方法中，最优化问题目标函数也有可能不是风险函数，如：SVM，是和模型紧密相关的损失函数，但逻辑是一样的

Empirical Risk Minimiation

ERM：经验风险最小化策略认为，经验风险最小模型就是最优模型

• 按经验风险最小化求最优模型，等价于求最优化问题

  $$\min_{f \in F} \frac 1 N \sum_{i=1}^N L(y_i, f(x_i))$$

• 样本容量足够大时，经验风险最小化能保证有较好的学习效果，现实中也被广泛采用

Structural Risk Minimization

SRM：结构风险最小化，为防止过拟合提出的策略

• 结构化风险最小化策略认为结构风险最小的模型是最优模型，则求解最优模型等价于求解最优化问题

  $$arg \min_{f \in F} \frac 1 N \sum_{i=1}^N L(y_i, f(x_i)) + \lambda J(f)$$

• 结构风险小需要经验风险与模型复杂度同时小，此时模型往往对训练数据、未知的测试数据都有较好的预测

• 结构化风险最小策略符合 Occam’s Razor 原理

• Occam’s Razor：奥卡姆剃刀原理，在所有可能选择的模型中，能够很好的解释已知数据并且十分简单才是最好的模型

Algorithm/Optimizer

算法/优化器：学习模型（选择、求解最优模型）的具体计算方法 （求解最优化问题）

• 如果最优化问题有显式解析解，比较简单

• 但通常解析解不存在，需要用数值计算方法求解

  • 保证找到全局最优解
  • 高效求解

Supervised Learning

监督学习：学习一个模型，使得模型能够对任意给定输入、输出，做出好的预测

• 从给定的、有限的、用于学习的 train data $T={(x_1,y_1), (x_2,y_2), \cdots, (x_N, y_N)}$ 中学习

• 预测 “未知” test data $T={(x_1,y_1), (x_2,y_2), \cdots, (x_N^{‘}, y_N^{‘})}$

数据

• input space：输入空间 $\chi$，所有输入 $X$ 可能取值的集合
• output space：输出空间 $\gamma$，所有输出 $Y$ 可能取值集合
• feature space：特征空间，表示输入实例 feature vector 存在的空间
  • 特征空间每维对应一个特征
  • 模型实际上是定义在特征空间上的
  • 特征空间是输入空间的象集，有时等于输入空间

学习方法分类

Generative Approach

生成方法：由数据学习联合概率分布 $P(X, Y)$，然后求出条件概率分布 $P(Y|X)$ 作为 generative model

• 方法学习给定输入X产生输出Y的生成关系（联合概率分布）

• generative model：生成模型，由生成方法学习到的模型 $P(Y|X) = \frac {P(X, Y)} {P(X}$

  • 朴素贝叶斯法
  • 隐马尔可夫模型

• 特点

  • 可以还原联合概率分布 $P(X, Y)$
  • 生成方法学习收敛速度快，样本容量增加时，学习到的模型可以快速收敛到真实模型
  • 存在隐变量时，仍可以使用生成方法学习

Discriminative Approach

判别方法：由数据直接学习决策函数 $f(x)$、条件概率分布 $P(Y|X)$ 作为 discriminative model

• 判别方法关心的是对给定输入 $X$，预测输出$Y$

• discriminative model：判别模型

  • KNN
  • 感知机
  • 决策树
  • 逻辑回归
  • 最大熵模型
  • 支持向量机
  • 提升方法
  • 条件随机场

• 特点

  • 直接学习条件概率、决策函数
  • 直面预测，学习准确率更高
  • 可以对数据进行各种程度抽象、定义特征、使用特征，简化学习问题

问题分类

• well-posed problem：好解问题，指问题解应该满足以下条件

  • 解存在
  • 解唯一
  • 解行为随着初值连续变化

• ill-posed problem：病态问题，解不满足以上三个条件

Classification

分类问题：输出变量$Y$为有限个离散变量

• 学习过程：根据已知训练数据集，利用有效学习方法学习分类器 $P(Y|X))$、$Y=F(X)$
• 分类过程：利用学习的分类器对新输入实例进行分类

• 可用学习方法

  • KNN
  • 感知机
  • 朴素贝叶斯
  • 决策树
  • 决策列表
  • 逻辑回归
  • 支持向量机
  • 提升方法
  • 贝叶斯网络
  • 神经网络

• 不存在分类能力弱于随机预测的分类器（结论取反）

Tagging

标注问题：输入、输出 均为变量序列

• 可认为是分类问题的一个推广、更复杂 structure prediction 简单形式
• 学习过程：利用已知训练数据集构建条件概率分布模型 $P(Y^{(1)}, Y^{(2)}, \cdots, Y^{(n)}|X^{(1)}, X^{(2)}, \cdots, X^{(n)})$

  • $X^{(1)}, X^{(2)}, \cdots, X^{(n)}$：每个输入序列
  • $Y^{(1)}, Y^{(2)}, \cdots, Y^{(n)}$：所有可能标记

• 标注过程：按照学习到的条件概率分布，标记新的输入观测序列
• 可用模型
  • 隐马尔可夫模型
  • 条件随机场

Regression

回归问题：输入（自变量）、输出（因变量）均为连续变量

• 回归模型的拟合等价于函数拟合：选择函数曲线很好的拟合已知数据，且很好的预测未知数据
• 学习过程：基于训练数据构架模型（函数）$Y=f(X)$
  • 最常用损失函数是平方损失函数，此时可以使用最小二乘求解
• 预测过程：根据学习到函数模型确定相应输出

Unsupervised Learning

无监督学习：没有给定实现标记过的训练示例，自动对输入的数据进行分类

• 主要目标：预训练一般模型（称识别、编码）网络，供其他任务使用
• 目前为止，有监督模型一般比无监督的预训练模型表现得好
  • 主要原因：有监督模型对数据的 特性编码 更好

问题分类

Clustering 聚类

• Hierarchy Clustering
• K-means
• Mixture Models
• DBSCAN
• OPTICS Algorithm

Anomaly Detection 异常检测

• Local Outlier Factor

Neural Networks 神经网络

• Auto-encoders
• Deep Belief Nets
• Hebbian Learning
• Generative Adversarial Networks
• Self-organizing Map

隐变量学习

• Expectation-maximization Algorithm
• Methods of Moments
• bind signal separation techniques
  • Principal Component analysis
  • Independent Component analysis
  • Non-negative matrix factorization
  • Singular Value Decomposition

Semi-Supervised Learning

半监督学习：利用少量标注数据和大量无标注数据进行学习的方式

• 可以利用大量无标注数据提高监督学习的效果

Reinforcement Learning

强化学习：从与环境交互中不断学习的问题、以及解决这类问题的方法

• 强化学习问题可以描述为：智能体从与环境的交互中不断学习以完成特定目标

• 强化学习的关键问题：贡献度分配问题

  • 每个动作不能直接得到监督信息，需要通过整个模型的最终 监督信息得到，且具有时延性
  • 给出的监督信息也非“正确”策略，而是策略的延迟回报，并通过调整策略以取得最大化期望回报

网络结构

• node/vertex：人
• link/edge：人与人之间的relation，可以有标签、权重、 方向
• graph/network：社交网络，表示个体之间的相互关系

• 图、网络参见cs_algorithm/data_structure/graph

基本统计指标、特性

• subnetwork/subgraph

  • singleton：单点集，没有边的子图
  • clique：派系，任意两个节点间均有连边的子图

• degree：

  • 对有向图可以分为out-degree、in-degree
  • average degree：网络平均度，所有节点度的算术平均
  • degree distribution：网络度分布，概率分布函数 $P(k)$

Path

• path length：路径长度
• shortest path：节点间最短路径
• distance：节点距离，节点间最短路径长度

• diameter：网络直径，任意两个节点间距离最大值

• 对规模（节点数量）为$N$大多数现实网络（尤其是社交网络）

  • 小直径：与六度分离实验相符
  • 存在巨大连通分支
  • 高聚类特性：具有较大点聚类系数
  • 明显的模块结构

• giant connected component：巨大连通分支，即规模达到 $O(N)$的连通分支

• node clustering coefficient：点聚类系数

  $$\begin{align*} NC_i & = \frac {triange_i} {triple_i} \\ NC & = \frac {\sum_i NC_i} N \end{align*}$$

  • $triangle_i$：包含节点$i$三角形数量
  • $triple_i$：与节点$i$相连三元组：包含节点$i$的三个 节点，且至少存在节点$i$ 到其他两个节点的两条边
  • $NC_i$：节点$i$聚类系数
  • $NC$：整个网络聚类系数

• edge clustering coefficient：边聚类系数

  $$EC_{ij} = \frac {|包含边<i,j>三角形|} {min\{(d_i-1), (d_j-1)\}}$$

  • $d_i$：节点$i$度，即分母为边$$最大可能存在于 的三角形数量

• edge betweenness：边介数，从源节点$v$出发、通过该边 的最短路径数目

边介数的计算

• 从源节点$i$出发，为每个节点$j$维护距离源节点最短路径 $d_j$、从源节点出发经过其到达其他节点最短路径数目$w_j$

  • 定义源节点$i$距离$d_i=0$、权值$w_i=1$

  • 对源节点$i$的邻接节点$j$，定义其距离$d_j=d_i+1$、 权值$w_j=w_i=1$

  • 对节点$j$的任意邻接节点$k$

    • 若$k$未被指定距离，则指定其距离$d_k=d_j+1$、 权值$w_k=w_j$
    • 若$k$被指定距离且$d_k=d_j+1$，则原权值增加1， 即$w_k=w_k+1$
    • 若$k$被指定距离且$d_k<d_j+1$，则跳过

  • 重复以上直至网络中包含节点的连通子图中节点均被指定 距离、权重

• 从节点$k$经过节点$j$到达源节点$i$的最短路径数目、与节点 $k$到达源节点$i$的最短路径数目之比为$w_i/w_j$

  • 从叶子节点$l$开始，若叶子节点$l$节点$i$相邻，则将 权值$w_i/w_l$赋给边$(i,l)$

  • 从底至上，边$(i,j)$赋值为该边之下的邻边权值之和加1 乘以$w_i/w_j$

  • 重复直至遍历图中所有节点

• 叶子节点：广度优先搜索叶子节点，即不被任何从源节点出发到 其他节点的最短路径经过
• 此边介数计算方式与节点介数中心性计算，都是寻找通过边、 节点的最短路径数目，但是具体计算方式不同

最短路径唯一

• 考虑从任何节点间最短路径只有一条，则某节点到其他节点 的最短路径构成一棵最短路径树

• 找到最短路径树的叶子节点，为每条与叶子节点相连的边赋值 为1
• 自下而上为树中其他边赋值：边之下所有临边值之和加1
• 处理所有节点直至树根源节点时，各边相对于树根源节点的介数 即为其权重

• 对各节点分别重复以上即可得到各边对各节点介数，相总即可得 各边总边介数

Node Centrality

节点中心性：采用某种定量方法对每个节点处于网络中心地位的程度 进行刻画

• 描述整个网络是否存在核心、核心的状态

基于度

• Degree Centrality：度中心性

  $$DC_i = \frac {d_i} {N-1}$$

  • $d_i$：节点$i$的度

  • 衡量节点对促进网络传播过程发挥的作用

• eigenvector centrality：特征向量中心性

  $$ EC_i = $

• subgraph centrality：子图中心性

  $$ SC_i = $

基于路径数

• Betweenness Centrality：介数中心性

  $$BC_i = \frac 2 {(N-1)(N-2)} \sum_{j<k, j,k \neq i} \frac {p_{j,k}(i)} {p_{j,k}}$$

  • $p_{j,k}$：节点$j,k$间路径数量
  • $p_{j,k}(i)$：节点$j,k$间路径经过节点$i$路径数量

  • 衡量节点对其他节点间信息传输的潜在控制能力

• Closeness Centrality

  $$CC_i =$$

Community Structure

社团/模块/社区结构：内部联系紧密、外部联系稀疏（通过边数量 体现）的子图

基于连接频数的定义

$$\begin{align*} \sigma_{in}(S) & = \frac {|E(S)|} {|V(S)|(|V(S)|-1)/2} \\ \sigma_{out}(S) & = \frac {|E| - |E(S)|} {(N - |V(S)|)(N - |V_S| - 1) / 2} \\ \sigma(G) & = \frac {|E|} {|V|(|V|-1) / 2} \end{align*}$$

• $G, S$：全图、子图
• $\simga_{in}(S)$：子图$S$的内部连接率/频数
• $S_{in}$：子图$S$内部的实际边数
• $E, E(S)$：全图、子图$S$内部边
• $V, V(S)$：全图、子图$S$内部节点

• 若子图$S \subset G$满足如下，则称为网络$G$的社区

  $$\sigma_{in}(S) > \sigma(G) > \sigma_{out}(S)$$

强弱社区

• 强社区结构

  $$|E_{in}(S, i)| > |E_{out}(S, i)|, \forall i \in S$$

  • $E_{in}(S, i)$：节点$i$和子图$S$内节点连边
  • $E_{out}(S, i)$：节点$i$和子图$S$内节点连边

• 弱社区结构

  $$\sum_{i \in S} |E_{in}(S, i)| > \sum_{i \in S} |E_{out}(S, i)|, \forall i \in S$$

• 最弱社区结构

  $$\forall i \in S_j, |E_{in}(S_j, i)| > |E(S_j, i, S_k)|, j \neq k, k=1,2,\cdots,M$$

  • 社区$S_1,S_2,\cdots,S_M$是网络$G$中社区
  • $E(S_j, i, S_k)$：子图$S_j$中节点$i$与子图$S_k$之间 连边数

• 改进的弱社区结构：同时满足弱社区结构、最弱社区结构

LS集

LS集：任何真子集与集合内部连边数都多于与集合外部连边数 的节点集合

Clique

• 派系：节点数大于等于3的全连通子图

• n派系：任意两个顶点最多可以通过n-1个中介点连接

  • 对派系定义的弱化
  • 允许两社团的重叠

• 全连通子图：任意两个节点间均有连边

模块度函数Q

$$\begina{align*} Q & = \sum_{i} (e_{i,i} - \hat e_{i,i}) \\ & = \sum_{i} (e_{i,i} - a_i^2) \\ & = \sum_{i} (e_{i,i} - \sum_j e_{i,j}^2) & = Tre - \sum_{i,j} e_{i,j}^2 \end{align*}$$

• $\hat e_{i,i}$：随机网络中社区$i$内连边数占比期望
• $e_{i,j}$：社区$i,j$中节点间连边数在所有边中所占比例
• $ai = \sum_j e{i,j}$：与社区$i$中节点连边数比例

• 思想：随机网络不会具有明显社团结构

  • 不考虑节点所属社区在节点对间直接连边，则应有 $\hat e{i,j} = a_i a_j$，特别的 $\hat e{i,i} = a_i^2$

  • 比较社区实际覆盖度、随机连接覆盖度差异评估对社区结构 的划分

• 划分对应Q值越大，划分效果越好

  • $0< Q <1$：一般以$Q=0.3$作为网络具有明显社团结构的 下限
  • 实际网络中$Q{max} \in [0.3, 0.7]$，$Q{max}$越大 网络分裂（聚类）性质越强，社区结构越明显

• 缺点

  • 采用完全随机形式，无法避免重边、自环的存在，而现实 网络研究常采用简单图，所以Q值存在局限
  • Q值分辨能力有限，网络中规模较大社区会掩盖小社区， 即使其内部连接紧密

• 覆盖度：社区内部连接数占总连接数比例

模块密度D

$$\begin{align*} D & = \sum_{i=1}^M d(S_i) \\ & = \sum_{i=1}^K \frac {|E_{in}(S_i)| - |E_{out}(S_i)|} {|V_{in}(S_i)} \begin{align*}$$

• 模块密度D表示社区内部连边、社区间连边之差与社区节点总数 之比
  • 值越大表示划分结果越好
  • 考虑社区总节点数，克服模块度Q无法探测小社区的缺陷

社区度C

$$C = \frac 1 M \sum_{i=1}^M [\frac {|E_{in}(S_i)|} {|V(S_i)|(|V(S_i)| - 1) / 2} - \frac {|E_{out}(S_i)|} {|V(S_i)| (|V| - V(S_i)|}]$$

• $\frac {|E_{in}(S_i)} {|V(S_i)||(|V(S_i)-1)/2}$：社区 $S_i$的簇内密度
• $\frac {|E_{out}(S_i)} {|V(S_i)||(|V|-|V(S_i))}$：社区 $S_i$的簇内密度

Fitness函数

$$\begin{align*} f_i & = \frac {d_{in}(S_i)} {d_{in}(S_i) + d_{out}(S_i)} \\ & = \frac {2 * E_{in}(S_i)} {2 * E_{in}(S_i) + E_{out}(S_i)} \\ \bar f = \frac 1 M \sum_{i=1}^M f_i \end{align*}$$

• $f_i$：社区$S_i$的fitness函数
• $d{in}(S_i) = 2 * E{in}(S_i)$：社区$S_i$内部度
• $d{out}(S_i) = E{out}(S_i)$：社区$S_i$外部度
• $\bar f$：整个网络社区划分的fitness函数

• fitness函数使用直接的方式避开了模块度Q函数的弊端
  • 应用结果显示其为网络社区结构的有效度量标准

Modularity

$$Q = \frac 1 {2|E|} \sum_{i,j}$$

社区发现算法

网络测试集

• Girvan、Newman人工构造网络

  • 网络包含128个节点、平均分为4组
  • 每组内部连边、组间连边概率分别记为$p{in}, p{out}$
  • 要求每个节点度期望为16

• Lancichinet ti人工构造网络

  • 测试集中节点度、社区大小服从幂律分布
  • 混淆参数$\mu$控制社区结构显著程度

• 小规模、社区结构已知真实网络

  • Zachary空手道俱乐部
  • 海豚社会关系网络
  • 美国大学生足球俱乐部网络

社区发现算法

• Agglomerative Method：凝聚算法

  • NF算法
  • Walk Trap

Division Method：分裂算法

• Girvan-Newman算法
• 边聚类探测算法

• 凝聚算法流程

  • 最初每个节点各自成为独立社区
  • 按某种方法计算各社区之间相似性，选择相似性最高的社区 合并
    • 相关系数
    • 路径长度
    • 矩阵方法
  • 不断重复直至整个网络成为一个社区

• 算法流程可以的用世系图表示

  • 可以在任意合并步骤后停止，此时节点聚合情况即为网络中 社区结构
  • 但应该在度量标准值最大时停止

• 分裂算法流程同凝聚算法相反

Girvan-Newman算法

GN算法

• 流程

  • 计算网络中各边相对于可能源节点的边介数
  • 删除网络中边介数较大的边，每当分裂出新社区 （即产生新连通分支）
    • 计算网络的社区结构评价指标
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

• 缺点：计算速度满，边介数计算开销大，只适合处理中小规模 网络

Newman Fast Algorithm

NF快速算法：

• 流程

  • 初始化网络中各个节点为独立社区、矩阵$E={e_{i,j}}$

    $$\begin{align*} e_{i,j} & = \left \{ \begin{array}{l} \frac 1 {2M}, & 边(i,j)存在 \\ 0, & 节点间不存在边 \end{array} \right. \\ a_i & = \frac {d_i} {2M} \end{align*}$$

    • $M$：网络中边总数
    • $e_{i,j}$：网络中社区$i,j$节点边在所有边中占比
    • $a_i$：与社区$i$中节点相连边在所有边中占比

  • 依次合并有边相连的社区对，计算合并后模块度增量

    $$\Delta Q = e_{i,j} + e_{j,i} = 2(e_{i,j}-a_i a_j)$$
    • 根据贪婪思想，每次沿使得$Q$增加最多、减少最小 方向进行
    • 每次合并后更新元素$e_{i,j}$，将合并社区相关行、 列相加
    • 计算网络社区结构评价指标、网络结构

  • 重复直至整个网络合并成为一个社区，选择最优评价指标 对应网络社区结构

• 基于贪婪思想的凝聚算法

• GN算法、NF算法大多使用无权网络，一个可行的方案是计算无权 情况下各边介数，加权网络中各边介数为无权情况下个边介数 除以边权重

  • 此时，边权重越大介数越小，被移除概率越小，符合社区 结构划分定义

Edge-Clustering Detection Algorithm

边聚类探测算法：

• 流程：
  • 计算网络中尚存的边聚类系数值
  • 移除边聚类系数值最小者$(i,j)$，每当分裂出新社区 （即产生新连通分支）
    • 计算网络社区评价指标fitness、modularity
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

Walk Trap

随机游走算法：

Label Propagation

标签扩散算法：

Self-Similar

（网络结构）自相似性：局部在某种意义上与整体相似

• fractal分形的重要性质

Random Walk

（网络）随机游走：

游走形式

• unbiased random walks：无偏随机游走，等概率游走
• biased random walks：有偏随机游走，正比于节点度
• self-avoid walks：自规避随机游走
• quantum walks：量子游走

研究内容

• first-passage time：平均首达时间

  $$F(s,t)$$

• mean commute time：平均转移时间

  $$C(t,s) = F(s,t) + F(t,s)$$

• mean return time：平均返回时间

  $$T(s,s)$$

用途

• community detection：社区探测
• recommendation systems：推荐系统
• electrical networks：电力系统
• spanning trees：生成树
• infomation retrieval：信息检索
• natural language proessing：自然语言处理
• graph partitioning：图像分割
• random walk hypothesis：随机游走假设（经济学）
• pagerank algorithm：PageRank算法

网络可视化

Graph Layout

图布局：无实际意义但是影响网络直观效果

• random layout：随机布局，节点、边随机放置
• circular layout：节点放在圆环上
• grid layout：网格布局
• force-directed layout：力导向布局
  • 最常用
  • 动态、由节点相互连接决定布局
  • 点距离较近节点在放置在较近位置
• YiFan Hu layout
• Harel-Koren Fast Multiscale Layout
• NodeXL：节点以box形式被展示，边放置在box内、间

Visualizing Network Features

网络特征可视化：边权、节点特性、标签、团结构

• 标签：只显示感兴趣标签
• 度、中心性、权重等量化特征：借助大小、形状、颜色体现
• 节点分类信息：节点节点颜色、形状体现

Scale Issue

网络可视化：是否对所有网络均有可视化必要

• 网络密度太小、太大，无可视化必要

现实网络

• 网络科学：现实世界的任何问题都可以用复杂关系网络近似模拟

  • 节点：研究问题中主体
  • 边：模拟主体间的某种相互关系

• 现实网络大多为无标度网络，且幂指数$\gamma \in [2, 3]$

  • 网络中大部分节点度很小，小部分hub节点有很大的度
  • 对随机攻击稳健，但对目的攻击脆弱
  • triangle power law：网络中三角形数量服从幂律分布
  • eigenvalue power law：网络邻接矩阵的特征值服从 幂律分布

• 绝大多数现实网络、网络结构模型虽然不能只管看出自相性， 但是在某种length-scale下确实具有自相似性

  • 万维网
  • 社会网络
  • 蛋白质交互作用网络
  • 细胞网络

• 个体社会影响力：社交网络中节点中心性

• power-law distribution：幂律分布
• scale-free network：无标度网络，度分布服从幂律分布的 复杂网络，具有无标度特性
• heavy-tailed distribution：厚尾分布

社交网络

• 人、人与人之间的关系确定，则网络结构固定

• 有人类行为存在的任何领域都可以转化为社交网络形式

  • offline social networks：线下社交网络，现实面对面 接触中的人类行为产生，人类起源时即出现
  • online social networks/social webs：在线社交网络
  • social media websites：多媒体网社交网

• 由于社交网络中人类主观因素的存在，定性特征可以用于社交 网络分析

  • 关系强弱
  • 信任值

• 对网络结构的分析的数量化指标可以分析社交网络的基本特征

  • 度、度分布
  • 聚类系数
  • 路径长度
  • 网络直径

• 数据分析类型

  • Content Data：内容数据分析，文本、图像、其他多媒体 数据
  • Linkage Data：链接数据分析，网络的动力学行为：网络 结构、个体之间沟通交流

社交网络中社区发现

• 现实世界网络普遍具有模块/社区结构特性

  • 内部联系紧密、外部连接稀疏
  • 提取社区/模块结构，研究其特性有助于在网络动态演化 过程中理解、预测其自然出现的、关键的、具有因果关系的 本质特性

• 挑战

  • 现实问题对应的关系网络
    • 拓扑结构类型未知
    • 大部分为随时间变化网络
    • 规模庞大
  • 现有技术方法应用受到限制
    • 多数方法适用静态无向图，研究有向网络、随时间动态 演化网络形式技术方法较少
    • 传统算法可能不适用超大规模网络

• 社区发现/探测重要性

  • 社区结构刻画了网络中连边关系的局部聚集特性，体现了 连边的分布不均匀性
  • 社区通常由功能相近、性质相似的网络节点组成
    • 有助于揭示网络结构和功能之间的关系
    • 有助于更加有效的理解、开发网络