Matching

基于用户行为

离线协同过滤

• 根据用户行为日志，利用物品-based协同过滤生成离线的 物品2物品相似度矩阵、用户离线推荐结果

  • 基于艾宾浩斯遗忘曲线按照时间进行降权
  • 弱化热点影片的权重
  • 矩阵分解

• 基于用户的playlog接口实时获取用户的短时间内的观看历史， 通过物品2物品相似度矩阵进行CF扩散，提取出与用户短时间内 观看历史相似的topN个物品用于召回

• 用户的CF离线推荐结果直接作为线上服务的召回渠道

W2V

• 全部影片作为预料库、观看历史按时序排列视为文档，计算所有 物品的词向量

• 根据词向量计算物品2物品相似度矩阵，用于线上playlog召回 数据

LDA

• 基于概率主题模型：文档-潜在主题-词三级关系，映射/类比到 用户行为数据：用户-潜在兴趣-资源

• 通过用户历史行为记录，提取LDA中间产物、用户的潜在兴趣 向量、资源潜在主题分布向量

• 基于物品的主题向量，进行物品2物品相似度计算，用于线上 playlog召回数据

SimRank

• 将用户、物品关系视为二部图，考虑相似关系可以在图上传播 思想，使用SimRank计算物品相似队列

基于内容

基于标题

• 对影片文本简介使用doc2vector，计算资源的表示向量
• 使用资源的表示项集计算物品2物品相似度矩阵

基于Style

基于Tag

其他方向

• RNN捕捉用户在点击序列中的模式，利用点击行为发生先后顺序 调整推荐展示顺序

• Graph Embedding

Ranking

特征工程

• 低维稠密通用特征：泛化能力良好、记忆能力差

  • embedding特征
  • 统计特征

• 高维稠密特征：记忆能力较好

  • 视频ID
  • 标签
  • 主题

分类

• 按特征来源分类

  • 物品特征：资源风格、低于、类型、标签、统计特征
  • 用户特征：性别、年龄、婚姻状况、收入预测
  • context特征：网络状态、时间段、城市
  • 交叉特征

• 按特征更新频率、获取方式

  • 离线特征：变化缓慢，如：用户、物品基本特征、统计特征
  • 近在线特征：分钟级、小时级需要更新的特征，如：ctr
  • 在线特征：每次请求达到实时获取特征，如：网络状态、 请求时间

特征扩充

• 用户兴趣向量丰富用户维度上兴趣特征

  • LDA中间产物作为用户潜在兴趣向量
  • W2V词向量、用户行为历史统计出用户兴趣向量

• 资源embedding向量丰富物品维度特征

  • 用户行为数据embedding得到W2V、LDA词向量
  • 资源标题embedding得到doc2vector词向量

• 资源封面AutoEncode向量

  • 基于资源封面采用自编码器训练，提取隐层向量作为资源 特征

统计特征细化

• 特征工程时间窗口细化：按不同时间窗口分别计算资源的统计 特征

  • 丰富资源特征
  • 融入时间衰减因素

• 在线特征交叉：交叉特征增加样本特征的区分度

连续特征离散化

• 目标：避免特征为长尾分布、大部分取值集中在小范围，对样本 区分度差

• 等频离散化：等频分桶、独热编码
• 对数转化

采样策略

• 负样本采样策略调整：基本曝光时间、顺序，过滤负样本
• 不平衡样本策略调整：离线A/B测试正负样本比例，择优调整

模型

• 一般使用stacking模型堆叠集成

• 参见ml_models/model_enhancement/ensemble_stacking

基学习器

• GBDT：各树、各叶子节点对应一维特征

  • 适合低维稠密通用特征，对输入特征分布没有要求

• DNN

  • 适合普通稠密特征、embedding特征
  • 能抽取有良好分布数据的深层次特征，提高模型准确性、 泛化能力

元学习器

• LR

  • 适合低维稀疏特征，可对所有特征离散化以引入非线性

• FM

  • 适合低维稀疏特征
  • LR基础上自动组合二阶交叉项

• Linear：训练模型、对训练结果线性加权

冷启动、EE

冷启动

Matching

• 冷启动用户召回

  • 使用imbd算法计算资源得分，根据不同时间周期进行得分 融合、并ab测试，选取最优时间周期组合
  • 按照imdb得分倒排，生成热点召回数据

• 冷启动资源召回

  • 基于资源库，统计各资源点击、播放率，按一定比例召回 第点击、播放率物品

Ranking

• 通常使用强化学习算法

• Thompson Sampling
• UCB算法
• Epsilon-Greedy算法
• 朴素Bandit算法
• LinUCB算法：较UCB算法加入特征信息
• COFIBA算法：Bandit算法结合协同过滤

Exploration and Exploitation Tradeoff

Matching

• 调整不同召回渠道的配比方式保证多样性

总述

在给定的集合、多重集（允许多个元素具有相同的值）中找给定值 （查找键，search key）

• 顺序搜索
• 折半查找：效率高但应用受限
• 将原集合用另一种形式表示以方便查找

评价

没有任何一种查找算法在任何情况下都是最优的

• 有些算法速度快，但是需要较多存储空间
• 有些算法速度快，但是只适合有序数组

查找算法没有稳定性问题，但会发生其他问题

• 如果应用里的数据相对于查找次数频繁变化，查找问题必须结合 添加、删除一起考虑

• 必须仔细选择数据结构、算法，以便在各种操作的需求间达到 平衡

无序线性表查找

顺序查找

算法

• 将给定列表中连续元素和给定元素查找键进行比较
  • 直到遇到匹配元素：成功查找
  • 匹配之前遍历完整个列表：失败查找

1
2
3
4
5
6
7
8
9
10
11
12

SequentialSearch(A[0..n-1], K)
	// 顺序查找，使用**查找键作限位器**
	// 输入：n个元素数组A、查找键K
	// 输出：第一个值为K的元素位置，查找失败返回-1
	A[n] = K
	i = 0
	while A[i] != K do
		i = i + 1
	if i < n
		return i
	else
		return -1

改进

• 将查找键添加找列表末尾，查找一定会成功，循环时将不必每次 检查是否到列表末尾
• 如果给定数组有序：遇到等于（查找成功）、大于（查找失败） 查找键元素，算法即可停止

二叉查找树

算法

• 对数组构建二叉查找树
• 在二叉查找树上进行查找

特点

• 算法效率：参见二叉查找树

• 构建二叉查找树（插入）和查找操作基本相同，效率特性也相同

• 减可变规模 + 输入增强

预排序查找

对线性表预排序，有序表中查找速度快得多

算法

1
2
3
4
5
6
7

PreorderSearch(A[0..n-1])
	// 对数组预排序然后查找
	// 输入：可排序数组A[0..n-1]
	// 输出：元素在数组中的位置
	对B[(数组元素, 索引)]进行预排序
	使用折半查找寻找二元组
	返回二元组中索引

特点

• 算法时间效率：取决于排序算法

  • 查找算法在最差情况下总运行时间$\in \Theta(nlogn)$
  • 如果需要在统一列表上进行多次查找，预排序才值得

• 这种预排序思想可以用于众数、检验惟一性等， 此时算法执行时间都取决于排序算法 （优于蛮力法$\in \Theta(n^2)$）

• 变治法（输入增强）

预排序检验唯一性

1
2
3
4
5
6
7
8
9

PresortElementUniqueness(A[0..n-1])
	// 先对数组排序，求解元素唯一性问题
	// 输入：n个可排序元素构成数[0..n-1]
	// 输出：A中有相等元素，返回true，否则false
	对数组排序
	for i=0 to n-2 do
		if A[i] = A[i+1]
			return false
	return true

预排序求众数

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

PresortMode(A[0..n-1])
	// 对数组预排序来计算其模式（众数）
	// 输入：可排序数组A[0..n-1]
	// 输出：数组模式
	对数组A排序
	i = 0
	modefrequency = 0
	while i <= n-1 do
		runlength = 1
		runvalue = A[i]
		while i + runlength <= n-1 and A[i+runlength] == runvalue
			// 相等数值邻接，只需要求出邻接次数最大即可
			runlength = runlength+1
		if runlength > modefrequency
			modefrequency = runlength
			modevalue = runvalue
		i = i+runlength

	return modevalue

有序顺序表查找

• 有序顺序表的查找关键是利用有序减规模

• 但关键不是有序，而是减规模，即使顺序表不是完全有序， 信息足够减规模即可

折半查找/二分查找

二分查找：利用数组的有序性，通过对查找区间中间元素进行判断， 缩小查找区间至一般大小

• 依赖数据结构，需能够快速找到中间元素，如数组、二叉搜索树

• 一般模板：比较中间元素和目标的大小关系、讨论

  1 2 3 4 5 6 7 8 9

  left, right = ... while condition(search_space is not NULL): mid = (left + right) // 2 if nums[mid] == target: // do something elif nums[mid] > target: // do something elif nums[mid] < target: // do somthing

  • 函数独立时，找到target可在循环内直接返回
  • 函数体嵌入其他部分时，为方便找到target应break， 此时涉及跳出循环时target可能存在的位置
    • 找到target中途break
    • 未找到target直到循环终止条件

基本版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BinarySearchEndReturnV1(nums[0..n-1], target):
	// 非递归折半查找基本版，不直接返回，方便嵌入
	// 输入：升序数组nums[0..n-1]、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = 0, n-1
	while left <= right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid-1
	else:
		assert(mid == right == left-1)

	# 仅最后返回，方便嵌入，下同
	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n-1

  • 左、右均未检查、需检查
  • 即代码中查找区间为闭区间$[left, right]$，此时 搜索区间非空

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 对此版本无影响，left、right总是移动，不会死循环

• 循环条件：left <= right

  • 搜索区间为闭区间，则相应检查条件为left <= right， 否则有元素未被检查
  • 在循环内left、right可能重合

• 更新方式：left=mid+1, right=mid-1

  • 为保证搜索区间始终为闭区间，需剔除mid

• 终止情况：right=left-1、mid=left/right

  • 循环条件、循环内部+1保证：上轮循环left==right
  • 越界终止情况：左、右指针均剔除mid，两侧均可能越界
    • mid=right=n-1, left=n
    • mid=left=0, right=-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target位于[right, left]间
    • left=mid+1=right+1表示小于target元素数量

• 需要和左右邻居（查找结束后）、left、right比较 情况下，容易考虑失误，不适合扩展使用

高级版1

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

BinarySearchV2(nums[0..n-1], target):
	left, right = 0, n
	while left < right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid
	else:
		assert(mid-1 == left == right)

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n

  • 左未检查、需检查，右无需检查
  • 即代码中查找区间为左闭右开区间$[left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 此处必须选择向下取整，否则left=right-1时进入死循环
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左闭右开区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid+1, right=mid

  • 为保证搜索区间始终为左闭右开区间
    • 移动左指针时需剔除mid
    • 移动右指针时无需剔除mid

• 终止情况：right=left、mid=left/left-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left=mid=right-1
  • 越界终止情况：仅左指针剔除mid，仅可能右侧越界
    • left=right=n=mid+1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(mid-1, mid)
    • mid+1=left=right：(mid, left)
    • left表示小于target元素数量

高级版2

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

BainarySearchEndReturnV3(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right:
		mid = (left + right + 1) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			right = mid-1
		else:
			left = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n-1

  • 左无需检查，右未检查、需检查
  • 即代码中查找区间为左开右闭区间$(left, right]$

• 中点选择：mid = (left + right + 1) // 2

  • 向上取整
  • 此处必须选择向上取整，否则left=right-1时进入死循环 （或放宽循环条件，添加尾判断）
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左开右闭区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid+1

  • 为保证搜索区间始终为左闭右开区间
    • 移动右指针时需剔除mid
    • 移动左指针时无需剔除mid

• 终止情况：left=right、mid=left/left+1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left+1=mid=right
  • 越界终止情况：仅右指针剔除mid，仅可能左侧越界
    • left=right=-1=mid-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(right, right+1)
    • mid+1=left=right：(left, right)
    • left+1表示小于target元素数量

高级版3

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

BinarySearchEndReturnV2(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right-1:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid
		else:
			right = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n

  • 左、右均无需检查
  • 即代码中查找区间为开区间$(left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整、向上取整均可

• 循环条件：left < right-1

  • 搜索区间为左开右闭区间，则检查条件为left < right-1， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid

  • 循环终止条件足够宽泛，不会死循环

• 终止情况：left=right-1、mid=right/right-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
  • 越界终止情况：左右初始条件均越界，则左、右均可能越界
    • mid=left=n-1、right=n
    • left=-1、mid=right=0

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target始终在搜索区间(left, right)内
    • 最终位于(left, right)

高级版1-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

BinarySearchKeep1(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n-1

	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			right = mid
		else:
			left = mid

	// post-procesing
	if nums[left] == target:
		return left
	if nums[right] == target:
		return right

	return -1

• 初始条件：left = 0, right = n-1
• 终止情况：left = right - 1
• 指针移动：left = mid, right= mid

• 关键特点

  • n>1时left、mid、right循环内不会重合
  • mid可以left、right任意比较，无需顾忌重合
  • 需要和左右邻居、left、right比较时适合使用
  • 扩展使用需要进行真后处理，对left、right进行判断

• 终止情况：left = right - 1

  • 循环过程中会保证查找空间至少有3个元素，剩下两个 元素时，循环终止
  • 循环终止后，left、right不会越界，可以直接检查

• target位置

  • 若存在target，可能位于mid、left、right

    • mid：因为找到nums[mid]==target跳出
    • left：left=0，循环中未检查
    • right：right=n-1，循环中未检查

  • 不存在target，则target位于(left, right)之间

  • 适合访问目标在数组中索引、极其左右邻居

• 仅仅二分查找的话，后处理其实不能算是真正的后处理

  • nums[mid]都会被检查，普通left、right肯定不会 是target所在的位置

  • 真正处理的情况：target在端点

    • left=0, right=1终止循环，left=0未检查
    • left=n-2, right=n-1终止循环，right=n-1未检查

  • 即这个处理是可以放在循环之前进行处理

高级版2-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySearchKeep0(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n
	while left < right:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid + 1
		else:
			right = mid

	// post-processing
	if left != len(nums) and nums[left] == target:
		return left

	return -1

• 初始条件：left = 0, right = n，保证n-1可以被正确处理
• 终止情况：left = right
• 指针移动：left = mid + 1, right = mid
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 终止情况还有left = right + 1

• 关键特点

  • left、right循环内不会重合
  • 由于floor的特性，mid可以right任意比较，无需 顾忌和right重合
  • 需要和右邻居、right比较时适合使用

• 终止情况：left = right

  • 循环过程中会保证查找空间至少有2个元素，否则循环 终止
  • 循环终止条件导致退出循环时，可能left=right=n越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left-1, left)
  • 适合访问目标在数组中索引、及其直接右邻居

• 仅二分查找，甚至无需后处理

• 判断nums长度在某些语言中也可以省略

高级版3-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySearchNoKeep(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = -1, n-1
	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid
		else:
			right = mid - 1

	// post-processing
	if right >= 0 and nums[right] == target:
		return right

	return -1

• 初始条件：left = -1, right = n-1
• 终止情况：left = right、left = right + 1
• 指针移动：left = mid, right = mid - 1
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 同高级版本2

• 终止条件：left = right、left = right - 1

  • 循环过程中保证查找空间至少有3个元素，否则循环 终止

  • 由于floor特性，必须在left < right - 1时即终止 循环，否则可能死循环

  • 循环终止后，left=right=-1可能越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left, left+1)
  • 适合访问目标在数组中索引、及其直接左邻居

• 此版本仅想实现二分查找必须后处理

  • 终止条件的原因，最后一次right=left + 1时未被检查 即退出循环

  • 可能在任何位置发生，不是端点问题

特点

• 前两个版本比较常用，最后两个版本逻辑类似

• 折半查找时间效率

  • 最坏情况下：$\in \Theta(log n)$
  • 平均情况下仅比最差稍好

• 就依赖键值比较的查找算法而言，折半查找已经是最优算法 ，但是插值算法、散列法等具有更优平均效率

• 减常因子因子法

插值查找

Interpolation Search：查找有序数组，在折半查找的基础上考虑 查找键的值

算法

• 假设数组值是线性递增，即数字值~索引为一条直线，则根据 直线方程，可以估计查找键K在A[l..r]所在的位置

  $$x = l + \left \lfloor \frac {(K-A[l])(r-l)} {A[r] - A[l]} \right \rfloor$$

• 若k == A[x]，则算法停止，否则类似折半查找得到规模更小的 问题

特点

• 即使数组值不是线性递增，也不会影响算法正确性，只是每次 估计查找键位置不够准确，影响算法效率

• 统计考虑

  • 折半插值类似于非参方法，只考虑秩（索引）方向
  • 插值查找类似参数方法，构建了秩（索引）和数组值模型， 但是线性关系基于假设
  • 如果模型错误可能会比折半查找效率更差，即在数据分布 分布偏差较大的情况下非参方法好于参数方法

• 所以是否可以考虑取样方法，先取5个点构建模型，然后估计

• 算法效率

  • 对随机列表，算法比较次数小于$log_2log_n+1$
  • 最差情况，比较次数为线性，没有折半查找稳定
  • Robert Sedgewick的Algorithms中研究表明，对较小文件 折半查找更好，大文件、比较开销大插值查找更好

• 减可变规模

子串匹配

蛮力字符串匹配

算法

• 将pattern对齐文本前m个字符，从左向右匹配相应字符
  • m个字符全部匹配，匹配成功，算法停止
  • 遇到不匹配字符则
• 模式右移1位，然后从模式首个字符开始重复以上匹配
• 在n-m位置无法匹配成功，则无足够匹配字符，算法停止

1
2
3
4
5
6
7
8
9
10
11
12

BruteForceStringMatch(T[0..n-1], P[0..m-1])
	// 蛮力字符串匹配
	// 输入：文本T：n个字符的字符数组
	//       模式：m个字符的字符数组
	// 输出：查找成功返回文本第一个匹配子串中第一个字符位置
	for i = 0 to m-m do
		j = 0
		while j < m and P[j] = T[i+j] do
			j = j + 1
			if j = m
				return i
	return -1

特点

• 最坏情况下，算法比较次数属于$O(nm)$
  • 即在移动模式之前，算法需要做足m次比较
  • 但是一般在自然语言中，算法平均效率比最差好得多
  • 在随机文本中，有线性效率

Horspool算法

算法从右往左匹配，在任意位置匹配不成功时只考虑 同模式最后字符匹配的文本字符c，确定安全移动距离，在 不会错过匹配子串的情况下移动最长距离

• 如果c在模式中出现，则模式移动到其最后c至同文本中c 匹配
• 否则移动模式长度m
• 特别的，如果c只在模式最后字符出现，则也应该移动m

算法

• 对给定长度m的模式及文本中用到的字母表，构造移动表t
• 将模式同文本开始对齐
• 重复以下过程直至发了了匹配子串或模式达到了文本字符外
  • 从模式最后字符开始，比较模式、文本相应字符
  • 若m个字符匹配，停止
  • 遇到不匹配字符c，若为当前文本中和模式最后匹配字符 对齐的字符，将模式移动t(c)个字符

1
2
3
4
5
6
7
8
9
10
11

ShiftTable(P[0..m-1])
	// 用Horspool算法、Boyer-Moore算法填充移动表
	// 输入：模式P[0..m-1]、可能出现字符表
	// 输出：以字符表为为索引的数组Table[0..size-1]
	for i=0 to size-1 do
		Table[i] = m
		// 初始化所有字符对应移动距离为m
	for j=0 to m-2 do
		Table[P[j]] = m - 1 - j
		// 对模式中存在的字符重新计算移动距离
	return Table

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

HorspoolMatching(P[0..m-1], T[0..n-1])
	// 实现Horspool字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	Table = ShiftTable(P[0..m-1])
	i = m - 1
	while i <= n-1 do
		k = 0
		while k <= m-1 and P[m-1-k]=T[i-k] do
			k = k+1
		if k == m
			return i-m+1
		else
			i = i+Table[T[i]]
	return -1

特点

• 算法效率

  • 最差情况下模式为相同字符，效率$\in O(nm)$
  • 对随机文本效率$\in O(n)$

• 输入增强

Boyer-Moore算法

• 坏符号移动：模式、文本中相应不匹配字符确定的移动 （不是Horspool中简单根据最后字符确定移动）
• 好后缀移动：模式、文本匹配的后缀确定的移动

算法

• 对给定长度m的模式及文本用到的字母表，构造坏符号移动表t
• 对给定长度m的模式构造后缀移动表
• 将模式与文本开始处对齐
• 重复以下直到找到匹配子串或模式达到文本字符以外
  • 从模式最后字符开始比较模式、文本相应字符
  • 所有m个字符匹配，则停止
  • 若c是不匹配字符，移动坏符号表、后缀移动表决定的 距离较大者

1
2
3
4
5

BadSymbolShift(P[0..m-1])
	// 创建坏符号移动表
	// 输入：模式P[0..m-1]
	// 输出：坏符号移动表

特点

• 算法效率

  • 算法效率最差也是线性的

• 输入增强

KMP算法

算法从左往右匹配，失败时不回溯指针，利用已经得到的 部分匹配结果尽可能将模式滑动一段距离，从模式中间next 字符开始比较

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShift(P[0..m-1])
	// 计算KMP算法next值
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next值数组
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next[0] = -1
		// 即如果模式首字符都不匹配，比较文本下个字符
	while j < m
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			// 当前字符匹配成功，决定下个字符next值
			next[j] = i
		else
			i = next[i]
			// 若当前字符没有匹配成功，不会立即处理下个字符
			// next值，而是反复迭代、查询已匹配部分next值，
			// 以获得最大匹配前缀
	return next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShiftVal(P[0..m-1])
	// 计算KMP算法next值修正版（考虑next值与当前相等）
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next_val值数组u
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next_val[0] = -1
	while j < m do
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			if T[j] != T[i]
				next_val[j] = i
			else
				next_val[j] = next_val[i]
				// 考虑了next值相同时，可以再滑动一次
				// 这里会导致next_val值跳跃
		else
			i = next_val[i]
	return next_val

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

KMPMatching(P[0..m-1], T[0..n-1])
	// 实现KMP字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	i = 0
	j = 0
	while i < m and j < n do
		if i == -1 or P[i] == T[j]
			i += 1
			j += 1
		else
			i = next[i]
	if i >= m
		return j - m + 1
	else
		return -1

特点

• 算法效率

  • 算法时间效率$\in O(m+n)$

• 文本指针不需要回溯，整个匹配过程只需要对文本扫描一次， 对流程处理十分有效，可以边读边匹配

• 输入增强

集合

势

• 等势：若集合 $X, Y$ 之间存在双射 $\phi: X \rightarrow Y$，则称 $X, Y$ 等势
• 可数/可列集合：与自然数集合、其子集等势的集合称为可数集合，否则称为不可数集合

• 等势构成集合之间的等价关系
  • 集合 $X$ 的等势类记为 $|X|$
  • 若存在单射 $\phi: X \rightarrow Y$，则记为 $|X| \leq |Y|$
• 一些基本结论
  • 自然数集 $N = {0, 1, 2, 3, \cdots}$ 和闭区间 $[0,1]$ 不等势

• https://zhuanlan.zhihu.com/p/34097692

序

• 偏序集：若集合 $A$ 上有二元关系 $\leq$ 满足以下性质，则称集合 $A$ 为偏序集，关系 $\leq$ 称为偏序关系

  • 反身性：$\forall x \in A, x \leq x$
  • 传递性：$(x \leq y) \wedge (y \leq z) \Rightarrow x \leq z$
  • 反称性：$(x \leq y) \wedge (y \leq x) \Rightarrow x = y$

• 全序集：若 $\leq$ 是集合上的偏序关系，若对每个$x, y \in A$，必有 $x\leq y$ 或 $y \leq x$，则称集合 $A$ 为全序集，关系 $\leq$ 为全序关系

• 良序集：若集合 $A$ 每个自己都有极小元，则称为良序集

• 特点
  • 偏序指集合中只有部分成员之间可比较
  • 全序指集合全体成员之间均可比较
  • 良序集则是不存在无穷降链的全序集（可有无穷升链）

序数

• 序数：若集合 $A$ 中每个元素都是 $A$ 的子集，则称 $A$ 是传递的。而 $A$ 对于关系 $\in$ 构成良序集，则称 $A$ 为序数

• 满足如下形式的集合即为序数

  $$\{\phi, \{\phi\}, \{\phi, \{\phi\}\}, \{\phi, \{\phi\}, \{\phi, \{\phi\}\}\} \}, \cdots$$

• 序数的性质（引理）

  • 若 $\alpha$ 为序数，$\beta \in \alpha$，则 $\beta$ 也是序数
  • 对任意序数 $\alpha, \beta$，若 $\alpha \subset \beta$，则 $\alpha \in \beta$
  • 对任意序数 $\alpha, \beta$，必有 $\alpha \subseteq \beta$ 或 $\beta \subseteq \alpha$

• 由以上，序数性质的解释

  • 序数是唯一的，都满足上述形式
  • 序数都是由自己之前的所有序数构造而来
  • 对任意序数 $\alpha$，有 $\alpha = {\beta: \beta < \alpha }$ （$ < $ 表示偏序关系）

• 将 $0, 1, 2, \cdots$ 依次对应上述序数，即给出自然数和序数

  $$0 := \phi, 1 := \{phi\}, 2 := \{\phi, \{phi\}\}, \cdots$$

• https://zh.wikipedia.org/wiki/%E5%BA%8F%E6%95%B0
• 自然数可用于描述集合大小（势，基数）、序列中元素的位置（序，序数）

良序定理

• Zermelo 良序定理：任何集合 $P$ 都能被赋予良序

• Zermelo 良序定理和 ZFC 选择公理等价，可以由选择公理证明
  • 由选择公理，可以一直从集合中选择元素，建立偏序关系
  • 而集合有限，则集合和序数之间可以建立双射

基

基数

• 基数：序数 $k$ 为基数，若对任意序数 $\lambda < k$，都有 $|\lambda| < |k|$
• Counter 定理：设 $A$ 为集合，$P(A)$ 为 $A$ 的幂集，则有 $|A| \leq |P(A)|$

• 基数是集合势的标尺

• 数的集合的基数

  • 自然数集合基数 $\aleph_0$：最小的无限基数
  • 实数集集合基数称为 continuum 连续统

• 连续统假设：不存在一个集合，基数在自然数集和连续统之间

  • 哥德尔证明：连续统假设与公理化集合论体系 Zermelo-Fraenkel set theory with the axiom of choice 中不矛，即不能再 ZFC 中被证伪
  • 科恩证明：连续统假设和 ZFC 彼此独立，不能在 ZFC 公理体系内证明、证伪

• https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0_(%E6%95%B0%E5%AD%A6)

距离

• 距离可认为是两个对象 $x,y$ 之间的 相似程度
  • 距离和相似度是互补的
  • 可以根据处理问题的情况，自定义距离

Bregman Divergence

• $Phi(x)$：凸函数

• 布雷格曼散度：穷尽所有关于“正常距离”的定义

  • 给定 $R^n * R^n \rightarrow R$ 上的正常距离 $D(x,y)$，一定可以表示成布雷格曼散度形式
  • 直观上：$x$处函数、函数过$y$点切线（线性近似）之差
    • 可以视为是损失、失真函数：$x$由$y$失真、近似、添加噪声得到

• 特点

  • 非对称：$D(x, y) = D(y, x)$
  • 不满足三角不等式：$D(x, z) \leq D(x, y) + D(y, z)$
  • 对凸集作 Bregman Projection 唯一
    • 即寻找凸集中与给定点Bregman散度最小点
    • 一般的投影指欧式距离最小

• 正常距离：对满足任意概率分布的点，点平均值点（期望点）应该是空间中距离所有点平均距离最小的点
• 布雷格曼散度对一般概率分布均成立，而其本身限定由凸函数生成

  • 和 Jensen 不等式有关？凸函数隐含部分对期望的度量

• http://www.jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf

单点距离

Minkowski Distance

闵科夫斯基距离：向量空间 $\mathcal{L_p}$ 范数

• 表示一组距离族

  • $p=1$：Manhattan Distance，曼哈顿距离
  • $p=2$：Euclidean Distance，欧式距离
  • $p \rightarrow \infty$：Chebychev Distance，切比雪夫距离

• 闵氏距离缺陷

  • 将各个分量量纲视作相同
  • 未考虑各个分量的分布

Mahalanobis Distance

马氏距离：表示数据的协方差距离

• $\Sigma$：总体协方差矩阵

• 优点
  • 马氏距离和原始数据量纲无关
  • 考虑变量相关性
• 缺点
  • 需要知道总体协方差矩阵，使用样本估计效果不好

LW Distance

兰氏距离：Lance and Williams Distance，堪培拉距离

• 特点
  • 对接近0的值非常敏感
  • 对量纲不敏感
  • 未考虑变量直接相关性，认为变量之间相互独立

Hamming Distance

汉明距离：差别

• $v_i \in {0, 1}$：虚拟变量
• $p$：虚拟变量数量

• 可以衡量定性变量之间的距离

Embedding

• 找到所有点、所有维度坐标值中最大值 $C$
• 对每个点 $P=(x_1, x_2, \cdots, x_d)$
  • 将每维 $x_i$ 转换为长度为 $C$ 的 0、1 序列
  • 其中前 $x_i$ 个值为 1，之后为 0
• 将 $d$ 个长度为 $C$ 的序列连接，形成长度为 $d * C$ 的序列

• 以上汉明距离空间嵌入对曼哈顿距离是保距的

Jaccard 系数

Jaccard 系数：度量两个集合的相似度，值越大相似度越高

• $S_1, S_2$：待度量相似度的两个集合

Consine Similarity

余弦相似度

• $x_1, x_2$：向量

欧式距离

点到平面

• $T={(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)}$：样本点集
• $wx + b = 0$：超平面

Functional Margin 函数间隔

• 函数间隔可以表示分类的正确性、确信度

  • 正值表示正确
  • 间隔越大确信度越高

• 点集与超平面的函数间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

• 超平面参数 $w, b$ 成比例改变时，平面未变化，但是函数间隔成比例变化

Geometric Margin 几何间隔

• 几何间隔一般是样本点到超平面的 signed distance

  • 点正确分类时，几何间隔就是点到直线的距离

• 几何间隔相当于使用 $|w|$ 对函数间隔作规范化

  • $|w|=1$ 时，两者相等
  • 几何间隔对确定超平面、样本点是确定的，不会因为超平面表示形式改变而改变

• 点集与超平面的几何间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

Levenshtein/Edit Distance

（字符串）编辑距离：两个字符串转换需要进行插入、删除、替换操作的次数

组间距离

Single Linkage

Average Linkage

Complete Linkage

Spark Streaming

Spark Streaming：提供对实时数据流高吞吐、高容错、可扩展的 流式处理系统

• 可以对多种数据源（Kafka、Flume、Twitter、ZeroMQ），进行 包括map、reduce、join等复杂操作

• 采用Micro Batch数据处理方式，实现更细粒度资源分配，实现 动态负载均衡

  • 离散化数据流为为小的RDDs得到DStream交由Spark引擎处理
  • 数据存储在内存实现数据流处理、批处理、交互式一体化
  • 故障节点任务将均匀分散至集群中，实现更快的故障恢复

streaming.StreamingContext

1
2
3
4
5
6
7
8
9
10

import org.apache.spark.streaming.StreamingContext
class StreamingContext(?conf: SparkConf, ?slices: Int){

	// 开始接受、处理流式数据
	def start()
	// 结束流式处理过程
	def stop(?stop_spark_context=True)
	// 等待计算完成
	def awaitTermination()
}

1
2
3
4
5
6

import org.apache.spark.{SparkContext, SparkConf}
import org.apache.spark.streaming.Seconds
import org.apache.spark.streaming.StreamingContext._

val conf = new SparkConf().setAppName("app name").setMaster(master)
val ssc = new StreamingContext(conf, Seconds(1))

Discreted Stream

DStream：代表持续性的数据流，是Spark Streaming的基础抽象

• 可从外部输入源、已有DStream转换得到

  • 可在流应用中并行创建多个输入DStream接收多个数据流

• 在内部实现

  • DStream由时间上连续的RDD表示，每个RDD包含特定时间 间隔内的数据流
  • 对DStream中各种操作也是映射到内部RDD上分别进行 （部分如transform等则以RDD为基本单元）
    • 转换操作仍然得到DStream
    • 最终结果也是以批量方式生成的batch

  • 对DStream操作参见tools/spark/spark_rdd

• （大部分）输入流DStream和一个Receiver对象相关联

  • Recevier对象作为长期任务运行，会占用独立计算核， 若分配核数量不够，系统将只能接收数据而不能处理
  • reliable receiver：可靠的receiver正确应答可靠源， 数据收到、且被正确复制至Spark
  • unreliable receiver：不可靠recevier不支持应答

Basic Sources

基本源：在StreamingContext中直接可用

• 套接字连接
• Akka中Actor
• RDD队列数据流

1
2
3
4
5
6
7
8

// 套接字连接TCP源获取数据
def ssc.socketTextStream(?host: String, ?port: Int): DStream

// 自定义actor流
def ssc.actorStream(actorProps: ?, actorName: String): DStream

// RDD队列流
def ssc.queueStream(queueOfRDDs: Seq[RDD])

文件系统

1
2
3
4

// 文件流获取数据
def ssc.fileStream[keyClass, valueClass, inputFormatClass]
	(dataDirectory: String): DStream
def ssc.textFileStream(dataDirectory)

文件系统：StreamingContext将监控目标目录，处理目录下任何 文件（不包括嵌套目录）

• 文件须具有相同数据格式
• 文件需要直接位于目标目录下
• 已处理文件追加数据不被处理

• 文件流无需运行receiver

Advanced Sources

高级源：需要额外的依赖

• Flume
• Kinesis
• Twitter

Kafka

1
2
3

// 创建多个Kafka输入流
val kafkaStreams = (1 to numStreams).map(_ => kafkaUtils.createStream())
val unifiedStream = streamingContext.union(kafkaStreams)

性能调优

• 减少批数据处理时间

  • 创建多个receiver接收输入流，提高数据接受并行水平
  • 提高数据处理并行水平
  • 减少输入数据序列化、RDD数据序列化成本
  • 减少任务启动开支

• 设置正确的批容量，保证系统能正常、稳定处理数据

• 内存调优，调整内存使用、应用的垃圾回收行为

Checkpoint

1
2
3
4

// 设置checkpoint存储信息目录
def ssc.checkpoint(?checkpointDirectory: String)
// 从checkpoint中恢复（若目录存在）、或创建新streaming上下文
def StreamingContext.getOrCreate(?checkPointDirectory: String, ?functionToCreateContext: () => StreamingContext)

• 为保证流应用程序全天运行，需要checkpoint足够信息到容错 存储系统，使得系统能从程序逻辑无关错误中恢复

  • metadata checkpointing：流计算的定义信息，用于恢复 worker节点故障
  • configuration：streaming程序配置
  • DStream operation：streaming程序操作集合
  • imcomplete batches：操作队列中未完成批
  • data checkpointing：中间生成的RDD，在有状态的转换 操作中必须，避免RDD依赖链无限增长

• 需要开启checkpoint场合

  • 使用有状态转换操作：updateStateByKey、 reduceByKeyAndWindow等
  • 从程序的driver故障中恢复

1
2
3
4
5
6
7

def functionToCreateContext(): StreamingContext = {
	val conf = new SparkConf()
	val ssc = new StreamingContext(conf)
	// other streaming setting
	ssc.checkpoint("checkpointDirectory")
	ssc
}

禁忌搜索

进化算法

进化算法：

• 后设启发式算法：适合多种最优化问题，但不保证找到全局最优

Genetic Algorithm

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

• 本质是高效、并行、全局搜索方法
• 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

• 将问题域中可能解看作是染色体，将其编码为符号串的形式
• 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
• 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

实体

• population：群体，GA的遗传搜索空间
• individual：个体，搜索空间中可能解
• chromosome：染色体，个体特征代表
  • 由若干段基因组成
  • GA中基本操作对象
• gene：基因
  • 染色体片段
• fitness：适应度，个体对环境的适应程度

基本操作

• selection：选择，根据个体适应度在群体中按照一定概率 选择个体作为父本

  • 适应度大个体被选择概率高
  • 体现了适者生存、优胜劣汰的进化规则

• crossover：交叉，将父本个体按照一定概率随机交换基因 形成新个体

• mutate：变异，按照一定概率随机改变某个体基因值

串编码方式

• 把问题的各种参数用二进串进行编码构成子串
• 把子串拼接成染色体

  • 串长度、编码方式对算法收敛影响极大

二进制编码方式

二进制法：使用二进制染色体表示所有特征

• 优点

  • 编码、解码操作简单
  • 交叉、变异等遗传操作便于实现
  • 符合最小字符集编码原则
  • 利于模式定理对算法理论分析

• 缺点

  • 连续函数离散化存在误差，染色体长度短时达不到精度 要求，较长时解码难度大、搜索空间增大
  • 对连续函数优化问题，随机性使得其局部搜索能力较差， 接近最优值时不稳定

浮点编码

浮点法：个体的每个基因值用某一范围内的一个浮点数表示

• 必须保证基因之在给定区间限制范围内

  • 交叉、变异等遗传算子结果也必须在限制范围内

• 优点

  • 适用于在遗传算法中表示范围较大的数
  • 精度较高
  • 便于较大空间的遗传搜索
  • 改善了遗传算法的计算复杂性，提高了运算效率
  • 便于遗传算法与经典优化方法的混合使用
  • 便于设计针对问题的专门知识的知识型遗传算子
  • 便于处理复杂的决策变量约束条件

符号编码法

符号法：个体染色体编码串基因值取自无意义字符集

• 优点
  • 符合有意义积木块编码原则
  • 方便利用所求解问题的专门知识
  • 访问GA和相关近似算法的混合使用

Fitness Function

适应度/对象函数

• 一般可以把问题模型函数作为对象函数

• 过程

  • 解码个体，得到个体表现型
  • 由个体表现型计算个体目标函数值
  • 根据最优化问题类型，由目标函数值按一定转换规则求出 个体适应度

操作

选择函数

• Roulette Wheel Selection：轮盘赌选择，个体进入下一代 概率为其适应度与整个种群适应度之比

  • 放回式随机抽样
  • 选择误差较大

• Stochastic Tournament：随机竞争选择，每次按轮盘赌选择 一对个体，选择适应度较高者，重复直到选满

• 最佳保留选择：按轮盘赌选择方法执行遗传算法选择操作，然后 t将当前群体中适应度最高的个体结构完整地复制到下一代群体中

• Excepted Value Selection：无回放随机选择，根据每个个体 在下一代群体中的生存期望来进行随机选择运算

  • 计算群体中每个个体在下一代群体中的生存期望数目N
  • 若体被选中参与交叉运算，则它在下一代中的生存期望数目 减去0.5，否则在下一代中的生存期望数目减去1.0
  • 随着选择过程的进行，当个体的生存期望数目小于0时，则 该个体就不再有机会被选中。

• 确定式选择：按照一种确定的方式来进行选择操作

  • 计算群体中各个体在下一代群体中的期望生存数目N
  • 用N的整数部分确定个体在下一代群体中的生存数目
  • 用N的小数部分对个体进行降序排列，顺序取前M个个体加入 到下一代群体
  • 完全确定出下一代群体中Ｍ个个体

• 无回放余数随机选择

  • 可确保适应度比平均适应度大的一些个体能够被遗传到 下一代群体中
  • 选择误差比较小

• 均匀排序：对群体中的所有个体按期适应度大小进行排序，基于 这个排序来分配各个个体被选中的概率

• 最佳保存策略：当前群体中适应度最高的个体不参与交叉运算 和变异运算，而是用它来代替掉本代群体中经过交叉、变异等 操作后所产生的适应度最低的个体

• 随机联赛选择：每次选取几个个体中适应度最高个体遗传到 下一代群体中。

• 排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高 群体的多样性

Cross Over

• One-point Crossover：单点交叉，在个体编码串中只随机 设置一个交叉点，然后再该点相互交换两个配对个体的部分 染色体

• Two-point Crossover：两点交叉，在个体编码串中随机设置 两个交叉点，然后再进行部分基因交换

• Multi-point Crossover：多点交叉

• Uniform Crossover：均匀交叉/一致交叉，两个配对个体的 每个基因座上的基因都以相同的交叉概率进行交换，从而形成 两个新个体

• Arithmetic Crossover：算术交叉，由两个个体的线性组合 而产生出两个新的个体

  • 操作对象一般是由浮点数编码表示的个体

Mutation

• Simple Mutation：基本位变异，对个体编码串中以变异概率 、随机指定的某一位或某几位仅因座上的值做变异运算

• Uniform Mutation：均匀变异，用符合某一范围内均匀分布 的随机数，以较小的概率来替换个体编码串中各个基因座上原有 基因值

  • 适用于在算法的初级运行阶段

• Boundary Mutation：边界变异，随机的取基因座上的两个 对应边界基因值之一去替代原有基因值

  • 适用于最优点位于或接近于可行解的边界时的一类问题

• 非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果 作为变异后的新基因值

  • 对每个基因值都以相同的概率进行变异运算之后，相当于 整个解向量在解空间中作了一次轻微的变动

• 高斯近似变异：进行变异操作时用符号均值为P、方差$P^2$的 正态分布的一个随机数来替换原有的基因值

GA超参设置

• 群体大小$n$：过小难以求出最优解，过大难收敛，一般取 $n = 30 ~ 160$

• 交叉概率$P_c$：太小难以前向搜索，太大容易破坏高适应 值结构，一般取$P_c = 0.25 ~ 0.75$

• 变异概率$P_m$：太小难以产生新结构，太大则变为单纯 随机搜索，一般取$P_m = 0.01 ~ 0.2$

算法

1. 随机初始化种群
2. 估初始种群：为种群每个个体计算适应值、排序
3. 若没有达到预定演化数，则继续，否则结束算法
4. 选择父体
   • 杂交：得到新个体
   • 变异：对新个体变异
5. 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
6. 重复3

Differential Evolution

差分进化算法：

Particle Swarm Optimization

粒子群/微粒群算法：

Simulated Annealing Algorithm

模拟退火算法

• 来源于固体退火原理

  • 将固体加热至充分高，固体内部粒子随之变为无序状，内能 增加
  • 再让固体徐徐冷却，内部例子随之有序
  • 到达常温状态时，内能减为最小

• 用固体退火模拟组合优化问题

  • 目标函数值f视为内能E，控制参数t视为温度T
  • 由初始解i、控制参数初值t开始，对当前解重复 产生新解->计算目标函数增量->接受或舍弃的迭代，并 逐步衰减t值
  • 算法终止时，当前解即为所得近似最优解

• 退火过程由Cooling Schedule控制，包括控制参数初值t、衰减 因子$\Delta t$、迭代次数L、停止条件S

算法

• 初始化：初始温度$t_0$（充分大）、初始解$i_0$、迭代次数L
• 产生新解$i_1$，计算目标函数增量$\Delta f=f(i_1)-f(i)$
• 若$\Delta f<0$则接受$i_1$作为新解，否则以概率 $\exp^{\Delta f/f(i_0)}$接受$i_1$作为新解
• 若满足终止条件则算法结束
  • 若干次新解都不被接受：当前解“能量”低
  • 迭代次数达到上限
• 否则减小温度为$t_1$继续迭代

说明

• 解生成器：应该可以通过简单变换即可产生新解，便于减少每次 迭代计算新解耗时

  • 比如对新解全部、部分元素进行置换、互换等
  • 需要注意的是，这决定了新解的领域结构，对冷却的进度表 选取有影响

• 新解是否被接受采用的是Metropolis准则

模拟退火算法性质

• 与初值无关
• 具有渐进收敛性
• 具有并行性
• 在理论上被证明是以概率1收敛于全局最优解的算法
• 能够跳出局部最优解

应用

• VLSI：目前退火模拟算法的应用实例，几乎可以完成所有VLSI 设计工作
• 神经网络：模拟退火算法能够跳出局部最优解
• 图像处理：用于进行图像恢复工作
• 其他问题：还可以用于其他各种组合优化问题

数值随机化算法

数值化随机算法：常用于数值问题求解，往往得到的是近似解

• 近似解的精度随计算时间、采样数量增加不断提高
• 很多情况下计算问题的精确解不可能、无必要，数值化随机算法 可以得到较好的解

随机投点法

随机投点法：在给定范围内生成均匀分布随机数模拟随机投点

• 计算$\pi$值：在正方形、内切圆中随机撒点，计算圆内、 正方形内点数量之比

• 计算黎曼积分：在包括积分区域单位矩形内随机投点，计算 积分区域、矩形区域点数量之比

平均值法

平均值法：结合随机数分布、目标问题构造统计量，估计目标问题

计算黎曼积分

• 假设独立同分布随机变量${\eta_i}$在$[a, b]$中服从分布 $f(x)$、待积函数为$g(x)$

• 记$g^{*}(x) = \frac {g(x)} {f(x)}$，则有

  $$\begin{align*} E(g^{*}(\eta)) & = \int_a^b g^{*}f(x) dx \\ & = \int_a^b g(x) dx = I \end{align*}$$

• 由强大数定理

  $$P_r(\lim_{x \rightarrow \infty} \frac 1 n \sum_{i=1}^n g^{*}(\eta_i) = I) = 1$$

  选择$\bar I = \frac 1 n \sum_{i=1}^n g^{*}(\eta_i)$， 则$\bar I$依概率收敛为$I$

• 选择抽样方法简单的概率密度函数$f(x)$满足

  $$\left \{ \begin{array}{l} f(x) \neq 0, & g(x) \neq 0, a \leq x \leq b \\ \int_a^b f(x) dx = 1 \end{array} \right.$$

  可以取$f(x)$为均匀分布

  $$f(x) = \left \{ \begin{array}{l} \frac 1 {b-a}, & a \leq x \leq b \\ 0, & x < a, x > b \end{array} \right.$$

• 则积分

  $$I = \int_a^b g(x)dx = (b-a) \int_a^b g(x) \frac 1 {b-a}dx$$

  取均值

  $$\bar I = \frac {b-a} n \sum_{i=1}^n g(x_i)$$

  可作为求分I的近似值

解非线性方程组

• 线性化方法、求函数极小值方法有时会遇到麻烦，甚至使方法 失效而不能获得近似解
• 随机化方法相较而言要耗费较多时间，但设计简单、易于实现
• 对于精度要求较高的问题，随机化方法可以提供一个较好的初值

步骤

• 构造目标函数

  $$\Phi(x) = \sum f_i^2(x)$$

  则目标函数的极小值点即为所求非线性方程组的一组解

• 随机选择点$x_0$作为出发点，不断随机生成搜索方向， 迭代为使得目标函数值下降的搜索点

  • 一般以目标函数变化幅度、迭代轮数作为终止条件
  • 搜索方向为随机生成，迭代步长比例每轮缩小指定幅度

• 真正的随机次梯度下降

Monte Carol Method

蒙特卡洛算法：一定能给出问题解，但未必正确

• 要求在有限时间、采样内必须给出解，解未必正确
• 求得正确解的概率依赖于算法所用时间，算法所用时间越多， 得到正确解概率越高
• 无法有效判断得到的解是否肯定正确

Las Vegas Method

拉斯维加斯算法：找到的解一定是正确解，但是可能找不到解

• 找到正确解的概率随着计算所用时间增加而提高
• 用同一拉斯维加斯算法反复对实例求解多次，可使得求解失效 概率任意小

Sherwood Method

舍伍德算法：能求得问题的一个解，所求得得解总是正确的

• 确定性算法在最好情况、平均情况下计算复杂度有较大差别， 在确定性算法中引入随机性将其改造成舍伍德算法，消除、减少 问题的好坏实例间差别

• 精髓不是改进算法在最坏情形下的行为，而是设法消除最坏情形 与特定问题实例的关联性

思想

• 问题输入规模为n时，算法A所需的平均时间为

  $$\bar t_A(n) = \sum_{x \in X_n} t_A(x) / |X_n|$$

  • $X_n$：算法A输入规模为n的实例全体
  • $t_A(x)$：输入实例为x时所需的计算时间

  显然存在$x \in X_n, t_A(x) >> \bar t_A(x)$

• 希望获得随机化算法B，使得对问题的输入规模为n的每个实例 $x \in X_n$均有$t_B(x) = \bar t_A(x) + s(n)$

  • 对具体实例，存在$x \in X_n$，算法B需要时间超过 $\bar t_A(x) + s(n)$，但这是由于算法所做的概率引起， 与具体实例无关

  • 算法B关于规模为n的随机实例平均时间为

    $\begin{align*} \bar t_B(n) & = \sum_{x \in X_n} t_B(x) / (X_n) \\ & = \bar t_A(n) + s(n) \end{align*}$K

    当$s(n)$与$\bar t_A(n)$相比可以忽略时，舍伍德算法 可以获得较好平均性能

todo

Reproducing Kernel Hilbert Space

• Hilbert space：假设 $K(x,z)$ 是定义在 $\mathcal{X X}$ 上的对称函数，并且对任意 $x_1, x_2, \cdots, x_m \in \mathcal{X}$，$K(x,z)$ 关于其的 Gram* 矩阵半正定，则可以根据函数 $K(x,z)$ 构成一个希尔伯特空间

构造步骤

定义映射构成向量空间

• 定义映射

  $$\phi: x \rightarrow K(·, x)$$

• 根据此映射，对任意 $x_i \in \mathcal{X}, \alpha_i \in R, i = 1,2,\cdots,m$ 定义线性组合

  $$f(·) = \sum_{i=1}^m \alpha_i K(·, x_i)$$

• 由以上线性组合为元素的集合 $S$ 对加法、数乘运算是封闭的，所以 $S$ 构成一个向量空间

定义内积构成内积空间

• 在 $S$ 上定义运算 $ * $：对任意 $f,g \in S$

  $$\begin{align*} f(·) = \sum_{i=1}^m \alpha_i K(·, x_i) \\ g(·) = \sum_{j=1}^n \beta_j K(·, z_j) \end{align*}$$

  定义运算 $ * $

  $$f * g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \beta_j K(x_i, z_j)$$

• 为证明运算 $ * $ 是空间 $S$ 的内积

  • 需要证明：
    • $(cf) g = c(f g), c \in R$
    • $(f + g) h = f h + g * h, h \in S$
    • $f g = g f$
    • $f f \geq 0, f f = 0 \Leftrightarrow f = 0$
  • 其中前3条由 $S$ 元素定义、$K(x,z)$ 对称性容易得到
  • 由 $ * $ 运算规则可得 $$f * f = \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i, x_j)$$ 由 Gram 矩阵非负可知上式右端非负，即 $f * f \geq 0$

• 为证明 $f * f \Leftrightarrow f = 0$

  • 首先证明

    $$|f * g|^2 \leq (f * f)(g * g)$$

    • 设$f, g \in S$，则有$f + \lambda g \in S$，则有

      $$\begin{align*} (f + \lambda g) * (f + \lambda g) & \geq 0 \\ f*f + 2\lambda (f * g) + \lambda^2 (g*g) & \geq 0 \end{align*}$$

    • 则上述关于$\lambda$的判别式非负，即

      $$(f*g)^2 - (f*f)(g*g) \leq 0$$

  • $\forall x \in \mathcal{x}$，有

    $$K(·, x) * f = \sum_{i=1}^m \alpha_i K(x, x_i) = f(x)$$

    则有

    $$|f(x)|^2 = |K(·, x) * f|^2$$

  • 又

    $$|K(·, x) * f|^2 \leq (K(·, x) * K(·, x))(f * f) = K(x, x)(f*f)$$

    则有

    $$|f(x)|^2 \leq K(x, x) (f * f)$$

    即$f * f = 0$时，对任意$x$都有$|f(x)| = 0$

• 因为 $ * $ 为向量空间 $S$ 的内积，可以继续用 $ · $ 表示

  $$f·g = \sum_{i=1}^m \sum_{j=1}^n \alpha_i \alpha_j K(x_i,z_J)$$

完备化构成Hilbert空间

• 根据内积定义可以得到范数

  $$\|f\| = \sqrt {f · f}$$

  所以 $S$ 是一个赋范向量空间，根据泛函分析理论，对于不完备的赋范空间 $S$ ，一定可以使之完备化得到希尔伯特空间 $\mathcal{H}$

• 此希尔伯特空间 $\mathcal{H}$ ，称为 reproducing kernel Hilber Space ，因为核 $K$ 具有再生性

  $$\begin{align*} K(·, x) · f & = f(x) \\ K(·, x) · K(·, Z) & = K(x, z) \end{align*}$$

Positive Definite Kernel Function

• 设 $K: \mathcal{X X} \leftarrow R$ 是对称函数，则 $K(x,z)$ 为正定核函数的充要条件是 $\forall x_i \in \mathcal{X}, i=1,2,…,m$，$K(x,z)$ 对应的 Gram 矩阵 $K = [K(xi, x_j)]{mm} $ 是半正定矩阵

• 必要性

• 由于 $K(x,z)$ 是 $\mathcal{X X}$ 上的正定核，所以存在从 $\mathcal{X}$ 到 Hilbert* 空间 $\mathcal{H}$ 的映射，使得

  $$K(x,z) = \phi(x) \phi(z)$$

• 则对任意 $x_1, x_2, \cdots, x_m$，构造 $K(x,z)$ 关于其的 Gram 矩阵

  $$[K_{ij}]_{m*m} = [K(x_i, x_i)]_{m*m}$$

• 对任意 $c_1, c_2, \cdots, c_m \in R$，有

  $$\begin{align*} \sum_{i,j=1}^m c_i c_j K(x_i, x_j) & = \sum_{i,j=1}^m c_i c_j (\phi(x_i) \phi(x_j)) \\ & = (\sum_i c_i \phi(x_i))(\sum_j c_j \phi(x_j)) \\ & = \| \sum_i c_i \phi(x_i) \|^2 \geq 0 \end{align*}$$

  所以 $K(x,z)$ 关于 $x_1, x_2, \cdots, x_m$ 的 Gram 矩阵半正定

• 充分性

• 对给定的 $K(x,z)$，可以构造从 $\mathcal{x}$ 到某个希尔伯特空间的映射

  $$\phi: x \leftarrow K(·, x)$$

• 且有

  $$K(x,z) = \phi(x) · \phi(z)$$

  所以 $K(x,z)$ 是 $\mathcal{X * X}$ 上的核函数