《机器学习》学习笔记.tex

\documentclass{ctexart}

\usepackage{xeCJK}
\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{newfloat}
\usepackage{setspace}
\usepackage{tikz}
\usepackage{bm}
\usepackage{multirow}
\usepackage{enumerate}
\usepackage{mathrsfs}
\usepackage{listings}
\usepackage{framed}
\usepackage[colorlinks,linkcolor=black,anchorcolor=black,citecolor=black,CJKbookmarks=True]{hyperref}
\usepackage{fancyhdr}
\allowdisplaybreaks[4]
\usetikzlibrary{arrows,graphs}
\usetikzlibrary{graphs}
\usetikzlibrary{graphs.standard}
\pagestyle{fancy}
\fancyhead[L]{Machine Learning}
\usetikzlibrary {positioning}
\definecolor {processblue}{cmyk}{0.96,0,0,0}
\setCJKmainfont{STKaiti}

\newtheorem{theorem}{Theorem}
\newcommand{\bigCI}{\mathrel{\text{\scalebox{1.07}{$\perp\mkern-10mu\perp$}}}}

\renewcommand{\algorithmicrequire}{\textbf{Input:}} 
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\begin{document}
			\title{《机器学习》读书笔记}
			\author{黄奕诚}
			\date{}
			\maketitle
			
			\tableofcontents
			\newpage
			\section{绪论}
				\subsection{引言}
					\begin{itemize}
						\item 机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。
						\item 机器学习研究的主要内容：在计算机上从数据中产生``模型''的算法，即``学习算法''。
					\end{itemize}
				\subsection{基本术语}
					\begin{itemize}
						 \item 数据集（data set）：一组记录的集合
						 \item 示例（instance）/样本（sample）：每条记录，即关于一个事件或对象的描述
						 \item 属性（attribute）/特征（feature）：反映事件或对象在某方面的表现或性质的事项
						 \item 属性值（attribute value）：属性上的取值
						 \item 属性空间（attribute space）/样本空间（sample space）/输入空间：属性张成的空间，记为$\mathcal{X}$
						 \item 特征向量（feature vector）：一个示例（在样本空间对应的坐标向量）
						 \item 学习（learning）/训练（training）：从数据中学得模型的过程
						 \item 训练数据（training data）：训练过程中使用的数据
						 \item 训练样本（training sample）：训练数据中的每个样本
						 \item 训练集（training set）：训练样本组成的集合
						 \item 假设（hypothesis）：对应了关于数据的某种潜在规律的学得模型
						 \item 真实（ground-truth）：潜在规律自身
						 \item 学习器（learner）：学习算法在给定数据和参数空间上的实例化
						 \item 标记（label）：关于示例结果的信息
						 \item 样例（example）：拥有标记信息的示例
						 \item 标记空间（label space）/输出空间：所有标记的集合，记为$\mathcal{Y}$
						 \item 分类（classification）：预测的是离散值的学习任务（二分类$\mathcal{Y}=\{-1,+1\}\textrm{或}\{0,1\}$；三分类$|\mathcal{Y}|>2$）
						 \item 回归（regression）：预测的是连续值的学习任务（$\mathcal{Y}=\mathbb{R}$）
						 \item 测试（testing）：使用学得模型进行预测的过程
						 \item 测试样本（testing sample）：被预测的样本
						 \item 无监督学习（unsupervised learning）：训练数据中没有标记信息的学习任务，代表是聚类（clustering）
						 \item 监督学习（supervised learning）：训练数据中具有标记信息的学习任务，代表是分类和回归
						 \item 泛化（generalization）能力：学得模型适用于新样本的能力
					\end{itemize}
				\subsection{假设空间}
					\begin{itemize}
						\item ``从样例中学习''是一个归纳的过程。
						\item 可以把学习过程看作一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集``匹配''（fit）的假设。
						\item 假设空间可以表示为一课属性值中通配符逐渐被具体数值取代的树。
						\item 可以用许多策略对假设空间进行搜索，如自顶向下（从一般到特殊）、自底向上（从特殊到一般）。
						\item 可能有多个假设与训练集一致，即存在着一个与训练集一致的``假设集合''，称之为``版本空间''（version space）。
					\end{itemize}
				\subsection{归纳偏好}
					\begin{itemize}
						\item 多个与训练集一致的假设所对应的模型在面临新样本时，可能产生不同的输出。而对于一个具体的学习算法而言，必须要产生一个模型。此时学习算法本身的偏好会起到关键的作用。
						\item 归纳偏好（inductive bias）：机器学习算法在学习过程中对某种类型假设的偏好。
						\item 奥卡姆剃刀（Occam's razor）：若有多个假设与观察一致，则选最简单的那个。【常用的、自然科学研究中最基本的原则】
						\item 设$f$为希望学习的真实目标函数，则基于训练数据$X$的算法$\mathfrak{L}_a$在训练集之外的所有样本上的误差与学习算法无关，即\[\sum_{f}^{}E_{ote}(\mathfrak{L}_a|X,f)=\sum_{f}^{}E_{ote}(\mathfrak{L}_b|X,f)\]``没有免费的午餐''定理（NFL定理）：所有学习算法的期望性相同。
					\end{itemize}
				\subsection{发展历程}
					\begin{enumerate}[1.]
						\item 二十世纪五十年代到七十年代初：``推理期''——赋予机器逻辑推理能力
						\item 二十世纪七十年代中期开始：``知识期''
							\begin{enumerate}[a.]
								\item 机械学习（信息存储与检索）
								\item 示教学习（从指令中学习）
								\item 类比学习（通过观察和发现学习）
								\item 归纳学习（从样例中学习）
									\begin{itemize}
										\item 符号主义学习（决策树、基于逻辑的学习）
										\item 连接主义学习（神经网络）
										\item 统计学习（支持向量机、核方法）
										\item 深度学习
									\end{itemize}
							\end{enumerate}
					\end{enumerate}
				\subsection{应用现状}
					\begin{itemize}
						\item 计算机科学诸多分支学科领域（如计算机视觉、自然语言处理）
						\item 交叉学科（如生物信息学）
						\item 数据挖掘（机器学习领域和数据库领域是数据挖掘的两大支撑）
						\item 人类日常生活（天气预报、搜索引擎、自动驾驶、政治选举等）
						\item 促进人们理解``人类如何学习''
					\end{itemize}
			\section{模型评估与选择}
				\subsection{经验误差与过拟合}
					\begin{itemize}
						\item 设在$m$个样本中有$a$个样本分类错误，则错误率（error rate）为$E=a/m$，精度（accuracy）为$1-a/m$。
						\item 误差（error）：学习器的实际预测输出与样本的真实输出之间的差异。训练误差（training error）/经验误差（empirical error）：学习器在训练集上的误差。泛化误差（generalization error）：学习器在新样本上的误差。想要使泛化误差最小，而新样本未知，所以努力使经验误差最小化。
						\item 过拟合（overfitting）：学习器将训练样本自身的一些特点当作为所有潜在样本都会具有的一般性质。【关键障碍、无法彻底避免】欠拟合（underfitting）：学习器对训练样本的一般性质尚未学好。【较容易克服】若``P$\neq$NP''，过拟合就不可避免。
					\end{itemize}
				\subsection{评估方法}
				
					为了对学习器对泛化误差进行评估，需要使用一个测试集（testing set）来测试学习器对新样本的判别能力，然后以测试集上的测试误差（testing error）作为泛化误差的近似。
					
					若当前只有一个包含$m$个样例的数据集\[D=\{(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)\}\]，则对其进行适当的处理，从中产生训练集$S$和测试集$T$。
					\subsubsection{留出法}
					
						直接将数据集$D$划分为两个互斥的集合，其中一个作为训练集$S$，另一个作为测试集$T$，即$D=S\cup T,S\cap T=\emptyset$，在$S$上训练出模型后，用$T$来评估其测试误差，作为对泛化误差的估计。
						\begin{itemize}
							\item 划分尽可能保持数据分布的一致性，例如在分类任务中至少要保持样本的类别比例相似（分层采样）。
							\item 一般采用若干次随机划分、重复进行实验评估后取平均值作为评估结果。
							\item $S$和$D$大小权衡没有完美的解决方案，常见做法是2/3$\sim$4/5的训练样本比例。
						\end{itemize}
					\subsubsection{交叉验证法}
						
						将数据集$D$划分为$k$个大小相似的互斥子集，即\[D=D_1\cup D_2\cup\dots\cup D_k,D_i\cup D_j=\emptyset(i\neq j)\]每个子集$D_i$都尽可能保持数据分布的一致性（分层抽样）。然后从中选取$k-1$个子集为训练集，剩下一个子集为测试集。可进行$k$次训练和测试，最终返回$k$个测试结果的均值。也称为``$k$折交叉验证''（$k$-fold cross validation）。
						\begin{itemize}
							\item $k$最常用的取值是10，常用的还有5、20等。
							\item 留一法（Leave-One-Out）不受随机样本划分的影响，评估结果比较准确，但计算开销大。
						\end{itemize}
					\subsubsection{自助法}
						
						以自助采样法（bootstrap sampling）为基础，给定包含$m$个样本的数据集$D$，每次随机从$D$中挑选一个样本，将其拷贝放入$D'$，再将该样本放回初始数据集$D$中。这个过程重复执行$m$次后，得到了包含$m$个样本的数据集$D'$。此时将$D'$用作训练集，$D\backslash D'$用作测试集。
						\begin{itemize}
							\item $D$有约36.8\%的样本未出现在采样数据集$D'$中。
							\item 亦称为``包外估计''（out-of-bag estimate）。
							\item 自助法在数据集较小、难以有效划分训练/测试集时很有用，且能从初始数据集中产生多个不同的训练集。
							\item 因为自助法产生的数据集改变了初始数据集的分布，会引入估计偏差。
						\end{itemize}
					\subsubsection{调参与最终模型}
						\begin{itemize}
							\item 常用的调参做法：对每个参数选定一个范围和变化步长，进行计算开销和性能估计之间的折中。
							\item 在模型选择完成后，学习算法和参数配置已选定，此时用数据集$D$重新训练模型，使用所有$m$个样本，得到最终提交给用户的模型。
						\end{itemize}
				\subsection{性能度量}
					
					给定样例集\[D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}\]其中$y_i$是示例$\bm{x}_i$的真实标记。要评估学习器$f$的性能，即把学习器预测结果$f(\bm{x})$与真实标记$y$进行比较。
					
					回归任务中最常用的性能度量：``均方误差''（mean squared error）\[E(f;D)=\frac{1}{m}\sum_{i=1}^{m}(f(\bm{x}_i)-y_i)^2\]更一般地，对于数据分布$\mathcal{D}$和概率密度函数$p(\cdot)$，均方误差可描述为\[E(f;\mathcal{D})=\int_{x\sim\mathcal{D}}^{}(f(\bm{x})-y)^2p(\bm{x})d\bm{x}\]对于分类任务——
					\subsubsection{错误率与精度}
						\begin{itemize}
							\item 分类错误率\[E(f;D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}(f(\bm{x}_i)\neq y_i)\]精度\[\mathrm{acc}(f;D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}(f(\bm{x}_i)=y_i)=1-E(f;D)\]
							\item 对于数据分布$\mathcal{D}$和概率密度函数$p(\cdot)$，错误率\[E(f;\mathcal{D})=\int_{x\sim\mathcal{D}}^{}\mathbb{I}(f(\bm{x})\neq y)p(\bm{x})d\bm{x}\]精度\[\mathrm{acc}(f;\mathcal{D})=\int_{x\sim\mathcal{D}}^{}\mathbb{I}(f(\bm{x})=y)p(\bm{x})d\bm{x}=1-E(f;\mathcal{D})\]
						\end{itemize}
					\subsubsection{查准率、查全率与$F1$}
						\begin{center}
							\begin{tabular}{c|c|c}
								\hline
								\multirow{2}*{真实情况} & \multicolumn{2}{|c}{预测结果}\\
								\cline{2-3}
								& 正例 & 反例\\
								\hline
								正例 & $TP$（真正例）& $FN$（假反例）\\
								\hline
								反例 & $FP$（假正例）& $TN$（真反例）\\
								\hline 
							\end{tabular}
						\end{center}
						查准率（precision）\[P=\frac{TP}{TP+FP}\]查全率（recall）\[R=\frac{TP}{TP+FN}\]
						\begin{itemize}
							\item 平衡点（Break-Even Point，BEP）：$R=P$时的取值，数值越高可以认为学习器越优。
							\item $F1$度量\[F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{\textrm{样例总数}+TP-TN}\]实际上$F1$是$R$和$P$的调和平均\[\frac{1}{F1}=\frac{1}{2}(\frac{1}{P}+\frac{1}{R})\]
							\item $F_\beta$度量：考虑$R$与$P$的不同偏好，设$\beta$为查全率$R$对查准率$P$的相对重要性，则\[F_\beta=\frac{(1+\beta^2)\times P\times R}{(\beta^2\times P)+R}\]实际上$F_\beta$是加权调和平均\[\frac{1}{F_\beta}=\frac{1}{1+\beta^2}(\frac{1}{P}+\frac{\beta^2}{R})\]
							\item 宏$F1$：在各混淆矩阵上分别计算出各自的$(P_i,R_i)$，再计算平均值：\[\mathrm{macro-}P=\frac{1}{n}\sum_{i=1}^{n}P_i\]\[\mathrm{macro-}R=\frac{1}{n}\sum_{i=1}^{n}R_i\]\[\mathrm{macro-}F1=\frac{2\times\mathrm{macro-}P\times\mathrm{macro-}R}{\mathrm{macro-}P+\mathrm{macro-}R}\]
							\item 微$F1$：先将各混淆矩阵的对应元素进行平均得到四个指标，再基于这些平均值计算$F1$：\[\mathrm{micro-}P=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}\]\[\mathrm{micro-}R=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}\]\[\mathrm{micro-}F1=\frac{2\times\mathrm{micro-}P\times\mathrm{micro-}R}{\mathrm{micro-}P+\mathrm{micro-}R}\]
						\end{itemize}
						\begin{framed}
							$\triangle$ 混淆矩阵介绍：每一列代表了预测类别，每一列的总数表示预测为该类别的数据的数目；每一行代表了数据的真实归属类别 ，每一行的数据总数表示该类别的数据实例的数目。例如共有150个样本数据，预测为1、2、3类各50个，分类结束后得到的混淆矩阵为\begin{center}
								\begin{tabular}{|c|c|c|c|c|}
									\hline
									\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{3}{c|}{预测} \\ \cline{3-5} 
									\multicolumn{2}{|c|}{}                  & 类1     & 类2     & 类3    \\ \hline
									\multirow{3}{*}{实际}         & 类1        & 43     & 2      & 0     \\ \cline{2-5} 
									& 类2        & 5      & 45     & 1     \\ \cline{2-5} 
									& 类3        & 2      & 3      & 49    \\ \hline
								\end{tabular}
							\end{center}
						\end{framed}
					\subsubsection{ROC与AUC}
					
						ROC全称是``受试者工作特征''（Receiver Operating Characteristic）曲线。横轴为``假正例率''（$FPR$），纵轴为``真正例率''（$TPR$）。\[TPR=\frac{TP}{TP+FN}\]\[FPR=\frac{FP}{TN+FP}\]
						\begin{itemize}
							\item 现实任务中ROC曲线的绘制方法：给定$m^+$个正例和$m^-$个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，此时$FPR$和$TPR$都为0.在坐标$(0, 0)$处标记一个点，然后将分类阈值依次设为每个样例的预测值。设当前一个标记点坐标为$(x,y)$，若当前为真正例，则对应标记点坐标为$(x,y+\frac{1}{m^+})$；若当前为假正例，则对应标记点坐标为$(x+\frac{1}{m^-},y)$，然后用线段连接相邻点即得。
							\item AUC（Area Under ROC Curve）即为ROC曲线下各部分的面积之和。设ROC曲线是由坐标为$\{(x_i,y_i)|1\le i\le m\}$的点按序连接而成，则AUC可估算为\[\mathrm{AUC}=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_i)\cdot(y_i+y_{i+1})\]
							\item 给定$m^+$个正例和$m^-$个反例，令$D^+$和$D^-$分别表示正、反例集合，则排序``损失''（loss）定义为\[\ell_{rank}=\frac{1}{m^+m^-}\sum_{\bm{x}^+\in D^+}^{}\sum_{\bm{x}^-\in D^-}^{}\bigg(\mathbb{I}\big(f(\bm{x}^+)<f(\bm{x}^-)\big)+\frac{1}{2}\mathbb{I}\big(f(\bm{x}^+)=f(\bm{x}^-)\big)\bigg)\]它对应ROC曲线之上的面积，有\[\mathrm{AUC}=1-\ell_{rank}\]
						\end{itemize}
					\subsubsection{代价敏感错误率与代价曲线}
						\begin{itemize}
							\item 不同类型的错误可能造成不同损失，所以为错误赋予``非均等代价''（unequal cost）。
							\item 以二分类为例，可以设定一个``代价矩阵''，如下表所示。\begin{center}
								\begin{tabular}{|c|c|c|}
									\hline
									\multirow{2}{*}{真实类别} & \multicolumn{2}{c|}{预测类别} \\ \cline{2-3} 
									& 第0类         & 第1类         \\ \hline
									第0类                   & 0           & $cost_{01}$ \\ \hline
									第1类                   & $cost_{10}$ & 0           \\ \hline
								\end{tabular}	
							\end{center}
							\item ``代价敏感''（cost-sensitive）错误率\[E(f;D;cost)=\frac{1}{m}\bigg(\sum_{\bm{x}_i\in D^+}^{}\mathbb{I}\big(f(\bm{x}_i)\neq y_i\big)\times cost_{01}+\sum_{\bm{x}_i\in D^-}^{}\mathbb{I}\big(f(\bm{x}_i)\neq y_i\big)\times cost_{10}\bigg)\]
							\item 在非均等代价下， ``代价曲线''（cost curve）可以刻画期望总体代价。设$p$是样例为正例的概率。横轴为正例概率代价\[P(+)cost = \frac{p\times cost_{01}}{p\times cost_{01}+(1-p)\times cost_{10}}\]纵轴为取值为$[0,1]$的归一化代价\[cost_{norm}=\frac{\mathrm{FNR}\times p\times cost_{01}+\mathrm{FPR}\times(1-p)\times cost_{10}}{p\times cost_{01}+(1-p)\times cost_{10}}\]
							\item 代价曲线的绘制方法：将ROC曲线上的每一点转化为代价平面上的一条线段，取所有线段的下界，围成的面积即为所有条件下学习器的期望总体代价。
						\end{itemize}
				\subsection{比较检验}
					
					本节默认以错误率$\epsilon$为性能度量。
					\subsubsection{假设检验}
						\begin{itemize}
							\item 设一个学习器的泛化错误率为$\epsilon$，在$m$个样本中的测试错误率为$\hat{\epsilon}$，则其被测得测试错误率为$\hat{\epsilon}$的概率为\[P(\hat{\epsilon};\epsilon)=\binom{m}{\hat{\epsilon}\times m}\epsilon^{\hat{\epsilon}\times m}(1-\epsilon)^{m-\hat{\epsilon}\times m}\]它在$\epsilon=\hat{\epsilon}$时最大。
							\item 二项检验：假设$\epsilon\le\epsilon_0$，则在$1-\alpha$的概率内所能观测到的最大错误率为\[\sum_{i=\epsilon_0\times m+1}^{m}\binom{m}{i}\epsilon^i(1-\epsilon)^{m-i}<\alpha\]\[\bar{\epsilon}=\mathrm{max}\epsilon\]若测试错误率$\hat{\epsilon}$小于临界值$\bar{\epsilon}$，则能以$1-\alpha$的置信度认为学习器的泛化错误率不大于$\epsilon_0$，否则假设被拒绝。
							\item $t$检验：若得到了$k$个测试错误率$\hat{\epsilon}_1,\hat{\epsilon}_2,\dots,\hat{\epsilon}_k$，则平均测试错误率$\mu$和方差$\sigma^2$为\[\mu=\frac{1}{k}\sum_{i=1}^{k}\hat{\epsilon}_i\]\[\sigma^2=\frac{1}{k-1}\sum_{i=1}^{k}(\hat{\epsilon}_i-\mu)^2\]它们可看作泛化错误率$\epsilon_0$的独立采样，则变量\[\tau_t=\frac{\sqrt{k}(\mu-\epsilon_0)}{\sigma}\]服从自由度为$k-1$的$t$分布。若$|\mu-\epsilon_0|$位于$[t_{-\alpha/2},t_{\alpha/2}]$内，则接受假设$\mu=\epsilon_0$，否则拒绝该假设。
						\end{itemize}
					\subsubsection{交叉验证$t$检验}
						\begin{itemize}
							\item $k$折交叉验证``成对$t$检验''：对每对结果求差$\Delta_i=\epsilon_i^A-\epsilon_i^B$，若两个学习器性能相同，则差值均值为0。做$t$检验，在显著度$\alpha$下，若\[\tau_t=|\frac{\sqrt{k}\mu}{\sigma}|<t_{\alpha/2,k-1}\]则接受假设。其中$t_{\alpha/2,k-1}$指自由度为$k-1$的$t$分布上尾部累积分布为$\alpha/2$的临界值。
							\item 考虑到交叉验证法等实验估计方法，不同轮次的训练集会有一定程度的重叠，导致测试错误率并不独立。故可采用$5\times2$交叉验证法（5次2折交叉验证）。每次2折交叉验证之前随机将数据打乱，使得5次交叉验证中的数据划分不重复。设$\Delta_i^k$表示第$i$次第$k$上的差值。\[\mu=0.5(\Delta_1^1+\Delta_1^2)\]\[\sigma_i^2=\big(\Delta_i^1-\frac{\Delta_i^1+\Delta_i^2}{2}\big)^2+\big(\Delta_i^2-\frac{\Delta_i^1+\Delta_i^2}{2}\big)^2\]变量\[\tau_t=\frac{\mu}{\sqrt{0.2\sum_{i=1}^{5}\sigma_i^2}}\]服从自由度为5的$t$分布，其双边检验的临界值为$t_{\alpha/2,5}$。
						\end{itemize}
					\subsubsection{McNemar检验}
						
						对于二分类问题，可统计两个学习器A和B的分类结果样本数差别，列出``列联表''（contingency table）\begin{center}
							\begin{tabular}{|c|c|c|}
								\hline
								\multirow{2}{*}{算法B} & \multicolumn{2}{c|}{算法A} \\ \cline{2-3} 
								& 正确          & 错误         \\ \hline
								正确                   & $e_{00}$    & $e_{01}$   \\ \hline
								错误                   & $e_{10}$    & $e_{11}$   \\ \hline
							\end{tabular}
						\end{center}
					
						假设两学习器性能相同，则$e_{01}=e_{10}$，于是$|e_{01}-e_{10}|$服从正态分布，变量\[\tau_{\chi^2}=\frac{(|e_{01}-e_{10}|-1)^2}{e_{01}+e_{10}}\]服从自由度为1的$\chi^2$分布，若其小于临界值$\chi_\alpha^2$则接受假设，否则拒绝假设，较小者性能更优。
					\subsubsection{Friedman检验与Nemenyi后续检验}
						\begin{itemize}
							\item 在多个数据集上比较算法。
							\item 算法排序：使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果，然后在每个数据集上根据测试性能由好到坏排序，序值从1递增，若相同则平分序值。
							\item ``原始Friedman检验''：假定在$N$个数据集上比较$k$个算法，令$r_i$表示第$i$个算法的平均序值，暂不考虑平分序值，则$r_i$均值为$(k+1)/2$，方差为$(k^2-1)/12$。变量\[\tau_{\chi^2}=\frac{k-1}{k}\cdot\frac{12N}{k^2-1}\sum_{i=1}^{k}\big(r_i-\frac{k+1}{2}\big)^2=\frac{12N}{k(k+1)}\bigg(\sum_{i=1}^{k}r_i^2-\frac{k(k+1)^2}{4}\bigg)\]当$k$和$N$都较大时服从自由度为$k-1$的$\chi^2$分布。
							\item Friedman检验：变量\[\tau_F=\frac{(N-1)\tau_{\chi^2}}{N(k-1)-\tau_{\chi^2}}\]服从自由度为$k-1$和$(k-1)(N-1)$的F分布。
							\item Nemenyi检验：若``所有算法的性能相同''这一假设被拒绝，此时计算出平均序值差别的临界值域\[CD=q_{\alpha}\sqrt{\frac{k(k+1)}{6N}}\]若某两个算法的平均序值之差超出了$CD$，则以相应的置信度拒绝``这两个算法性能相同''这一假设。
							\item Friedman检验图：横轴为平均序值，纵轴为各个算法，对每个算法以一个圆点表示平均序值，以圆点为中心的横线段表示临界值域的大小。若两个算法的横线段有交叠，则说明它们没有显著区别，否则可以进行显著比较。
						\end{itemize}
				\subsection{偏差与方差}
					\begin{itemize}
						\item 偏差-方差分解：对学习算法的期望泛化错误率进行拆解。
						\item 学习算法的期望预测\[\bar{f}(\bm{x})=\mathbb{E}_D[f(\bm{x};D)]\]
						\item 使用样本数相同的不同训练集产生的方差\[var(\bm{x})=\mathbb{E}\big[(f(\bm{x};D)-\bar{f}(\bm{x})^2\big]\]
						\item 噪声\[\varepsilon^2=\mathbb{E}_D\big[(y_D-y)^2\big]\]
						\item 偏差（期望输出与真实标记的差别）\[bias^2(\bm{x})=\big(\bar{f}(\bm{x})-y\big)^2\]
						\item 假定$\mathbb{E}_D[y_D-y]=0$，则可通过多项式展开得到\[E(f;D)=\mathbb{E}_D\big[(f(\bm{x};D)-y_D)^2\big]=bias^2(\bm{x})+var(\bm{x})+\varepsilon^2\]泛化误差可分解为偏差、方差与噪声之和。
						\item 偏差：学习算法本身的拟合能力；方差：数据的充分性；噪声：学习问题本身的难度
						\item 偏差-方差窘境（bias-variance dilemma）：训练不足时偏差主导，训练加深时方差主导，训练充足时容易发生过拟合。
					\end{itemize}
			\section{线性模型}
				\subsection{基本形式}
				
					示例$\bm{x}=(x_1;x_2;\dots;x_d)$，其中$x_i$是$\bm{x}$在第$i$个属性上的取值，则线性模型\[f(\bm{x})=w_1x_1+w_2x_2+\dots+w_dx_d+b=\bm{w}^T\bm{x}+b\]
				\subsection{线性回归}
					\begin{itemize}
						\item 一元线性回归的目标\[f(x_i)=wx_i+b,\textrm{ 使得}f(x_i)\simeq y_i\]其中\[(w^*,b^*)=\mathrm{arg}_{(w,b)}\mathrm{min}\sum_{i=1}^{m}(y_i-wx_i-b)^2\]利用``最小二乘法''的最小二乘``参数估计''将$E_{(w,b)}=\sum_{i=1}^{m}(y_i-wx_i-b)^2$对$w$和$b$分别求导并令为零即可得到$w,b$最优解的闭式解\[w=\frac{\sum_{i=1}^{m}y_i(x_i-\bar{x})}{\sum_{i=1}^{m}x_i^2-\frac{1}{m}\big(\sum_{i=1}^{m}x_i\big)^2}\mathrm{\qquad}b=\frac{1}{m}\sum_{i=1}^{m}(y_i-wx_i)\]
						\item 多元线性回归的目标\[f(\bm{x}_i)=\bm{w}^T\bm{x}_i+b,\textrm{ 使得}f(\bm{x}_i)\simeq y_i\]设$\hat{\bm{w}}=(\bm{w};b)$，将数据集$D$表示为一个$m\times(d+1)$大小的矩阵$\bm{X}$\[\bm{X}=\left(\begin{matrix}
						x_{11} & x_{12} & \cdots & x_{1d} & 1 \\
						x_{21} & x_{22} & \cdots & x_{2d} & 1 \\
						\vdots & \vdots & \ddots & \vdots & \vdots \\
						x_{m1} & x_{m2} & \cdots & x_{md} & 1
						\end{matrix}\right)=\left(\begin{matrix}
						\bm{x}_1^T & 1 \\
						\bm{x}_2^T & 1 \\
						\vdots & \vdots \\
						\bm{x}_m^T & 1
						\end{matrix}\right)\]其中\[\hat{\bm{w}}^*=\mathrm{arg}_{\hat{\bm{w}}}\mathrm{min}(\bm{y}-\bm{X\hat{w}})^T(\bm{y}-\bm{X\hat{w}})\]令$E_{\hat{\bm{w}}}=(\bm{y}-\bm{X\hat{w}})^T(\bm{y}-\bm{X\hat{w}})$，对$\bm{\hat{w}}$求导并令为零即$2\bm{X}^T(\bm{X\hat{w}}-\bm{y})=0$即可。若$\bm{X}^T\bm{X}$正定（满秩），则求出$\hat{\bm{w}}^*=(\bm{X}^T\bm{X})^{-1}\bm{X}^T\bm{y}$，此时\[f(\hat{\bm{x}}_i)=\hat{\bm{x}}_i^T(\bm{X}^T\bm{X})^{-1}\bm{X}^T\bm{y}\]若$\bm{X}^T\bm{X}$不满秩，则可能有多解，通过引入正则化由归纳偏好决定。
						\item 广义线性模型：考虑单调可微函数$g(\cdot)$\[y=g^{-1}(\bm{w}^T\bm{x}+b)\]其中$g(\cdot)$称为``联系函数''。
					\end{itemize}
				\subsection{对数几率回归}
					\begin{itemize}
						\item 单位阶跃函数：对于二分类问题将线性回归模型的实值转化为0/1值。其中预测值为临界值零可任意判别\[y=\left\{\begin{aligned}
						0,\quad & z < 0; \\
						0.5,\quad & z = 0; \\
						1,\quad & z > 0;
						\end{aligned}\right.\]
						\item 对数几率函数\[y=\frac{1}{1+e^{-(\bm{w}^T\bm{x}+b)}}\]可化为\[\ln\frac{y}{1-y}=\bm{w}^T\bm{x}+b\]其中$y$可视为$\bm{x}$作为正例的可能性，$1-y$可视为其作为反例的可能性。
						\item 对数几率回归的$\bm{w},b$估计方法：极大似然法。【TODO：细节待学完7.2节极大似然法及梯度下降法再补充】
					\end{itemize}
				\subsection{线性判别分析}
					\begin{itemize}
						\item 思想：设法将样例投影到一条直线上，使得同类样例的投影尽可能接近、异类样例的投影尽可能远离。对于新样本根据其投影到这条直线的投影点位置进行分类。\begin{framed}
							$\triangle$ L2范数（例如欧氏距离）\[\parallel x\parallel_2=\sqrt{\sum_{i=1}^{k}|x_i|^2}\]
						\end{framed}
						\item 目的：使同类样例投影点的协方差（$\bm{w}^T\Sigma_{0}^{}\bm{w}+\bm{w}^T\Sigma_{1}^{}\bm{w}$）尽可能小，使类中心之间的距离（$\parallel\bm{w}^T\bm{\mu}_0-\bm{w}^T\bm{\mu}_1\parallel_2^2$）尽可能大。
						\item 类内散度矩阵\[\bm{S}_w=\Sigma_{0}+\Sigma_{1}=\sum_{\bm{x}\in X_0}^{}(\bm{x}-\bm{\mu}_0)(\bm{x}-\bm{\mu}_0)^T+\sum_{\bm{x}\in X_1}^{}(\bm{x}-\bm{\mu}_1)(\bm{x}-\bm{\mu}_1)^T\]
						\item 类间散度矩阵\[\bm{S}_b=(\bm{\mu}_0-\bm{\mu}_1)(\bm{\mu}_0-\bm{\mu}_1)^T\]
						\item 欲最大化目标（$\bm{S}_b$与$\bm{S}_w$的广义Rayleigh商）\[J=\frac{\parallel\bm{w}^T\bm{\mu}_0-\bm{w}^T\bm{\mu}_1\parallel_2^2}{\bm{w}^T\Sigma_{0}^{}\bm{w}+\bm{w}^T\Sigma_{1}^{}\bm{w}}=\frac{\bm{w}^T(\bm{\mu}_0-\bm{\mu}_1)(\bm{\mu}_0-\bm{\mu}_1)^T\bm{w}}{\bm{w}^T(\Sigma_{0}+\Sigma_{1})\bm{w}}=\frac{\bm{w}^T\bm{S}_b\bm{w}}{\bm{w}^T\bm{S}_w\bm{w}}\]
						\item 确定$\bm{w}$的方法：$J$中的解与$\bm{w}$的长度无关，故令$\bm{w}^T\bm{S}_w\bm{w}=1$，转化为：已知$\bm{w}^T\bm{S}_w\bm{w}=1$求$-\bm{w}\bm{S}_b\bm{w}$的最小值。由拉格朗日乘子法，即$\bm{S}_b\bm{w}=\lambda\bm{S}_w\bm{w}$。又$\bm{S}_b\bm{w}$方向恒为$\bm{\mu}_0-\bm{\mu}_1$，令$\bm{S}_b\bm{w}=\lambda(\bm{\mu}_0-\bm{\mu}_1)$，得\[\bm{w}=\bm{S}_w^{-1}(\bm{\mu}_0-\bm{\mu}_1)\]对$\bm{S}_w$进行奇异值分解$\bm{S}_w=\bm{U\Sigma V}^T$，由$\bm{S}_w^{-1}=\bm{V\Sigma}^{-1}\bm{U}^{-1}$得到$\bm{w}$。
						\begin{framed}
							$\triangle$ 上例用拉格朗日乘子法的计算细节：目标函数为$f(\bm{x})=-\bm{w}\bm{S}_b\bm{w}$，约束方程$g(\bm{x})=\bm{w}^T\bm{S}_w\bm{w}-1=0$。等价于由方程$g(\bm{x})=0$确定的$d-1$维曲面上寻找能使$f(\bm{x})$最小化的点，满足\begin{enumerate}[(1)]
								\item 约束曲面上任意点$\bm{x}$的梯度$\nabla g(\bm{x})$正交于约束曲面
								\item 在最优点$\bm{x}^*$，$f(\bm{x})$在该点的梯度$\nabla f(\bm{x}^*)$正交于约束曲面
							\end{enumerate}于是在最优点$\bm{x}^*$，梯度$\nabla g(\bm{x})$和$\nabla f(\bm{x})$的方向必相同或相反，即存在$\lambda\neq0$使得\[\nabla f(\bm{x}^*)+\lambda\nabla g(\bm{x}^*)=0\]即\[\bm{S}_b\bm{w}=\lambda\bm{S}_w\bm{w}\]
						\end{framed}
						\item LDA推广到多分类任务。假设存在$N$个类，且第$i$类示例数为$m_i$。设$\bm{\mu}$是所有示例的均值向量。全局散度矩阵\[\bm{S}_t=\bm{S}_b+\bm{S}_w=\sum_{i=1}^{m}(\bm{x}_i-\bm{\mu})(\bm{x}_i-\bm{\mu})^T\]类内散度矩阵\[\bm{S}_w=\sum_{i=1}^{N}\bm{S}_{w_i}=\sum_{i=1}^{N}\sum_{\bm{x}\in X_i}^{}(\bm{x}-\bm{\mu}_i)(\bm{x}-\bm{\mu}_i)^T\]类间散度矩阵\[\bm{S}_b=\bm{S}_t-\bm{S}_w=\sum_{i=1}^{N}m_i(\bm{\mu}_i-\bm{\mu})(\bm{\mu}_i-\bm{\mu})^T\]常用实现的优化目标\[\max\limits_{\bm{W}}\frac{\mathrm{tr}(\bm{W}^T\bm{S}_b\bm{W})}{\mathrm{tr}(\bm{W}^T\bm{S}_w\bm{W})}\]可以通过广义特征值$\bm{S}_b\bm{W}=\lambda\bm{S}_w\bm{W}$求解，$\bm{W}$的闭式解为$\bm{S}_w^{-1}\bm{S}_b$的$d'$个最大非零广义特征值对应的特征向量组成的矩阵，有$d'\le N-1$，实现了降维。
					\end{itemize}
				\subsection{多分类学习}
					\begin{itemize}
						\item 基本思路：将多分类任务拆为若干个二分类任务求解，最经典的拆分策略有三种。
						\item 一对一（OvO）：将$N$个类别两两配对，产生$N(N-1)/2$个二分类任务。最终把预测得最多的类别作为分类结果。
						\item 一对其余（OvR）：每次将一个类的样例作为正例，所有其它类的样例作为反例，产生$N$个分类任务。最终若仅有一个分类器预测为正类，则对应的类别标记为最终分类结果，否则考虑各分类器的置信区间，选择置信度最大的类别标记作为分类结果。
						\item 多对多（MvM）：每次将若干个类作为正类，若干个其它类作为反类，可用纠错输出码（ECOC）技术。
						\item ECOC工作过程：\begin{enumerate}[(1)]
							\item 编码（类别划分）：对$N$个类别做$M$次划分，每次划分将一部分类别作为正类、一部分类别作为反类，产生$M$个分类器。
							\item 解码（距离比较）：用$M$个分类器对测试样本进行预测，这些预测标记组成一个编码，计算其与各个类别各自编码的距离，返回距离最小的类别作为分类结果。
						\end{enumerate}
						常用的编码矩阵为二元码和三元码（有停用类）。
						\item 任何两个类别之间的编码距离越远，纠错能力越强，而码长的增加会增大确定最优编码的难度。
					\end{itemize}
				\subsection{类别不平衡问题}
					\begin{itemize}
						\item 类别不平衡（class-imbalance）：分类任务中不同类别的训练样例数目差别很大。以下为类别不平衡学习的策略。
						\item 再缩放（rescaling）：假设``训练集是真实样本总体的无偏采样''，令\[\frac{y'}{1-y'}=\frac{y}{1-y}\times\frac{m^-}{m^+}\]也是代价敏感学习，其中的$m^-/m^+$可用$cost^+/cost^-$代替。
						\item 欠采样（undersampling）/下采样（downsampling）：去除一些正例（反例）使得正、反例数目接近。可用EasyEnsemble算法将反例划分为若干个集合供不同学习器使用，全局上不会丢失重要信息。
						\item 过采样（oversampling）/上采样（upsampling）：增加一些正例（反例）使得正、反例数目接近。可用SMOTE算法对训练集中的正例进行插值。
						\item 阈值移动（threshold-moving）：基于原始训练集学习，在用训练好的分类器进行预测时将``再缩放''中的式子嵌入到决策过程中。
					\end{itemize}
			\section{决策树}
				\subsection{基本流程}
					\begin{itemize}
						\item 决策树的性质：包含一个根结点、若干个内部结点、若干个叶结点，叶结点对应于决策结果，其他每个结点对应于一个属性测试，根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。
						\item 决策树的目的：产生一棵泛化能力强的决策树。
						\item 决策树的基本流程（分治策略）
						\begin{algorithm}
							\caption{TreeGenerate($D,A$)}
							\begin{algorithmic}[1]
								\REQUIRE 训练集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$;\\属性集$A=\{a_1,a_2,\dots,a_d\}$
								\ENSURE 以node为根结点的一棵决策树
								\STATE 生成结点node; \\
								\IF{$D$中样本全属于同一类别$C$}
								\STATE 将node标记为$C$类叶结点;\\
								\RETURN
								\ENDIF
								\IF{$A=\emptyset$ \OR $D$中样本在$A$上取值相同}
								\STATE 将node标记为叶结点，其类别标记为$D$中样本数最多的类;\\
								\RETURN
								\ENDIF
								\STATE 从$A$中选择最优划分属性$a_*$;\\
								\FOR{$a_*$的每一个值$a_*^v$}
								\STATE 为node生成一个分支;\\
								\STATE 令$D_v$表示$D$中在$a_*$上取值为$a_*^v$的样本子集;\\
								\IF{$D_v$为空}
								\STATE 将分支结点标记为叶结点，其类别标记为$D$中样本数最多的类;\\
								\RETURN
								\ELSE
								\STATE 以$\mathrm{TreeGenerate}(D_v,A\backslash\{a_*\})$为分支结点\\
								\ENDIF
								\ENDFOR
							\end{algorithmic} 
						\end{algorithm}
					\end{itemize}
				\subsection{划分选择}
					
					目的：使决策树的分支结点所包含的样本尽可能属于同一类别，结点的纯度越来越高。
					\subsubsection{信息增益}
						\begin{itemize}
							\item ID3决策树算法以信息增益为准则选择划分属性。
							\item 信息熵（设$D$中共有$\mathcal{Y}$类样本，第$k$类样本所占的比例为$p_k$，值越小则$D$的纯度越高）\[\mathrm{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k\]
							\item 设离散属性$a$的取值集合为$\{a^1,a^2,\dots,a_V\}$，用$a$对样本集合$D$进行划分，产生$V$个分支结点，第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$，于是信息增益（值越大则纯度提升越大）：\[\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\]
							\item 最终选择的属性\[a_*=\mathrm{arg}_{a\in A}\mathrm{max}\quad\mathrm{Gain}(D,a)\]
							\item 缺点：对可取值数目较多对属性有所偏好。
						\end{itemize}
					\subsubsection{增益率}
						\begin{itemize}
							\item C4.5决策树算法以增益率为准则选择划分属性。
							\item 增益率\[\mathrm{Gain_ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}\]其中$\mathrm{IV}(a)$为属性$a$的``固有值''，可能取值数目越多则通常越大。\[\mathrm{IV}(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}\]
							\item 缺点：对可取值数目较少的属性有所偏好，所以选择候选划分属性时使用了一个启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
						\end{itemize}
					\subsubsection{基尼指数}
						\begin{itemize}
							\item CART决策树算法以基尼指数（Gini index）为准则选择划分属性。
							\item 基尼值（度量数据集$D$的纯度），反映了从$D$中随机抽取两个样本，其类别标记不一致的概率，值越小则纯度越高。\[\mathrm{Gini}(D)=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k'\neq k}^{}p_kp_{k'}=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2\]
							\item 属性$a$的基尼指数\[\mathrm{Gini_index}(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Gini}(D^v)\]
							\item 最终选择属性\[a_*=\mathrm{arg}_{a\in A}\mathrm{min}\quad\mathrm{Gini\_index}(D,a)\]
						\end{itemize}
				\subsection{剪枝处理}
					\begin{itemize}
						\item 目的：去掉一些分支来降低过拟合的风险。
						\item 基本策略之``预剪枝''（prepruning）：在决策树生成过程中对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
						\item 基本策略之``后剪枝''（postpruning）：先从训练集生成一棵完整的决策树，然后自底向上对非叶结点考察，若将该结点的子树替换为叶结点能提升决策树的泛化性能，则将该子树替换为叶结点。
						\item 泛化性能评估方法用2.2节的性能评估方法即可，简单地，可以使用留出法并计算错误率（精度）。
					\end{itemize}
					\subsubsection{预剪枝}
						\begin{itemize}
							\item 降低了过拟合的风险。
							\item 显著减少决策树训练和测试时间开销。
							\item 可能因为本身的贪心禁止了那些后续划分使泛化性能显著提升的分支的展开，带来欠拟合的风险。
						\end{itemize}
					\subsubsection{后剪枝}
						\begin{itemize}
							\item 通常比预剪枝决策树保留了更多的分支。
							\item 欠拟合风险很小，泛化性能往往优于预剪枝决策树。
							\item 训练时间比未剪枝或预剪枝决策树大得多。
						\end{itemize}
				\subsection{连续与缺失值}
					\subsubsection{连续值处理}
						\begin{itemize}
							\item 思路：连续属性离散化。
							\item 最简单的策略：二分法（C4.5决策树算法中采用）。
							\item 二分法过程：给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将它们从小到大排序，记为$\{a^1,a^2,\dots,a^n\}$，基于划分点$t$划分为子集$D_t^-$和$D_t^+$，前者包含在属性$a$上不大于$t$的样本。我们把每个区间$[a^i,a^{i+1})$的中位点$\frac{a^i+a^{i+1}}{2}$作为候选划分点。
							\item 改造后的信息增益\[\mathrm{Gain}(D,a)=\max\limits_{t\in T_a}\mathrm{Gain}(D,a,t)=\max\limits_{t\in T_a}\big(\mathrm{Ent}(D)-\sum_{\lambda\in\{-,+\}}^{}\frac{|D_t^\lambda|}{|D|}\mathrm{Ent}(D_t^\lambda)\big)\]
							\item 与离散属性的区别：若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性。
						\end{itemize}
					\subsubsection{缺失值处理}
						\begin{itemize}
							\item 策略：利用某个属性$a$上无缺失值样本的信息增益扩放到所有样本的信息增益。（C4.5决策树算法中采用）
							\item 划分属性的选择过程：$\tilde{D}$表示$D$中在属性$a$上没有缺失值的样本子集；$\tilde{D}^v$表示$\tilde{D}$中在属性$a$上取值为$a^v$的样本子集（$1\le v\le V$）；$\tilde{D}_k$表示$\tilde{D}$中属于第$k$类的样本子集（$1\le k\le|\mathcal{Y}$）。为每个样本$\bm{x}$赋予一个权重$w_{\bm{x}}$\begin{align*}
								& \textrm{无缺失值样本的比例：} & \rho=\frac{\sum_{\bm{x}\in\tilde{D}}^{}w_{\bm{x}}}{\sum_{\bm{x}\in D}^{}w_{\bm{x}}}\\
								& \textrm{无缺失值样本中第$k$类的比例：} & \tilde{p}_k=\frac{\sum_{\bm{x}\in\tilde{D}_k}^{}w_{\bm{x}}}{\sum_{\bm{x}\in\tilde{D}}^{}w_{\bm{x}}}\\
								& \textrm{无缺失值样本中在属性$a$上取值为$a^v$的样本的比例：} & \tilde{r}_v=\frac{\sum_{\bm{x}\in\tilde{D^v}}^{}w_{\bm{x}}}{\sum_{\bm{x}\in\tilde{D}}w_{\bm{x}}}
							\end{align*}
							信息增益的推广式\[\mathrm{Gain}(D,a)=\rho\times\mathrm{Gain}(\tilde{D},a)=\rho\times\big(\mathrm{Ent}(\tilde{D})-\sum_{v=1}^{V}\tilde{r}_v\mathrm{Ent}(\tilde{D}^v)\big)\]\[\mathrm{Ent}(\tilde{D})=-\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_k\log_2\tilde{p}_k\]
							\item 已经划分属性进行样本划分的过程：\begin{itemize}
								\item 若样本$\bm{x}$在$a$上的取值已知，则将其划入与其取值对应的子结点，样本权值在子结点中保持为$w_{\bm{x}}$
								\item 若样本$\bm{x}$在$a$上的取值未知，则将其划入所有子结点，样本权值在与属性值$a^v$对应的子结点中调整为$\tilde{r}_v\cdot w_{\bm{x}}$。
							\end{itemize}
						\end{itemize}
				\subsection{多变量决策树}
					\begin{itemize}
						\item 决策树所形成的分类边界的特点：轴平行。每一段划分都直接对应某个属性取值。当真实分类边界比较复杂时决策树也会相当复杂。
						\item 多变量决策树：非叶结点是一个形如$\sum_{i=1}^{d}w_ia_i=t$的线性分类器。在学习过程中试图建立一个合适的线性分类器。实现了斜划分。
					\end{itemize}
			\section{神经网络}
				\subsection{神经元模型}
					\begin{itemize}
						\item 神经网络的定义：神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体作出对交互反应。
						\item 最基本的成分：神经元模型
						\item M-P神经元模型：神经元接收到来自$n$个其他神经元的输入信号$x_i$，它们各通过带权重$w_i$的连接进行传递，神经元将总输入值$\sum_{i=1}^{n}w_ix_i$与神经元的阈值$\theta$进行比较，得到$\sum_{i=1}^{n}w_ix_i-\theta$，然后通过``激活函数''$f$处理以产生神经元的输出：\[y=f\big(\sum_{i=1}^{n}w_ix_i-\theta\big)\]
						\item 激活函数的模型\begin{itemize}
							\item 阶跃函数（不连续、不光滑）：\[\mathrm{sgn}(x)=\left\{\begin{aligned}
							1, \quad& x\ge0;\\
							0, \quad& x < 0
							\end{aligned}\right.\]
							\item Sigmoid函数（将可能在较大范围内变化的输入值挤压到$(0,1)$输出值范围内）：\[\mathrm{sigmoid}(x)=\frac{1}{1+e^{-x}}\]
						\end{itemize}
					\end{itemize}
				\subsection{感知机与多层网络}
					\begin{enumerate}[1.]
						\item 感知机（Perceptron）：两层神经元，输入层接受外界输入信号后传递给输出层，输出层是M-P神经元，也称为``阈值逻辑单元''\begin{itemize}
							\item 感知机实现逻辑``与''：$w_1=w_2=1,\theta=0$；逻辑``或''：$w_1=w_2=1,\theta=0.5$；逻辑``非''：$w_1=-0.6,w_2=0,\theta=-0.5$。
							\item 将阈值看作固定输入为-1.0的``哑结点''所对应的权重$w_{n+1}$。统一为权重的学习。对训练样例$(\bm{x},y)$，若当前感知机的输出为$\hat{y}$，则其权重调整如下：\[w_i\leftarrow w_i + \Delta w_i\quad\quad\Delta w_i=\eta(y-\hat{y})x_i\]其中$\eta$为$(0,1)$内的小正数，称为学习率。
							\item 感知机只能求解线性可分问题（存在一个线性超平面区分两类模式），对于非线性可分问题会发生振荡（fluctuation）。
						\end{itemize}
						\item 多层前馈神经网络：每层神经元与下一层全互连，不存在同层连接和跨层连接。输入层神经元仅接收输入，隐层与输出层包含功能神经元。
						\item 神经网络的学习过程：根据训练数据来调整神经元之间的连接权以及每个功能神经元的阈值。
					\end{enumerate}
				\subsection{误差逆传播算法}
					\includegraphics[width=\linewidth]{BP}
					\begin{itemize}
						\item 任意参数$v$的更新估计式：$v\leftarrow v+\Delta v$
						\item 目标：最小化训练集$D$上的累积误差\[E=\frac{1}{m}\sum_{k=1}^{m}E_k\]\[E_k=\frac{1}{2}\sum_{j=1}^{l}(\hat{y}_j^k-y_j^k)^2\]
						\item 参数调整原则：梯度下降。例如$\Delta w_{hj}=-\eta\frac{\partial E_k}{\partial w_{hj}}$
						\item 推导方法：参数影响的逐级传递，例如\[\frac{\partial E_k}{\partial w_{hj}}=\frac{\partial E_k}{\partial\hat{y}_j^k}\cdot\frac{\partial\hat{y}_j^k}{\partial\beta_j}\cdot\frac{\partial\beta_j}{\partial w_{hj}}\]Sigmoid函数的性质：$f'(x)=f(x)(1-f(x))$
						\item 各个参数的调整值：\[\Delta w_{hj}=\eta g_jb_h\]\[\Delta\theta_j=-\eta g_j\]\[\Delta v_{ih}=\eta e_hx_i\]\[\Delta\gamma_h=-\eta e_h\]其中\[g_j=\hat{y}_j^k(1-\hat{y}_j^k)(y_j^k-\hat{y}_j^k)\]\[e_h=b_h(1-b_h)\sum_{j=1}^{l}w_{hj}g_j\]
						\item BP算法执行过程：\begin{enumerate}[1.]
							\item 输入：训练集$D=\{(\bm{x}_k,\bm{y}_k)\}_{k=1}^m$和学习率$\eta$
							\item 在$(0,1)$范围内随机初始化网络中所有连接权和阈值
							\item 重复计算$\hat{\bm{y}_k},g_j,e_h$并更新四个参数直到达到停止条件（如训练误差已达到一个很小的值）
							\item 输出：连接权与阈值确定的多层前馈神经网络
						\end{enumerate}
						\item 累积误差逆传播（ABP）算法：省去BP算法对每个样例都更新参数都步骤，而是读取整个训练集一遍后才更新参数，直接针对累积误差最小化。
						\item 缓解过拟合的策略\begin{itemize}
							\item 早停：将数据分成训练集和验证集，若训练集误差降低而验证集误差升高，则停止训练。
							\item 正则化：在误差目标函数中增加一个用于描述网络复杂度的部分。令$\lambda\in(0,1)$，如\[E=\lambda\frac{1}{m}\sum_{k=1}^{m}E_k+(1-\lambda)\sum_{i}^{}w_i^2\]
						\end{itemize}
					\end{itemize}
				\subsection{全局最小与局部极小}
					\begin{itemize}
						\item 神经网络训练过程：在参数空间中寻找一组最优参数使得$E$最小。
						\item 局部极小：对$\bm{w}^*$和$\theta^*$，若存在$\epsilon>0$使得\[\forall(\bm{w};\theta)\in\{(\bm{w};\theta)|\parallel(\bm{w};\theta)-(\bm{w}^*;\theta^*)\parallel\le\epsilon\}\]都有$E(\bm{w};\theta)\ge E(\bm{w}^*;\theta^*)$，则$(\bm{w}^*;\theta^*)$为局部极小解。
						\item 全局最小：对参数空间中任意$(\bm{w};\theta)$都有$E(\bm{w};\theta)\ge E(\bm{w}^*;\theta^*)$，则$(\bm{w}^*;\theta^*)$为全局最小解。
						\item 使用最为广泛的参数寻优方法：梯度下降法（容易找到局部极小）。
						\item 跳出局部极小，进一步接近全局最小的策略：\begin{itemize}
							\item 以多组不同参数值初始化多个神经网络（从多个不同的初始点开始搜索）；
							\item 使用``模拟退火''技术：每一步有一定概率接受比当前解更差的结果，且接受次优解概率随时间推移而逐渐降低；
							\item 使用随机梯度下降（即使陷入局部极小点，计算出来的梯度可能不为零）；
							\item 遗传算法等其它启发式算法。
						\end{itemize}
					\end{itemize}
				\subsection{其他常见神经网络}
					\subsubsection{RBF网络}
						\begin{itemize}
							\item RBF网络（径向基网络）：一种单隐层前馈神经网络。
							\item 隐层激活函数：径向基函数；输出层是对隐层输出的线性组合。
							\item 设$q$为隐层神经元个数，$\bm{c}_i$和$w_i$是第$i$个隐层神经元所对应的中心和权重。径向基函数$\bm{\rho}(\bm{x},\bm{c}_i)$通常定义为样本$\bm{x}$到数据中心$\bm{c}_i$之间欧氏距离的单调函数。常用的高斯径向基函数\[\rho(\bm{x},\bm{c}_i)=e^{-\beta_i\parallel\bm{x}-\bm{c}_i\parallel^2}\]
							\item 训练过程：通过随机采样、聚类等方法确定神经元中心$\bm{c}_i$$\rightarrow$利用BP算法确定参数$w_i$和$\beta_i$
						\end{itemize}
					\subsubsection{ART网络}
						\begin{itemize}
							\item ART网络（自适应谐振网络）：一种竞争学习型无监督神经网络。
							\item 构成：比较层（接收输入样本，传递给识别层）、识别层（每个神经元对应一个模式类，数目也在训练过程中动态增长）、识别阈值、重置模块。
							\item 接收比较层的输入$\rightarrow$识别层神经元相互竞争（向量距离）$\rightarrow$获胜神经元抑制其他识别层神经元的激活$\rightarrow$输入向量与获胜神经元的代表向量相似度大于识别阈值? 则当前输入样本被归为该代表向量所属类别并更新连接权 : 重置模块在识别层增设新神经元，代表向量即为当前输入向量。
							\item 识别阈值高$\rightarrow$输入样本分类数目多且精细；识别阈值低$\rightarrow$输入样本分类数目少且粗略。
							\item 缓解了``可塑性-稳定性窘境''，可进行增量学习或在线学习。
						\end{itemize}
					\subsubsection{SOM网络}
						\begin{itemize}
							\item SOM网络（自组织映射网络）：一种竞争学习型无监督神经网络。
							\item 特点：将高维输入数据映射到低维空间，同时保持输入数据在高维空间的拓扑结构。获胜神经元决定了输入向量在低维中的位置。
							\item 目标：为每个输出层神经元找到合适的权向量，达到拓扑结构的保持。
							\item 训练过程：接收一个训练样本$\rightarrow$每个输出层神经元计算其与自身权向量的距离$\rightarrow$距离最近者获胜（最佳匹配单元）$\rightarrow$最佳匹配单元及其邻近神经元的权向量被调整使得它们与当前输入样本的距离缩小$\rightarrow$不断迭代直到收敛
						\end{itemize}
					\subsubsection{级联相关网络}
						\begin{itemize}
							\item 自适应网络的代表：网络结构也是学习目标之一。
							\item 级联：建立层次连接的层级结构。从仅有输入输出层增加新的隐层神经元。
							\item 相关：通过最大化新神经元的输出与网络误差之间的相关性来训练相关的参数。
							\item 特点：无需设置网络层数、隐层神经元数目，训练速度快，数据较小时易陷入过拟合。
						\end{itemize}
					\subsubsection{Elman网络}
						\begin{itemize}
							\item 最常用的递归神经网络（RNN）之一：可出现环形，有信息反馈，网络在$t$时刻的输出状态与$t$时刻的输入及$t-1$时刻的网络状态都有关。
							\item 结构与多层前馈网络相似，隐层神经元的输出反馈给所有隐层神经元。
							\item 隐层神经元常采用Sigmoid激活函数，网格训练常用推广的BP算法。
						\end{itemize}
					\subsubsection{Bolzmann机}
						\begin{itemize}
							\item 定义了``能量''，能量最小化时网络达理想状态。
							\item 神经元全部为布尔型，神经元两两全连接。设状态向量$\bm{s}\in\{0,1\}^n$表示$n$个神经元的状态。则$\bm{s}$对应的Boltzmann机能量为\[E(\bm{s})=-\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}s_is_j-\sum_{i=1}^{n}\theta_is_i\]
							\item 若神经元以任意不依赖于输入值顺序进行更新，网络最终达到Boltzmann分布（平衡态），此时状态向量$\bm{s}$出现的概率\[P(\bm{s})=\frac{e^{-E(\bm{s})}}{\sum_{\bm{t}}^{}e^{-E(\bm{t})}}\]
							\item 训练过程：将每个训练样本视为一个训练向量，使其出现的概率尽可能大。常用受限Boltzmann机（仅保留显层与隐层的连接）。
							\item 受限Boltzmann机的训练方法：对比散度算法。设显、隐层神经元个数分别为$d,q$，状态向量分别为$\bm{v},\bm{h}$\[P(\bm{v}|\bm{h})=\prod_{i=1}^{d}P(v_i|\bm{h})\quad P(\bm{h}|\bm{v})=\prod_{j=1}^{q}P(h_j|\bm{v})\]
							\item 受限Bolzmann的工作过程：对每个训练样本$\bm{v}$，先计算$P(\bm{h}|\bm{v})$，然后分布采样得到$\bm{h}$，再计算$P(\bm{v}'|\bm{h})$，从$\bm{v}'$产生$\bm{h}$。连接权的更新公式为\[\Delta w=\eta(\bm{v}\bm{h}^T-\bm{v}'\bm{h}^{'T})\]
						\end{itemize}
				\subsection{深度学习}
					\begin{itemize}
						\item 典型的深度学习模型：多隐层神经网络
						\item 多隐层网络训练的手段：无监督逐层训练（预训练+微调）。将大量参数分组，对每组找到局部较优，联系起来进行全局寻优，节省训练开销。
						\item 卷积神经网络（CNN）：待本书主要内容学完后，对于CNN方面将着重学习：\href{https://cs231n.github.io}{CS231n Convolutional Neural Networks for Visual Recognition}
					\end{itemize}
			\section{支持向量机}
				\subsection{间隔与支持向量}
					\begin{itemize}
						\item 划分超平面：\[\bm{w}^{\mathrm{T}}\bm{x}+b=0\]其中$\bm{w}=(w_1;w_2;\dots;w_d)$为法向量，决定方向；$b$为位移项，决定超平面与原点之间的距离。
						\item 样本空间中任意点$\bm{x}$到超平面$(\bm{x},b)$的距离\[r=\frac{|\bm{w}^{\mathrm{T}}+b|}{\parallel\bm{w}\parallel}\]
						\item 若超平面$(\bm{w},b)$能将训练样本正确分类，则对于任意$(\bm{x}_i,y_i)\in D$有\[\left\{\begin{aligned}
							\bm{w}^{\mathrm{T}}\bm{x}_i+b\ge+1, & \quad y_i=+1;\\
							\bm{w}^{\mathrm{T}}\bm{x}_i+b\le-1, & \quad y_i=-1.
							\end{aligned}\right.\]
						\item 支持向量：满足$\bm{w}^{\mathrm{T}}\bm{x}_i+b=\pm1,y_i=\pm1$的距离超平面最近的几个训练样本点。
						\item 间隔：两个异类支持向量到超平面的距离之和：\[\gamma=\frac{2}{\parallel\bm{w}\parallel}\]
						\item 支持向量机（SVM）的基本型：最大化间隔，即最小化$\parallel\bm{w}\parallel^2$\begin{align*}
							& \min\limits_{\bm{w},b}\quad\frac{1}{2}\parallel\bm{w}\parallel^2\\
							& \mathrm{s.t.}\quad y_i(\bm{w}^{\mathrm{T}}\bm{x}_i+b)\ge1, i=1,2,\dots,m.
						\end{align*}
					\end{itemize}
				\subsection{对偶问题}
					
					求解6.1节基本型的一个高效方法：\begin{enumerate}[1.]
						\item 用拉格朗日乘子法得到对偶问题，即对基本型对每条约束添加拉格朗日乘子$a_i\ge0$，得到\[L(\bm{w},b,\bm{\alpha})=\frac{1}{2}\parallel\bm{w}\parallel^2+\sum_{i=1}^{m}\alpha_i(1-y_i(\bm{w}^T\bm{x}_i+b))\]分别令对$\bm{w}$和$b$的偏导数为零再代入消去$\bm{w},b$可得到对偶问题如下：\begin{align*}
							& \max\limits_{\bm{\alpha}}\quad\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\bm{x}^{\mathrm{T}}\bm{x}_j\\
							& \mathrm{s.t.}\quad\sum_{i=1}^{m}\alpha_iy_i=0\\
							& \alpha_i\ge0,\quad i=1,2,\dots,m.
						\end{align*}
						这样在解出$\bm{\alpha}$后，求出$\bm{w}$和$b$就可以得到模型$f(\bm{x})=\sum_{i=1}^{m}\alpha_iy_i\bm{x}_i^{\mathrm{T}}\bm{x}+b$
						\item 上述过程需满足KKT条件，即要求\[\left\{\begin{aligned}
							\alpha_i\ge0;\\
							y_if(\bm{x}_i)-1\ge0;\\
							\alpha_i(y_if(\bm{x}_i)-1)=0.
						\end{aligned}\right.\]\begin{framed}
							$\triangle$ KKT条件对于上述结论的具体分析过程： 对于不等式约束$g(\bm{x}_i)=1-y_i(\bm{w}^{\mathrm{T}}\bm{x}_i+b)=1-y_if(\bm{x}_i)\le0$，对于$g(\bm{x}_i)<0$的情形，可通过$\nabla f(\bm{x}_i)=0$来获得最优点，等价于在$L(\bm{w},b,\alpha_i)$中对$\alpha_i$置零然后对$\nabla_{\bm{w},b}L(\bm{x}_i,\alpha_i)$置零；对于$g(\bm{x}_i)=0$的情形，类似于拉格朗日乘子法中等式约束的分析，但此时$\nabla f(\bm{x}_i^*)$的方向必与$\nabla g(\bm{x}_i^*)$相反。综上有$\alpha_i g(\bm{x}_i)=0$。由此可转化为在如下约束下最小化拉格朗日函数的问题：\[\left\{\begin{aligned}
							1-y_if(\bm{x}_i)\le0;\\
							\alpha_i\ge0;\\
							\alpha_i(1-y_if(\bm{x}_i))=0.
							\end{aligned}\right.\]
						\end{framed}
						由此可以总结：若$\alpha_i=0$，则该样本不会出现在求和中，没有影响；若$y_if(\bm{x}_i)=1$，则对应的样本点在最大间隔边界上，是支持向量。因此\underline{在支持向量机训练完成后，最终模型仅与支持向量有关。}
						\item 求解第一步最后的对偶问题的方法：二次规划算法（问题规模正比于训练样本数，开销太大）；SMO算法。SMO不断执行以下两个步骤直至收敛：\begin{itemize}
							\item 选取一对需更新的变量$\alpha_i$和$\alpha_j$；
							\item 固定$\alpha_i$和$\alpha_j$以外的参数，求解对偶模型中获得更新后的$\alpha_i$和$\alpha_j$。
						\end{itemize}
						选择参数的启发式方法：\underline{使选取的两变量所对应样本之间的间隔最大}。（对它们进行更新一般会带给目标函数值更大的变化）仅考虑$\alpha_i,\alpha_j$时，因为有\[\alpha_iy_i+\alpha_jy_j=-\sum_{k\neq i,j}^{}\alpha_ky_k,\quad \alpha_i\ge0,\alpha_j\ge0\]可以消去$\alpha_j$得到单变量二次规划问题，仅有的约束是$\alpha_i\ge0$。
						\item 确定偏移项$b$的方法：对于所有支持向量$(\bm{x}_s,y_s),s\in S$都有$y_sf(\bm{x}_s)=1$即\[y_s\bigg(\sum_{i\in S}^{}\alpha_iy_i\bm{x}_i^{\mathrm{T}}\bm{x}_s+b\bigg)=1\]现实任务中一般使用所有支持向量求解的平均值：\[b=\frac{1}{|S|}\sum_{s\in S}^{}\bigg(1/y_s-\sum_{i\in S}^{}\alpha_iy_i\bm{x}_i^{\mathrm{T}}\bm{x}_S\bigg)\]
					\end{enumerate}
				\subsection{核函数}
					\begin{itemize}
						\item 在现实任务中，原始样本空间可能不存在一个能正确划分两类样本的超平面，此时可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。若原始空间是有限维，则必定存在这样一个高维特征空间。
						\item 设$\phi(\bm{x})$表示将$\bm{x}$映射后的特征向量。于是在特征空间中划分超平面所对应的模型可表示为$f(\bm{x})=\bm{w}^{\mathrm{T}}\phi(\bm{x})+b$。此时对偶问题约束条件不变，目标变为\[\max\limits_{\bm{\alpha}}\quad\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(\bm{x}_i)^{\mathrm{T}}\phi(\bm{x}_j)\]直接在高维空间计算$\phi(\bm{x}_i)^{\mathrm{T}}\phi(\bm{x}_j)$很难，因此定义``核函数''：\[\kappa(\bm{x}_i,\bm{x}_j)=\langle\phi(\bm{x}_i),\phi(\bm{x}_j)\rangle=\phi(\bm{x}_i)^{\mathrm{T}}\phi(\bm{x}_j)\]由此``支持向量展式''为：\[f(\bm{x})=\bm{w}^{\mathrm{T}}\phi(\bm{x})+b=\sum_{i=1}^{m}\alpha_iy_i\phi(\bm{x}_i)^{\mathrm{T}}\phi(\bm{x})+b=\sum_{i=1}^{m}\alpha_iy_i\kappa(\bm{x},\bm{x}_i)+b\]
						\item 核函数的定理如下：\begin{theorem}
							令$\mathcal{X}$为输入空间，$\kappa(\cdot,\cdot)$是定义在$\mathcal{X}\times\mathcal{X}$上的对称函数，则$\kappa$是核函数当且仅当对于任意数据$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$，``核矩阵''$\mathbf{K}$总是半定的。其中\[\mathbf{K}=\left[\begin{matrix}
							\kappa(\bm{x}_1,\bm{x}_2) & \cdots & \kappa(\bm{x},\bm{x}_j) & \cdots & \kappa(\bm{x},\bm{x}_m) \\
							\vdots & \ddots & \vdots & \ddots & \vdots \\
							\kappa(\bm{x}_i,\bm{x}_1) & \cdots & \kappa(\bm{x}_i,\bm{x}_j) & \cdots & \kappa(\bm{x}_i,\bm{x}_m) \\
							\vdots & \ddots & \vdots & \ddots & \vdots \\
							\kappa(\bm{x}_m, \bm{x}_1) & \cdots & \kappa(\bm{x}_m,\bm{x}_j) & \cdots & \kappa(\bm{x}_m,\bm{x}_m)
							\end{matrix}\right]\]
						\end{theorem}
						任何一个核函数都隐式地定义了一个``再生核希尔伯特空间''。\begin{framed}
							$\triangle$ 半正定矩阵的定义\begin{itemize}
								\item 广义：设$\bm{A}$是$n$阶方阵，如果对任何非零向量$\bm{X}$，都有$\bm{X}^{\mathrm{T}}\bm{A}\bm{X}\ge0$，则称$A$为半正定矩阵。
								\item 狭义（常用）：设$\bm{A}$为实对称矩阵，若对于每个非零实向量$\bm{X}$，都有$\bm{X}^{\mathrm{T}}\bm{A}\bm{X}\ge0$，则称$\bm{A}$为半正定矩阵，称$\bm{X}^{\mathrm{T}}\bm{AX}$为半正定二次型。
							\end{itemize}
							$\triangle$ 再生核希尔伯特空间等空间的概念可见文章：\href{http://users.umiacs.umd.edu/~hal/docs/daume04rkhs.pdf}{From Zero to Reproducing Kernel Hilbert Spaces in Twelve Pages or Less}。这玩意有点硬核OTZ
						\end{framed}
						\item 支持向量机的最大变数：核函数选择。可以使用常用的核函数并通过函数组合得到。\begin{center}
							\begin{tabular}{lll}
								\hline
								名称 & 表达式 & 参数\\ \hline
								线性核 & $\kappa(\bm{x}_i,\bm{x}_j)=\bm{x}_i^{\mathrm{T}}\bm{x}_j$ & \\
								多项式核 & $\kappa(\bm{x}_i,\bm{x}_j)=(\bm{x}_i^{\mathrm{T}}\bm{x}_j)^d$ & $d\ge1$为多项式的次数 \\
								高斯核 & $\kappa(\bm{x}_i,\bm{x}_j)=\mathrm{exp}(-\frac{\parallel \bm{x}_i-\bm{x}_j\parallel^2}{2\sigma^2})$ & $\sigma>0$为高斯核的带宽 \\
								拉普拉斯核 & $\kappa(\bm{x}_i,\bm{x}_j)=\mathrm{exp}(-\frac{\parallel\bm{x}_i-\bm{x}_j\parallel}{\sigma})$ & $\sigma>0$ \\
								Sigmoid核 & $\kappa(\bm{x}_i,\bm{x}_j)=\mathrm{tanh}(\beta\bm{x}_i^{\mathrm{T}}\bm{x}_j+\theta)$ & tanh为双曲正切函数，$\beta>0,\theta<0$ \\ \hline
							\end{tabular}
						\end{center}
						若$\kappa_1,\kappa_2$为核函数，则线性组合（任意正数$\gamma_1,\gamma_2$）$\gamma_1\kappa_1+\gamma_2\kappa_2$、直积$\kappa_1\otimes\kappa_2(\bm{x},\bm{z})=\kappa_1(\bm{x},\bm{z})\kappa_2(\bm{x},\bm{z})$也是核函数。对于任意函数$g(x)$，$\kappa(\bm{x},\bm{z})=g(\bm{x})\kappa_1(\bm{x},\bm{z})g(\bm{z})$也是核函数。
					\end{itemize}
				\subsection{软间隔与正则化}
					\begin{itemize}
						\item 在现实任务中很难确定合适的核函数$\rightarrow$允许支持向量机在一些样本上出错$\rightarrow$加入``软间隔''概念（区别于``硬间隔''）$\leftrightarrow$允许某些样本不满足约束$y_i(\bm{w}^{\mathrm{T}}\bm{x}_i+b)\ge1$
						\item 优化目标可改为\[\min\limits_{\bm{w},b}\quad\frac{1}{2}\parallel\bm{w}\parallel^2+C\sum_{i=1}^{m}\ell\big(y_i(\bm{w}^{\mathrm{T}}\bm{x}_i+b)-1\big)\]其中$C>0$为常数，$\ell$是损失函数，一般为``0/1损失函数''（负则输出1，否则输出0），也可以是替代损失函数，如\begin{itemize}
							\item hinge损失：$\ell_{hinge}(z)=\max(0, 1-z)$；
							\item 指数损失：$\ell_{exp}(z)=\exp(-z)$；
							\item 对率损失：$\ell_{log}(z)=\log(1+\exp(-z)).$
						\end{itemize}
						后续分析以hinge损失为例。
						\item 引入松弛变量$\xi_i\ge0$，则得到``软间隔支持向量机''：\begin{align*}
							& \min\limits_{\bm{w},b,\xi_i}\quad\frac{1}{2}\parallel\bm{w}\parallel^2+C\sum_{i=1}^{m}\xi_i \\
							& \mathrm{s.t.}\quad y_i(\bm{w}^{\mathrm{T}}+b)\ge1-\xi_i\\
							& \xi_i\ge0,i=1,2,\dots,m.
						\end{align*}
						仿照6.2节的步骤，先用拉格朗日乘子法得到拉格朗日函数（拉格朗日乘子为$\alpha_i\ge0,\mu_i\ge0$）：\[L(\bm{w},b,\bm{\alpha},\bm{\xi},\bm{\mu})=\frac{1}{2}\parallel\bm{w}\parallel^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(\bm{w}^{\mathrm{T}}\bm{x}_i+b))-\sum_{i=1}^{m}\mu_i\xi_i\]分别对$\bm{w},b,\xi_i$偏导令为零可得$\bm{w}=\sum_{i=1}^{m}\alpha_iy_i\bm{x}_i$、$0=\sum_{i=1}^{m}\alpha_iy_i$、$C=\alpha_i+\mu_i$。代入得到对偶问题\begin{align*}
							& \max\limits_{\bm{\alpha}}\quad\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\bm{x}_i^{\mathrm{T}}\bm{x}_j\\
							& \mathrm{s.t.}\quad\sum_{i=1}^{m}\alpha_iy_i=0\\
							& 0\le\alpha_i\le C,i=1,2,\dots,m.
						\end{align*}
						对此KKT条件要求：\[\left\{\begin{aligned}
						\alpha_i\ge0, \quad \mu_i\ge0,\\
						y_if(\bm{x}_i)-1+\xi_i\ge0,\\
						\alpha_i(y_if(\bm{x}_i)-1+\xi_i)=0,\\
						\xi_i\ge0,\quad \mu_i\xi_i=0
						\end{aligned}\right.\]若$\alpha_i=0$则该样本无影响，若$\alpha_i>0$则有$y_if(\bm{x}_i)=1-\xi_i$，该样本是支持向量。若$\alpha_i<C$，则$\mu_i>0$，故$\xi_i=0$，该样本位于最大间隔边界上。若$\alpha_i=C$则有$\mu_i=0$，此时若$\xi_i\le1$则该样本落在最大间隔内部，否则该样本被错误分类。软间隔支持向量机的最终模型仍然仅与支持向量有关。
						\item 共性：优化目标中，第一项用来描述划分超平面的间隔大小，另一项用于表述训练集上的误差。一般形式为\[\min\limits_{f}\Omega(f)+C\sum_{i=1}^{m}\ell(f(\bm{x}_i),y_i)\]其中\begin{itemize}
							\item 该形式可称为``正则化''问题。
							\item $\Omega(f)$：结构风险。描述模型$f$的某些性质，为引入领域知识和用户意图提供途径，并且可以削减假设空间，降低过拟合风险。它也被称为正则化项。
							\item $\sum_{i=1}^{m}\ell(f(\bm{x}_i),y_i)$：经验风险。描述模型与训练数据的契合程度。
							\item $C$：用于对二者进行折中。被称为正则化常数。
						\end{itemize}
					\end{itemize}
				\subsection{支持向量回归}
					\begin{itemize}
						\item 对于回归问题，支持向量回归（SVR）假设能够容忍$f(\bm{x})$与$y$之间最多有$\epsilon$的偏差，即差值大于$\epsilon$时才计算损失$\rightarrow$以$f(\bm{x})$为中心，构建一个宽度为$2\epsilon$的间隔带。落入此带的训练样本被认为是预测正确。
						\item SVR问题的目标：\[\min\limits_{\bm{w},b}\quad\frac{1}{2}\parallel\bm{w}\parallel^2+C\sum_{i=1}^{m}\ell_\epsilon(f(\bm{x}_i)-y_i)\]其中$C$为正则化常数，$\ell_\epsilon$是$\epsilon$-不敏感损失函数：\[\ell_\epsilon(z)=\left\{\begin{aligned}
						&0, & \mathrm{if}\quad|z|\le\epsilon,\\
						&|z|-\epsilon, & \mathrm{otherwise.}
						\end{aligned}\right.\]
						\item 求解过程：引入两个松弛变量$\rightarrow$引入四个拉格朗日乘子$\rightarrow$得到对偶问题$\rightarrow$加入KKT条件$\rightarrow$表出SVR解的形式、$\bm{w}$、$b$
					\end{itemize}
				\subsection{核方法}
					\begin{itemize}
						\item 不论是SVM还是SVR，学得的模型总能表示成核函数$\kappa(\bm{x},\bm{x}_i)$的线性组合。
						\item ``表示定理''：\begin{theorem}
							令$\mathbb{H}$为核函数$\kappa$对应的再生核希尔伯特空间，$\parallel h\parallel_{\mathbb{H}}$表示$\mathbb{H}$空间中关于$h$的范数，对于任意单调递增函数$\Omega:[0,\infty]\mapsto\mathbb{R}$和任意非负损失函数$\ell:\mathbb{R}^m\mapsto[0,\infty]$，优化问题\[\min\limits_{h\in\mathbb{H}}\quad F(h)=\Omega(\parallel h\parallel_{\mathbb{H}})+\ell\big(h(\bm{x}_1),h(\bm{x}_2),\dots,h(\bm{x}_m)\big)\]的解总可写为\[h^*(\bm{x})=\sum_{i=1}^{m}\alpha_i\kappa(\bm{x},\bm{x}_i)\]
						\end{theorem}
					\item 利用核方法将线性学习器拓展为非线性学习器。以线性判别分析拓展为核线性判别分析（KLDA）为例：\begin{enumerate}
						\item 假设可通过某种映射$\phi:\mathcal{X}\mapsto\mathbb{F}$将样本映射到一个特征空间$\mathbb{F}$，然后在$\mathbb{F}$中执行线性判别分析，以求得\[h(\bm{x})=\bm{w}^{\mathrm{T}}\phi(\bm{x})\]
						\item KLDA学习目标为\[\max\limits_{\bm{w}}J(\bm{w})=\frac{\bm{w}^{\mathrm{T}}\bm{S}_b^\phi\bm{w}}{\bm{w}^{\mathrm{T}}\bm{S}_w^\phi\bm{w}}\]设$i\in\{0,1\}$，均值及两个散度矩阵分别为\[\bm{\mu}_i^\phi=\frac{1}{m_i}\sum_{\bm{x}\in X_i}^{}\phi(\bm{x})\]\[\bm{S}_b^\phi=(\bm{\mu}_1^\phi-\bm{\mu}_0^\phi)(\bm{\mu}_1^\phi-\bm{\mu}_0^\phi)^{\mathrm{T}}\]\[\bm{S}_w^\phi=\sum_{i=0}^{1}\sum_{\bm{x}\in X_i}^{}(\phi(\bm{x})-\bm{\mu}_i^\phi)(\phi(\bm{x})-\bm{\mu}_i^\phi)^{\mathrm{T}}\]
						\item 此时用核函数$\kappa(\bm{x},\bm{x}_i)=\phi(\bm{x}_i)^{\mathrm{T}}\phi(\bm{x})$来隐式地表达映射$\phi$和特征空间$\mathbb{F}$。对于表示定理中的优化问题，把$J(\bm{w})$作为损失函数$\ell$，令$\Omega\equiv0$，由此函数$h(\bm{x})$可写为\[h(\bm{x})=\sum_{i=1}^{m}\alpha_i\kappa(\bm{x},\bm{x}_i)\]结合步骤1中的式子，可推出\[\bm{w}=\sum_{i=1}^{m}\alpha_i\phi(\bm{x}_i)\]
						\item 令$\mathbf{K}$为核函数$\kappa$所对应的核矩阵。令$\bm{1}_i\in\{1,0\}^{m\times1}$为第$i$类样本的指示向量。\[\hat{\bm{\mu}}_0=\frac{1}{m_0}\mathbf{K1}_0\qquad\hat{\bm{\mu}}_1=\frac{1}{m_1}\mathbf{K1}_1\]\[\mathbf{M}=(\hat{\bm{\mu}}_0-\hat{\bm{\mu}}_1)(\hat{\bm{\mu}}_0-\hat{\bm{\mu}}_1)^{\mathrm{T}}\]\[\mathbf{N}=\mathbf{KK}^{\mathrm{T}}-\sum_{i=0}^{1}m_i\hat{\bm{\mu}}_i\hat{\bm{\mu}}_i^{\mathrm{T}}\]于是学习目标等价于\[\max\limits_{\bm{\alpha}}J(\bm{\alpha})=\frac{\bm{\alpha}^{\mathrm{T}}\mathbf{M}\bm{\alpha}}{\bm{\alpha}^{\mathrm{T}}\mathbf{N}\bm{\alpha}}\]
						\item 用LDA方法求解得到$\bm{\alpha}$，再由$h(\bm{x})=\sum_{i=1}^{m}\alpha_i\kappa(\bm{x},\bm{x}_i)$得到投影函数$h(\bm{x})$。
					\end{enumerate}
					\item 一个推荐的SVM开源库：\href{https://www.csie.ntu.edu.tw/~cjlin/libsvm/}{LIBSVM}
					\end{itemize}
			\section{贝叶斯分类器}
				\subsection{贝叶斯决策论}
					\begin{itemize}
						\item 贝叶斯决策论：基于所有与分类任务相关的概率和误判损失来选择最优的类别标记。
						\item 符号说明：$c_i$表示被分类为第$i$类，即$c_i\in\{c_1,c_2,\dots,c_N\}=\mathcal{Y}$；$\lambda_{ij}$表示将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失。$P(c_i\mid\bm{x})$是一种后验概率，表示将样本$\bm{x}$分类为$c_i$所产生的期望损失。对应的条件风险为$R(c_i\mid\bm{x})=\sum_{i=1}^{N}\lambda_{ij}P(c_j\mid\bm{x})$
						\item 目标：寻找一个判定准则$h:\mathcal{X}\mapsto\mathcal{Y}$以最小化总体风险\[R(h)=\mathbb{E}_{\bm{x}}[R(h(\bm{x})\mid\bm{x})]\]
						\item 贝叶斯判定准则：为最小化总体风险，只需在每个样本上选择那个能使条件风险$R(c\mid\bm{x})$最小的类别标记，即\[h^*(\bm{x})=\arg\limits_{c\in\mathcal{Y}}\min R(c\mid\bm{x})\]此时$h^*$被称为贝叶斯最优分类器，与之对应的总体风险$R(h^*)$称为贝叶斯风险。
						\item 若目标是最小化分类错误率，则$\lambda_{ij}=\left\{\begin{aligned}
						0,\quad & \mathrm{if}\quad i=j;\\
						1,\quad & \mathrm{otherwise}
						\end{aligned}\right.$，此时\[R(c\mid\bm{x})=1-P(c\mid\bm{x})\quad h^*(\bm{x})=\arg\limits_{c\in\mathcal{Y}}\max P(c\mid\bm{x})\]
						 \item 获得后验概率$P(c\mid\bm{x})$的方法：\begin{itemize}
						 	\item 判别式模型：直接建模$P(c\mid\bm{x})$来预测$c$（决策树、BP神经网络、支持向量机）
						 	\item 生成式模型：先对联合概率分布$P(\bm{x},c)$建模，然后获得$P(c\mid\bm{x})$。此处\[P(c\mid\bm{x})=\frac{P(c)P(\bm{x}\mid c)}{P(\bm{x})}\]\begin{itemize}
						 		\item $P(c)$：类先验概率。表达了样本空间中各类样本所占的比例。当训练集包含充足的独立同分布样本时，可通过各样本出现的概率进行估计。
						 		\item $P(\bm{x}\mid c)$：类条件概率。求法见下一节。
						 		\item $P(\bm{x})$：证据因子。与标记无关，可用于归一化。
						 	\end{itemize}
						 \end{itemize}
					\end{itemize}
				\subsection{极大似然估计}
					\begin{itemize}
						\item 极大似然估计在概率论与数理统计课上学过。这里假设$P(\bm{x}\mid c)$具有确定的形式并且被参数向量$\bm{\theta}_c$唯一确定。目的是利用训练集$D$估计参数$\bm{\theta}_c$。\[P(D_c\mid\bm{\theta}_c)=\prod_{\bm{x}\in D_c}^{}P(\bm{x}\mid\bm{\theta}_c)\]\[LL(\bm{\theta}_c)=\log P(D_c\mid\bm{\theta}_c)=\sum_{\bm{x}\in D_c}^{}\log P(\bm{x}\mid\bm{\theta}_c)\]\[\hat{\bm{\theta}}_c=\arg\limits_{\bm{\theta}_c}\max LL(\bm{\theta}_c)\]
					\end{itemize}
				\subsection{朴素贝叶斯分类器}
					\begin{itemize}
						\item 属性条件独立性假设：对已知类别，假设所有属性相互独立。
						\item 基于属性条件独立性假设的类后验概率、贝叶斯判定准则：\[P(c\mid\bm{x})=\frac{P(c)P(\bm{x}\mid c)}{P(\bm{x})}=\frac{P(c)}{P(\bm{x})}\prod_{i=1}^{d}P(x_i\mid c)\]\[h_{nb}(\bm{x})=\arg\limits_{c\in\mathcal{Y}}\max P(c)\prod_{i=1}^{d}P(x_i\mid c)\]
						\item 类先验概率：\[P(c)=\frac{|D_c|}{|D|}\]
						\item 离散属性的条件概率（$D_{c,x_i}$指$D_c$中在第$i$个属性上取值为$x_i$的样本组成的集合）：\[P(x_i\mid c)=\frac{|D_{c,x_i}|}{|D_c|}\]连续属性的条件概率密度函数（假设$p(x_i\mid c)\sim\mathcal{N}(\mu_{c,i},\sigma_{c,i}^2)$）：\[p(x_i\mid c)=\frac{1}{\sqrt{2\pi}}\sigma_{c,i}\exp\bigg(-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2}\bigg)\]
						\item 拉普拉斯修正：为了避免其它属性携带的信息被训练集中未出现的属性值抹去（导致概率估值为零）。设$N$为训练集$D$中可能的类别数，$N_i$表示第$i$个属性可能的取值数。可修正如下：\[\hat{P}(c)=\frac{|D_c|+1}{|D|+N}\]\[\hat{P}(x_i\mid c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}\]
					\end{itemize}
				\subsection{半朴素贝叶斯分类器}
					\begin{itemize}
						\item 基本思想：适当考虑一部分属性间的相互依赖信息，既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。
						\item 独依赖估计（ODE）：假设每个属性在类别之外最多仅依赖于一个其他属性。\[P(c\mid\bm{x})\propto P(c)\prod_{i=1}^{d}P(x_i\mid c,pa_i)\]其中$pa_i$为属性$x_i$所依赖的属性，称为$x_i$的父属性。问题的关键转化为：如何确定每个属性的父属性？\begin{itemize}
							\item SPODE：假设所有属性都依赖于同一个属性（超父）。通过交叉验证等模型选择方法确定超父属性。
							\item TAN：基于最大带权重生成树算法。先计算任意两个属性间的``条件互信息''：\[I(x_i,x_j\mid y)=\sum_{x_i,x_j;c\in\mathcal{Y}}^{}P(x_i,x_j\mid c)\log\frac{P(x_i,x_j\mid c)}{P(x_i\mid c)P(x_j\mid c)}\]然后以属性为结点构建完全图，任意两个结点之间边的权重设为$I(x_i,x_j\mid y)$，构建它的最大带权重生成树，挑选根变量，将边置为有向。最后加入类别结点$y$，增加从$y$到每个属性的有向边。
							\item AODE：一种基于集成学习机制的独依赖分类器。尝试将每个属性作为超父来构建SPODE，将具有足够训练数据支撑的SPODE集成起来作为最终结果。\[P(c\mid\bm{x})\propto\sum_{\substack{i=1\\|D_{x_i}|\ge m'}}^{d}P(c,x_i)\prod_{j=1}^{d}P(x_j\mid c,x_i)\]其中$D_{x_i}$是在第$i$个属性上取值为$x_i$的样本的集合。$m'$为阈值常数。此处\[\hat{P}(c,x_i)=\frac{|D_{c,x_i}|+1}{|D|+N\times N_i}\]\[\hat{P}(x_j\mid c,x_i)=\frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}\]
						\end{itemize}
						\item 若将属性$pa_i$替换成包含$k$个属性的集合$\bm{pa}_i$，从而将ODE拓展为$k$DE。随着$k$的增加，准确估计概率$P(x_i\mid y,\bm{pa}_i)$所需样本数量将以指数级增加。
					\end{itemize}
				\subsection{贝叶斯网}
					
					也称为``信念网''（belief network）。借助有向无环图（DAG）来刻画属性之间的依赖关系。使用条件概率表（CPT）来描述属性的联合概率分布。一个贝叶斯网$B$可以由结构$G$和参数$\Theta$构成。$B=\langle G,\Theta\rangle$。假设属性$x_i$在$G$的父结点集为$\pi_i$，则$\Theta$包含了每个属性的条件概率表$\theta_{x_i\mid\pi_i}=P_B(x_i\mid\pi_i)$。
					\subsubsection{结构}
						\begin{itemize}
							\item 给定父节点集，假设每个属性与它的非后裔属性独立，则$B=\langle G,\Theta\rangle$将属性$x_1,x_2,\dots,x_d$的联合概率分布定义为\[P_B(x_1,x_2,\dots,x_d)=\prod_{i=1}^{d}P_B(x_i\mid\pi_i)=\prod_{i=1}^{d}\theta_{x_i\mid\pi_i}\]
							\item 三个变量的典型依赖关系——\begin{enumerate}
								\item 同父结构：$x_1\rightarrow x_3,x_1\rightarrow x_4$。有$x_3\perp x_4\mid x_1$，而$x_3\bigCI x_4$不成立。（当$x_1$完全未知时的边界独立性）
								\item V型结构：$x_1\rightarrow x_4,x_2\rightarrow x_4$。有$x_1\bigCI x_2$，而$x_1\perp x_2\mid x_4$不成立。
								\item 顺序结构：$z\rightarrow x,x\rightarrow y$。有$y\perp z\mid x$，而$y\bigCI z$不成立。
							\end{enumerate}
							\item 使用``有向分离''（D-separation）将有向图转化为无向图，分析变量间的条件独立性。\begin{enumerate}
								\item 找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边。
								\item 将所有有向边改为无向边。
							\end{enumerate}
							产生的无向图称为``道德图''（moral graph）。令父结点相连的过程称为``道德化''（moralization）。
							\item 基于道德图的条件独立性判断方法：假定道德图中有变量$x,y$和变量集合$\bm{z}=\{z_i\}$，若变量$x$和$y$能在图上被$\bm{z}$分开，即从道德图中将$\bm{z}$去除后，$x$和$y$分属两个连通分支，则称变量$x$和$y$被$\bm{z}$有向分离，$x\perp y\mid\bm{z}$成立。 
						\end{itemize}
					\subsubsection{学习}
						\begin{itemize}
							\item 贝叶斯网的首要任务：根据训练数据集来找出结构最``恰当''的贝叶斯网。
							\item 常用方法：评分搜索。定义评分函数，以此评估贝叶斯网与训练数据的契合程度，以此寻找结构最优的贝叶斯网。
							\item 学习目标：找到综合编码长度（包括描述网络和编码数据）最短的贝叶斯网。即``最小描述长度''（MDL）准则。
							\item 给定训练集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$，贝叶斯$B=\langle G,\Theta\rangle$在$D$上的评分函数可写为\[s(B\mid D)=f(\theta)|B|-LL(B\mid D)\]其中$|B|$是贝叶斯网的参数个数，$f(\theta)$表示描述每个参数$\theta$所需的字节数，\[LL(B\mid D)=\sum_{i=1}^{m}\log P_B(\bm{x}_i)\]是贝叶斯网的对数似然。\begin{itemize}
								\item 若$f(\theta)=1$，得到AIC（Akaike Information Criterion），即$AIC(B\mid D)=|B|-LL(B\mid D)$。
								\item 若$f(\theta)=\frac{1}{2}\log m$，得到BIC（Bayesian Information Criterion），即$BIC(B\mid D)=\frac{\log m}{2}|B|-LL(B\mid D)$。
								\item 若$f(\theta)=0$，则学习任务退化为极大似然估计。
							\end{itemize}
							\item 若$G$固定，则$f(\theta)|B|$为常数，问题等价于对$\Theta$进行极大似然估计。这里每个参数$\theta_{x_i\mid\pi_i}$能直接在训练数据$D$上通过经验估计获得：\[\theta_{x_i\mid\theta_i}=\hat{P}_D(x_i\mid\pi_i)\]其中$\hat{P}_D(\cdot)$是$D$上的经验分布。
							\item 求解方法\begin{itemize}
								\item 从所有可能的网络结构空间搜索最优贝叶斯网结构是NP难问题。
								\item 贪心法（近似解）：从某个网络结构出发，每次调整一条边，直到评分函数值不再降低为止。
								\item 添加约束（近似解）：比如将网络结构限定为树形结构。
							\end{itemize}
						\end{itemize}
					\subsubsection{推断}
						\begin{itemize}
							\item 推断：通过已知变量观测值来推测待查询变量的过程。证据：已知变量观测值。
							\item 直接精确计算后验概率：NP-hard。
							\item 近似推断方法：吉布斯采样（Gibbs sampling）。设$\bm{Q}=\{Q_1,Q_2,\dots,Q_n\}$表示待查询变量，$\bm{E}=\{E_1,E_2,\dots,E_k\}$为证据变量，其取值为$\bm{e}=\{e_1,e_2,\dots,e_k\}$，目标是计算后验概率$P(\bm{Q}=\bm{q}\mid\bm{E}=\bm{e})$，其中$\bm{q}=\{q_1,q_2,\dots,q_n\}$是待查询变量的一组取值。吉布斯采样就是在贝叶斯网所有变量的联合状态空间与证据$\bm{E}=\bm{e}$一致的子空间中进行``随机漫步''。\begin{algorithm}
								\caption{吉布斯采样算法}
								\begin{algorithmic}[1]
									\REQUIRE 贝叶斯网$B=\langle G,\Theta\rangle$，采样次数$T$，证据变量$\bm{E}$及其取值$\bm{e}$，待查询变量$\bm{Q}$及其$\bm{q}$。
									\ENSURE $P(\bm{Q}=\bm{q}\mid\bm{E}=\bm{e})\simeq\frac{n_q}{T}$
									\STATE $n_q=0$ \\
									\STATE $\bm{q}^0=\textrm{对}\bm{Q}\textrm{随机赋初值}$ \\
									\FOR{$t=1,2,\dots,T$}
										\FOR{$Q_i\in\bm{Q}$}
											\STATE $\bm{Z}=\bm{E}\cup\bm{Q}\backslash\{Q_i\}$\\
											\STATE $\bm{z}=\bm{e}\cup\bm{q}^{t-1}\backslash\{q_i^{t-1}\}$\\
											\STATE 根据$B$计算分布$P_B(Q_i\mid\bm{Z}=\bm{z})$\\
											\STATE $q_i^t=\textrm{根据}P_B(Q_i\mid\bm{Z}=\bm{z})\textrm{采样所获}Q_i\textrm{取值}$\\
											\STATE $\bm{q}^t=\textrm{将}\bm{q}^{t-1}\textrm{中的}q_i^{t-1}\textrm{用}q_i^t\textrm{替换}$\\
										\ENDFOR
									\IF{$\bm{q}^t=\bm{q}$}
										\STATE $n_q=n_q+1$\\
									\ENDIF
								\ENDFOR
								\end{algorithmic} 
							\end{algorithm}
						\end{itemize}
				\subsection{EM算法}
					\begin{itemize}
						\item 样本中可能出现隐变量（未观测的、变量值未知的变量）。设已观测变量集为$\bm{X}$、隐变量集为$\bm{Z}$、模型参数为$\bm{\Theta}$。通过对$\bm{Z}$计算期望，最大化已观测数据的对数边际似然。\[LL(\Theta\mid\bm{X})=\ln P(\bm{X}\mid\Theta)=\ln\sum_{\bm{Z}}^{}P(\bm{X},\bm{Z}\mid\Theta)\]
						\item EM算法（期望最大值算法）：若参数$\Theta$已知，则可根据训练数据推断出最优隐变量$\bm{Z}$的值；反之若$\bm{Z}$已知，则可对参数$\Theta$已知做极大似然估计。
						\item 原型：\begin{enumerate}
							\item 基于$\Theta^t$推断隐变量$\bm{Z}$的期望，记为$\bm{Z}^t$；
							\item 基于已观测变量$\bm{X}$和$\bm{Z}^t$对参数$\Theta$做极大似然估计，记为$\Theta^{t+1}$。
							\item 重复以上两步直至收敛。
						\end{enumerate}
						\item 不取$\bm{Z}$的期望，而是基于$\Theta^t$计算隐变量$\bm{Z}$的概率分布$P(\bm{Z}\mid \bm{X},\Theta^t)$。\begin{enumerate}
							\item E步——以当前参数$\Theta^t$推断隐变量分布$P(\bm{Z}|\bm{X},\Theta^t)$，并计算对数似然$LL(\Theta\mid\bm{X},\bm{Z})$关于$\bm{Z}$的期望\[Q(\Theta\mid\Theta^t)=\mathbb{E}_{\bm{Z}\mid \bm{X},\Theta^t}LL(\Theta\mid\bm{X},\bm{Z})\]
							\item M步——寻找参数最大化期望似然\[\Theta^{t+1}=\arg\limits_{\Theta}\max Q(\Theta\mid\Theta^t)\]
						\end{enumerate}
					\end{itemize}
			\section{集成学习}
				\subsection{个体与集成}
					\begin{itemize}
						\item 集成学习（多分类器系统）：通过构建并结合多个学习器来完成学习任务。
						\item 同质集成：集成中只包含同种类型的个体学习器。此时个体学习器可称为``基学习器''。
						\item 异质集成：集成中包含不同类型的个体学习器。此时个体学习器可称为``组件学习器''。
						\item 个体学习器的准确性和多样性存在冲突。研究核心：产生并结合``好而不同''的个体学习器。
						\item 集成学习方法\begin{itemize}
							\item 个体学习器间强依赖，必须串行生成$\rightarrow$Boosting
							\item 个体学习器间不强依赖，可同时生成$\rightarrow$Bagging和Random Forest
						\end{itemize}
					\end{itemize}
				\subsection{Boosting}
					\begin{itemize}
						\item Boosting：一族可将弱学习器提升为强学习器的算法。先从初始训练集训练出一个基学习器，根据其表现调整训练样本分布，更多关注做错的训练样本，基于此训练下一个基学习器。如此直至基学习器数目达到事先指定的值$T$，最终将$T$个基学习器加权结合。
						\item AdaBoost算法（标准型🈯只适用于二分类任务）基于``加性模型$H(\bm{x})=\sum_{t=1}^{T}\alpha_th_t(\bm{x})$，最小化指数损失函数\[\ell_{\mathrm{exp}}(H\mid\mathcal{D})=\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H(\bm{x})}]\]\begin{algorithm}
							\caption{AdaBoost算法}
							\begin{algorithmic}[1]
								\REQUIRE 训练集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$，基学习算法$\mathfrak{L}$，训练轮数$T$
								\ENSURE $H(\bm{x})=\mathrm{sign}\big(\sum_{t=1}^{T}\alpha_th_t(\bm{x})\big)$
								\STATE $\mathcal{D}_1(\bm{x})=1/m$ \\
								\FOR{$t=1,2,\dots,T$}
									\STATE $h_t=\mathfrak{L}(D,\mathcal{D}_t)$ \\
									\STATE $\epsilon_t = P_{\bm{x}\sim\mathcal{D}_t}(h_t(\bm{x})\neq f(\bm{x}))$ \\
									\IF{$\epsilon_t>0.5$}
										\STATE \textbf{break}\\
									\ENDIF
									\STATE $\alpha_t=\frac{1}{2}\ln(\frac{1-\epsilon_t}{\epsilon_t})$\\
									\STATE $\mathcal{D}_{t+1}(\bm{x})=\frac{\mathcal{D}_t(\bm{x})\exp(-\alpha_tf(\bm{x})h_t(\bm{x}))}{Z_t}$\\
								\ENDFOR
							\end{algorithmic} 
						\end{algorithm}
						\item 使用``指数损失函数''的合理性：求指数损失函数对$H(\bm{x})$的偏导并令零可得到\[H(\bm{x})=\frac{1}{2}\ln\frac{P(f(x)=1\mid\bm{x})}{P(f(x)=-1\mid\bm{x})}\]由此$\mathrm{sign}(H(\bm{x}))=\arg\limits_{y\in\{-1,1\}}\max P(f(x)=y\mid\bm{x})$达到了贝叶斯最优错误率。说明指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数，且连续可微。
						\item 分类器权重更新公式的推导：使$\alpha_th_t$最小化指数损失函数：\[\ell_{\mathrm{exp}}(\alpha_th_t\mid\mathcal{D}_t)=\mathbb{E}_{\bm{x}\sim\mathcal{D}_t}\big[e^{-f(\bm{x})\alpha_th_t(\bm{x})}\big]=e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t\]对$\alpha_t$求偏导并令零，可得到权重更新公式\[\alpha_t=\frac{1}{2}\ln\bigg(\frac{1-\epsilon_t}{\epsilon_t}\bigg)\]
						\item 样本分布更新公式的推导：\begin{enumerate}
							\item 理想的下一轮基学习器$h_t$能纠正$H_{t-1}$的全部错误，即最小化\[\ell_{\mathrm{exp}}(H_{t-1}+h_t\mid\mathcal{D})=\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t-1}(\bm{x})}e^{-f(\bm{x})h_t(\bm{x})}]\]
							\item 使用泰勒展式，可将$e^{-f(\bm{x})h_t(\bm{x})}$近似为$1-f(\bm{x})h_t(\bm{x})+\frac{f^2(\bm{x})h_t^2(\bm{x})}{2}=\frac{3}{2}-f(\bm{x})h_t(\bm{x})$
							\item 理想的基学习器\begin{align*}
								h_t(\bm{x}) = & \arg\limits_{h}\min\ell_{\mathrm{exp}}(H_{t-1}+h\mid\mathcal{D})\\
								=& \arg\limits_{h}\max\mathbb{E}_{\bm{x}\sim\mathcal{D}}\bigg[\frac{e^{-f(\bm{x})H_{t-1}(\bm{x})}}{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t-1}(\bm{x})}]}f(\bm{x})h(\bm{x})\bigg]
							\end{align*}
							其中$\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t-1}(\bm{x})}]$是一个常数。
							\item 令\[\mathcal{D}_t(\bm{x})=\frac{\mathcal{D}(\bm{x})e^{-f(\bm{x})H_{t-1}(\bm{x})}}{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t-1}(\bm{x})}]}\]等价于令\[h_t(\bm{x})=\arg\limits_{h}\max\mathbb{E}_{\bm{x}\sim\mathcal{D}_t}[f(\bm{x})h(\bm{x})]\]
							\item \begin{align*}
								\mathcal{D}_{t+1}(\bm{x}) = & \frac{\mathcal{D}(\bm{x})e^{-f(\bm{x})H_t(\bm{x})}}{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_t(\bm{x})}]}\\
								= & \frac{\mathcal{D}(\bm{x})e^{-f(\bm{x})H_{t-1}(\bm{x})}e^{-f(\bm{x})\alpha_th_t(\bm{x})}}{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_t(\bm{x})}]}\\
								= & \mathcal{D}_t(\bm{x})\cdot e^{-f(\bm{x})\alpha_th_t(\bm{x})}\frac{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t-1}(\bm{x})}]}{\mathbb{E}_{\bm{x}\sim\mathcal{D}}[e^{-f(\bm{x})H_{t}(\bm{x})}]}
							\end{align*}
						\end{enumerate}
						\item 重赋权法：在训练的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。在训练的每一轮检查当前生成的基学习器是否满足基本条件，一旦不满足，则抛弃当前基学习器，学习过程停止。
						\item 重采样法：在训练的每一轮中，根据样本分布对训练集重新进行采样，再据此对基学习器进行训练。可以不抛弃不满足条件的当前基学习器，使学习过程维持到预设的$T$轮完成。
						\item 偏差-方差分解角度：关注降低偏差
					\end{itemize}
				\subsection{Bagging与随机森林}
					 
					 采样思路：希望基学习器有较大差异 \& 每个基学习器使用的训练数据不能太小 $\rightarrow$ 使用相互有交叠的采样子集
					 
					 \subsubsection{Bagging}
					 	\begin{itemize}
					 		\item 采样方法：自助采样法
					 		\item 输出结合方法：投票法（分类）、平均法（回归）
					 		\item 算法描述（$\mathcal{D}_{bs}$是自助采样产生的样本分布）\begin{algorithm}
					 			\caption{Bagging算法}
					 			\begin{algorithmic}[1]
					 				\REQUIRE 训练集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$，基学习算法$\mathfrak{L}$，训练轮数$T$
					 				\ENSURE $H(\bm{x})=\arg\limits_{y\in\mathcal{Y}}\max\sum_{t=1}^{T}\mathbb{I}(h_t(\bm{x})=y)$
					 				\FOR{$t=1,2,\dots,T$}
					 					\STATE $h_t=\mathfrak{L}(D,\mathcal{D}_{bs})$\\
					 				\ENDFOR
					 			\end{algorithmic} 
					 		\end{algorithm}
				 			\item 计算复杂度：$T(O(m)+O(s))$。高效。
				 			\item 包外估计：因自助采样，有约36.8\%的样本可用作验证集。令$D_t$表示$h_t$实际使用的训练样本集，$H^{oob}(\bm{x})$表示对样本$\bm{x}$的包外预测。于是\[H^{oob}(\bm{x})=\arg\limits_{y\in\mathcal{Y}}\max\sum_{t=1}^{T}\mathbb{I}(h_t(\bm{x})=y)\cdot\mathbb{I}(\bm{x}\notin D_t)\]\[\epsilon^{oob}=\frac{1}{|D|}\sum_{(\bm{x},y)\in D}^{}\mathbb{I}(H^{oob}(\bm{x})\neq y)\]
				 			\item 其他用途：决策树$\rightarrow$包外样本辅助剪枝或估计各结点的后验概率以辅助对零训练样本结点的处理；神经网络$\rightarrow$使用包外样本辅助早期停止以减小过拟合风险。
				 			\item 偏差-方差分解角度：关注降低方差。
					 	\end{itemize}
				 	\subsubsection{随机森林}
				 		\begin{itemize}
				 			\item 以决策树为基学习器
				 			\item 在Bagging集成的基础上，引入随机属性选择，对基决策树的每个结点，从该结点的属性集合中随机选择一个包含$k$个属性的子集，然后从这个子集中选择一个最优属性进行划分。推荐$k=\log_2d$
				 			\item 简单、易实现、开销小、被誉为``代表集成学习技术水平的方法''。训练效率常优于Bagging。
				 		\end{itemize}
			 	\subsection{结合策略}
			 		学习器结合的三个好处：\begin{itemize}
			 			\item 统计方面：减少因假设空间很大导致泛化性能不佳的风险
			 			\item 计算方面：降低陷入糟糕局部极小点的风险
			 			\item 表示方面：可使假设空间有所扩大，以包含真实假设
			 		\end{itemize}
		 			\subsubsection{平均法}
		 				\begin{itemize}
		 					\item 是数值型输出$h_i(\bm{x})\in\mathbb{R}$的最常见结合策略。
		 					\item 简单平均法\[H(\bm{x})=\frac{1}{T}\sum_{i=1}^{T}h_i(\bm{x})\]
		 					\item 加权平均法\[H(\bm{x})=\sum_{i=1}^{T}w_ih_i(\bm{x})\]
		 					\item 一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。
		 				\end{itemize}
	 				\subsubsection{投票法}
	 					
	 					\begin{itemize}
	 						\item 针对分类任务。类别标记集合为$\{c_1,c_2,\dots,c_N\}$。将$h_i$在样本$\bm{x}$上的预测输出表示为一个$N$维向量$(h_i^1(\bm{x});h_i^2(\bm{x});\dots;h_i^N(\bm{x}))$，其中$h_i^j(\bm{x})$是$h_i$在类别标记$c_j$上的输出。
	 					
		 					\item 投票方法\begin{itemize}
		 						\item 绝对多数投票法（若某标记得票过半数则预测为该标记，否则拒绝预测）
		 						\[H(\bm{x})=\left\{\begin{aligned}
		 						&c_j, && \mathrm{if}\quad\sum_{i=1}^{T}h_i^j(\bm{x})>0.5\sum_{k=1}^{N}\sum_{i=1}^{T}h_i^k(\bm{x});\\
		 						&\mathrm{reject,} && \mathrm{otherwise.}
		 						\end{aligned}\right.\]
		 						\item 相对多数投票法（预测为得票最多的标记，若同时有多个标记或最高票，则随机选取一个）
		 						\[H(\bm{x})=c_{\arg\limits_{j}\max\sum_{i=1}^{T}h_i^j(\bm{x})}\]
		 						\item 加权投票法（通常$w_i\ge0,\sum_{i=1}^{T}w_i=1$）\[H(\bm{x})=c_{\arg\limits_{j}\max\sum_{i=1}^{T}w_ih_i^j(\bm{x})}\]
		 						\end{itemize}
	 						\item 输出值$h_i^j(\bm{x})$的类型分类\begin{itemize}
	 							\item 类标记（硬投票）：$h_i^j(\bm{x})\in\{0,1\}$。若$h_i$将样本$\bm{x}$预测为类型$c_j$则取值为1，否则为0。
	 							\item 类概率（软投票）：$h_i^j(\bm{x})\in[0,1]$。相当于对后验概率$P(c_j\mid\bm{x})$的一个估计。
	 						\end{itemize}
 						\end{itemize}
 					\subsubsection{学习法}
 						\begin{itemize}
 							\item 策略：通过另一个学习器来进行结合。个体学习器$\rightarrow$初级学习器；用于结合的学习器$\rightarrow$次级学习器/元学习器
 							\item Stacking算法描述\begin{algorithm}
 								\caption{Stacking算法}
 								\begin{algorithmic}[1]
 									\REQUIRE 训练集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$，初级学习算法$\mathfrak{L}_1,\mathfrak{L}_2,\dots,\mathfrak{L}_T$，次级学习算法$\mathfrak{L}$。
 									\ENSURE $H(\bm{x})=h'(h_1(\bm{x}),h_2(\bm{x}),\dots,h_T(\bm{x})$
 									\FOR{$t=1,2,\dots,T$}
 										\STATE $h_t=\mathfrak{L}_t(D)$;\\
 									\ENDFOR
 									\STATE $D'=\emptyset$;\\
 									\FOR{$i=1,2,\dots,m$}
 										\FOR{$t=1,2,\dots,T$}
 											\STATE $z_{it}=h_t(\bm{x}_i)$;\\
 										\ENDFOR
 										\STATE $D'=D'\cup((z_{i1},z_{i2},\dots,z_{iT}),y_i)$;\\
 									\ENDFOR
 									\STATE $h'=\mathfrak{L}(D')$;
 								\end{algorithmic} 
 							\end{algorithm}
 							\item 一般采用交叉验证法或留一法。
 							\item 研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（MLR）作为次级学习算法效果较好。
 						\end{itemize}
 				\subsection{多样性}
 					\subsubsection{误差-分歧分解}
 						\begin{itemize}
 							\item 对示例$\bm{x}$，学习器$h_i$的``分歧''（ambiguity）：\[A(h_i\mid\bm{x})=\big(h_i(\bm{x})-H(\bm{x})\big)^2\]
 							\item 集成的``分歧''（反映个体学习器的多样性）：\[\overline{A}(h\mid\bm{x})=\sum_{i=1}^{T}w_iA(h_i\mid\bm{x})=\sum_{i=1}^{T}w_i\big(h_i(\bm{x})-H(\bm{x})\big)^2\]
 							\item 个体学习器$h_i$和集成$H$的平方误差\[E(h_i\mid\bm{x})=\big(f(\bm{x})-h_i(\bm{x})\big)^2\]\[E(H\mid\bm{x})=\big(f(\bm{x})-H(\bm{x})\big)^2\]
 							\item 对于全样本，个体的泛化误差、分歧项为\[E_i=\int E(h_i\mid\bm{x})p(\bm{x})d\bm{x}\]\[A_i=\int A(h_i\mid\bm{x})p(\bm{x})d\bm{x}\]
 							\item 对于全样本，集成的泛化误差、个体学习器泛化误差的加权均值、个体学习器的加权分分歧值为\[E=\int E(H\mid\bm{x})p(\bm{x})d\bm{x}\]\[\overline{E}=\sum_{i=1}^{T}w_iE_i\]\[\overline{A}=\sum_{i=1}^{T}w_iA_i\]
 							\item 误差-分歧分解（个体学习器准确性越高、多样性越大，则集成越好）\[E=\overline{E}-\overline{A}\]
 						\end{itemize}
 					\subsubsection{多样性度量}
 					
 						以如下二分类任务为例（$a+b+c+d=m$）\begin{center}
 							\begin{tabular}{c|cc}
 								\hline
 								& $h_i=+1$ & $h_i=-1$ \\ \hline
 								$h_j=+1$ & $a$ & $c$ \\
 								$h_j=-1$ & $b$ & $d$ \\ \hline
 							\end{tabular}
 						\end{center}
 						\begin{itemize}
 							\item 不合度量（disagreement measure）：值越大多样性越大\[dis_{ij}=\frac{b+c}{m}\]
 							\item 相关系数（correlation coefficient）：无关0，正相关正，负相关负\[\rho_{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}\]
 							\item $Q$-统计量：与相关系数符号相同，且$|Q_{ij}|\ge|\rho_{ij}|$\[Q_{ij}=\frac{ad-bc}{ad+bc}\]
 							\item $\kappa$-统计量：若两个分类器在$D$上完全一致则$\kappa=1$，若仅是偶然达成一致，则$\kappa=0$。\[\kappa=\frac{p_1-p_2}{1-p_2}\]\[p_1=\frac{a+d}{m}\]\[p_2=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^2}\]
 						\end{itemize}
 					\subsubsection{多样性增强}
 						\begin{itemize}
 							\item 数据样本扰动：基于采样法。不稳定基学习器（样本扰动敏感）：决策树、神经网络；稳定基学习器：线性学习器、支持向量机、朴素贝叶斯、$k$近邻学习器。
 							\item 输入属性扰动：\begin{algorithm}
 								\caption{随机子空间算法}
 								\begin{algorithmic}[1]
 									\REQUIRE 训练集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$，基学习算法$\mathfrak{L}$，基学习器数$T$，子空间属性数$d'$
 									\ENSURE $H(\bm{x})=\arg\limits_{y\in\mathcal{Y}}\max\sum_{t=1}^{T}\mathbb{I}(h_t(\mathrm{Map}_{\mathcal{F}_t}(\bm{x}))=y)$
 									\FOR{$t=1,2,\dots,T$}
 										\STATE $\mathcal{F}_t=\mathrm{RS}(D,d')$\\
 										\STATE $D_t=\mathrm{Map}_{\mathcal{F}_t}(D)$\\
 										\STATE $h_t=\mathfrak{L}(D_t)$\\
 									\ENDFOR
 								\end{algorithmic} 
 							\end{algorithm}
 							\item 输出表示扰动：对输出表示进行操纵\begin{itemize}
 								\item 翻转法：随机改变一些训练样本的标记
 								\item 输出调制法：将分类输出转化为回归输出后建构个体学习器
 								\item ECOC法：利用纠错输出码将多分类任务拆解为一系列二分类任务
 							\end{itemize}
 							\item 算法参数扰动：随机设置不同的参数。对参数较少的算法，可通过将其学习过程中某些环节用其他类似方式代替。
 						\end{itemize}
			\section{聚类}
				\subsection{聚类任务}
					
					假定样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$包含$m$个无标记样本，聚类算法将$D$划分为$k$个不相交的簇$\{C_l\mid l=1,2,\dots,k\}$，其中$C_{l'}\cap_{l'\neq l}C_l=\empty$且$D=\cup_{l=1}^kC_l$。用$\lambda_j\in\{1,2,\dots,k\}$表示样本$\bm{x}_j$的``簇标记''，即$\bm{x}_j\in C_{\lambda_j}$。于是聚类结果可以用簇标记向量$\bm{\lambda}=(\lambda_1;\lambda_2;\dots;\lambda_m)$表示。
				\subsection{性能度量}
					\begin{itemize}
						\item 聚类性能度量分类：外部指标（与某个参考模型进行比较）；内部指标（直接考察聚类结果）
						\item 设带星号的为参考模型对应的变量。考虑两两配对，定义\begin{align*}
							& a = |SS|, & SS=\{(\bm{x}_i,\bm{x}_j)\mid\lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}\\
							& b = |SD|, & SD=\{(\bm{x}_i,\bm{x}_j)\mid\lambda_i=\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j\}\\
							& c = |DS|, & DS=\{(\bm{x}_i,\bm{x}_j)\mid\lambda_i\neq\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}\\
							& d = |DD|, & DD=\{(\bm{x}_i,\bm{x}_j)\mid\lambda_i\neq\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j\}
						\end{align*}
						其中$a+b+c+d=m(m-1)/2$
						\item 外部指标（以下三者均在$[0,1]$区间，越大越好）\begin{itemize}
							\item Jaccard系数（JC）\[\mathrm{JC}=\frac{a}{a+b+c}\]
							\item FM指数（FMI）\[\mathrm{FMI}=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}}\]
							\item Rand指数（RI）\[\mathrm{RI}=\frac{2(a+d)}{m(m-1)}\]
						\end{itemize}
						\item 各种距离函数\begin{itemize}
							\item 簇$C$内样本间平均距离\[\mathrm{avg}(C)=\frac{2}{|C|(|C|-1)}\sum_{1\le i<j\le|C|}^{}\mathrm{dist}(\bm{x}_i,\bm{x}_j)\]
							\item 簇$C$内样本间最远距离\[\mathrm{diam}(C)=\max_{1\le i<j\le|C|}\mathrm{dist}(\bm{x}_i,\bm{x}_j)\]
							\item 簇$C_i$与簇$C_j$最近样本间距离\[d_{\mathrm{min}}(C_i,C_j)=\min_{\bm{x}_i\in C_i,\bm{x}_j\in C_j}\mathrm{dist}(\bm{x}_i,\bm{x}_j)\]
							\item 簇$C_i$与簇$C_j$中心点间距离\[d_{\mathrm{cen}}(C_i,C_j)=\mathrm{dist}(\bm{\mu}_i,\bm{\mu}_j)\]其中\[\bm{\mu}=\frac{1}{|C|}\sum_{1\le i\le|C|}^{}\bm{x}_i\]
						\end{itemize}
					\item 内部指标（DBI越小越好，DI越大越好）\begin{itemize}
						\item DB指数（DBI）\[\mathrm{DBI}=\frac{1}{k}\sum_{i=1}^{k}\max\limits_{j\neq i}\bigg(\frac{\mathrm{avg}(C_i)+\mathrm{avg}(C_j)}{d_{\mathrm{cen}}(\bm{\mu}_i,\bm{\mu}_j)}\bigg)\]
						\item Dunn指数（DI）\[\mathrm{DI}=\min\limits_{1\le i\le k}\bigg\{\min\limits_{j\neq i}\bigg(\frac{d_{\mathrm{min}}(C_i,C_j)}{\max_{1\le l\le k}\mathrm{diam}(C_l)}\bigg)\bigg\}\]
					\end{itemize}
					\end{itemize}
				\subsection{距离计算}
					\begin{itemize}
						\item 函数$\mathrm{dist}(\cdot,\cdot)$若是一个距离度量，需满足四个基本性质：\begin{enumerate}
							\item 非负性：$\mathrm{dist}(\bm{x}_i,\bm{x}_j)\ge0$
							\item 同一性：$\mathrm{dist}(\bm{x}_i,\bm{x}_j)=0$当且仅当$\bm{x}_i=\bm{x}_j$
							\item 对称性：$\mathrm{dist}(\bm{x}_i,\bm{x}_j)=\mathrm{dist}(\bm{x}_j,\bm{x}_i)$
							\item 直递性：$\mathrm{dist}(\bm{x}_i,\bm{x}_j)\le\mathrm{dist}(\bm{x}_i,\bm{x}_k)+\mathrm{dist}(\bm{x}_k.\bm{x}_j)$
						\end{enumerate}
						\item 给定样本$\bm{x}_i=(x_{i1};x_{i2};\dots;x_{in})$和$\bm{x}_j=(x_{j1};x_{j2};\dots;x_{jn})$。闵可夫斯基距离（Minkowski distance）  【可用于有序属性】：\[\mathrm{dist}_{\mathrm{mk}}(\bm{x}_i,\bm{x}_j)=\bigg(\sum_{u=1}^{n}|x_{iu}-x_{ju}|^p\bigg)^{\frac{1}{p}}\]$p=2$时即为欧式距离，$p=1$时即为曼哈顿距离\[\mathrm{dist_{ed}}(\bm{x}_i,\bm{x}_j)=||\bm{x}_i-\bm{x}_j||_2=\sqrt{\sum_{u=1}^{n}|x_{iu}-x_{ju}|^2}\]\[\mathrm{dist_{man}}(\bm{x}_i,\bm{x}_j)=||\bm{x}_i-\bm{x}_j||_1=\sum_{u=1}^{n}|x_{iu}-x_{ju}|\]
						\item VMD距离【可用于无序属性】：$m_{u,a,i}$表示在第$i$个样本簇中在属性$u$上取值为$a$的样本数。\[\mathrm{VDM}_p(a,b)=\sum_{i=1}^{k}\bigg|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}\bigg|^p\]
						\item 结合两种距离，设有$n_c$个有序属性、$n-n_c$个无序属性\[\mathrm{MinkovDM}_p(\bm{x}_i,\bm{x}_j)=\bigg(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^{n}\mathrm{VDM}_p(x_{iu},x_{ju})\bigg)^{\frac{1}{p}}\]
						\item 加权距离（以加权闵可夫斯基距离为例）\[\mathrm{dist_{wmk}}(\bm{x}_i,\bm{x}_j)=(w_i\cdot|x_{i1}-x_{j1}|^p+\dots+w_n\cdot|x_{in}-x_{jn}|^p)^{\frac{1}{p}}\]
					\end{itemize}
				\subsection{原型聚类}
					\begin{itemize}
						\item 原型：样本空间中具有代表性的点
						\item 原型聚类算法：先对原型进行初始化，再对原型进行迭代更新求解。
					\end{itemize}
					\subsubsection{$k$-均值算法}
						\begin{itemize}
							\item 目标：最小化平方误差$E=\sum_{i=1}^{k}\sum_{\bm{x}\in C_i}^{}||\bm{x}-\bm{\mu}_i||_2^2$（NP-hard）。故用贪心策略近似求解。
							\item 算法描述\begin{algorithm}
								\caption{$k$-均值算法}
								\begin{algorithmic}[1]
									\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、聚类簇数$k$.
									\ENSURE 簇划分$\mathcal{C}=\{C_1,C_2,\dots,C_k\}$
									\STATE 从$D$中随机选择$k$个样本作为初始均值向量$\{\bm{\mu}_1,\bm{\mu}_2,\dots,\bm{\mu}_k\}$; \\
									\REPEAT
									\STATE 令$C_i=\emptyset\quad(1\le i\le k)$; \\
									\FOR{$j=1,2,\dots,m$}
										\STATE 计算样本$\bm{x}_j$与各均值向量$\bm{\mu}_i\quad(1\le i\le k)$的距离：\[d_{ji}=||\bm{x}_j-\bm{\mu}_i||_2\] \\
										\STATE 根据距离最近的均值向量确定$\bm{x}_j$的簇标记：\[\lambda_j=\arg\min_{i\in\{1,2,\dots,k\}}d_{ji}\] \\
										\STATE 将样本$\bm{x}_j$划入相应的簇：$C_{\lambda_j}=C_{\lambda_j}\cup\{\bm{x}_j\}$; \\
									\ENDFOR
									\FOR{$i=1,2,\dots,k$}
										\STATE 计算新均值向量：$\bm{\mu}_i'=\frac{1}{|C_i|}\sum_{\bm{x}\in C_i}^{}\bm{x}$; \\
										\IF{$\bm{\mu}_i'\neq\bm{\mu}_i$}
											\STATE 将当前均值向量$\bm{\mu}_i$更新为$\bm{\mu}_i'$; \\
										\ELSE
											\STATE 保持当前均值向量不变; \\
										\ENDIF
									\ENDFOR
									\UNTIL{当前均值向量均未更新}
								\end{algorithmic} 
							\end{algorithm}
						\end{itemize}
					\subsubsection{学习向量量化}
						\begin{itemize}
							\item LVQ假设数据样本带有类别标记，利用这些监督信息辅助聚类。
							\item 目标：学得一组$n$维原型向量$\{\bm{p}_1,\bm{p}_2,\dots,\bm{p}_q\}$，每个原型向量代表一个聚类簇，簇标记$t_i\in\mathcal{Y}$
							\item 算法描述\begin{algorithm}
								\caption{学习向量量化算法}
								\begin{algorithmic}[1]
									\REQUIRE 样本集$D=\{(\bm{x}_1,y_1),(\bm{x}_2,y_2),\dots,(\bm{x}_m,y_m)\}$、原型向量个数$q$、各原型向量预设的类别标记$\{t_1,t_2,\dots,t_q\}$、学习率$\eta\in(0,1)$
									\ENSURE 原型向量$\{\bm{p}_1,\bm{p}_2,\dots,\bm{p}_q\}$
									\STATE 初始化一组原型向量$\{\bm{p}_1,\bm{p}_2,\dots,\bm{p}_q\}$; \\
									\REPEAT
										\STATE 从样本集$D$随机选取样本$(\bm{x}_j,y_j)$; \\
										\STATE 计算样本$\bm{x}_j$与$\bm{p}_i(1\le i\le q)$的距离：$d_{ji}=||\bm{x}_j-\bm{p}_i||_2$; \\
										\STATE 找出与$\bm{x}_j$距离最近的原型向量$p_{i^*}$，$i^*=\arg\min_{i\in\{1,2,\dots,q\}}d_{ji}$; \\
										\IF{$y_j=t_{i^*}$}
											\STATE $\bm{p}'=\bm{p}_{i^*}+\eta\cdot(\bm{x}_j-\bm{p}_{i^*})$; \\
										\ELSE
											\STATE $\bm{p}'=\bm{p}_{i^*}-\eta\cdot(\bm{x}_j-\bm{p}_{i^*})$; \\
										\ENDIF
										\STATE 将原型向量$\bm{p}_{i^*}$更新为$\bm{p}'$; \\
									\UNTIL{满足停止条件}
								\end{algorithmic} 
							\end{algorithm}
							\item 学得原型向量后，对任意样本，它被划入与其距离最近的原型向量所代表的簇中。形成了对样本空间的Voronoi划分。
						\end{itemize}
					\subsubsection{高斯混合聚类}
						\begin{itemize}
							\item 高斯分布、EM算法、极大似然法和聚类的结合
							\item 服从高斯分布的概率密度函数\[p(\bm{x\mid \bm{\mu},\bm{\Sigma}})=\frac{1}{(2\pi)^{\frac{n}{2}}|\bm{\Sigma}|^{\frac{1}{2}}}e^{-\frac{1}{2}(\bm{x}-\bm{\mu})^T\bm{\Sigma}^{-1}(\bm{x}-\bm{\mu})}\]
							\item 高斯混合分布\[p_{\mathcal{M}}(\bm{x})=\sum_{i=1}^{k}\alpha_i\cdot p(\bm{x}\mid\bm{\mu}_i,\bm{\Sigma}_i)\]
							\item 生成样本$\bm{x}_j$的每一个高斯混合成分的后验分布（记为$\gamma_{ji}$）\[p_{\mathcal{M}}(z_j=i\mid\bm{x}_j)=\frac{P(z_j=i)\cdot p_{\mathcal{M}}(\bm{x}_j\mid z_j=i)}{p_{\mathcal{M}}(\bm{x}_j)}=\frac{\alpha_i\cdot p(\bm{x}_j\mid \bm{\mu}_i,\bm{\Sigma}_i)}{\sum_{l=1}^{k}\alpha_l\cdot p(\bm{x}_j\mid\bm{\mu}_l,\bm{\Sigma}_l)}\]
							\item 算法描述\begin{algorithm}
								\caption{高斯混合聚类算法}
								\begin{algorithmic}[1]
									\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、高斯混合成分个数$k$
									\ENSURE 簇划分$\mathcal{C}=\{C_1,C_2,\dots,C_k\}$
									\STATE 初始化高斯混合分布的模型参数$\{(\alpha_i,\bm{\mu}_i,\bm{\Sigma}_i)\mid 1\le i\le k\}$; \\
									\REPEAT
										\FOR{$j=1,2,\dots,m$}
											\STATE 计算$\bm{x}_j$由各混合成分生成的后验概率，即$\gamma_{ji}=p_{\mathcal{M}}(z_j=i\mid\bm{x}_j)(1\le i\le k)$; \\
										\ENDFOR
										\FOR{$i=1,2,\dots,k$}
											\STATE 计算新均值向量：$\bm{\mu}_i'=\frac{\sum_{j=1}^{m}\gamma_{ji}\bm{x}_j}{\sum_{j=1}^{m}\gamma_{ji}}$; \\
											\STATE 计算新协方差矩阵：$\bm{\Sigma}_i'=\frac{\sum_{j=1}^{m}\gamma_{ji}(\bm{x}_j-\bm{\mu}_i')(\bm{x}_j-\bm{\mu}_i')^T}{\sum_{j=1}^{m}\gamma_{ji}}$; \\
											\STATE 计算新混合系数：$\alpha_i'=\frac{\sum_{j=1}^{m}\gamma_{ji}}{m}$; \\
										\ENDFOR
										\STATE 将模型参数$\{(\alpha_i,\bm{\mu}_i,\bm{\Sigma}_i)\mid 1\le i\le k\}$更新为$\{(\alpha_i',\bm{\mu}_i',\bm{\Sigma}_i')\mid 1\le i\le k\}$; \\
									\UNTIL{满足停止条件}
									\STATE $C_i=\emptyset(1\le i\le k)$; \\
									\FOR{$j=1,2,\dots,m$}
										\STATE 根据$\lambda_j=\arg\max_{i\in\{1,2,\dots,k\}}\gamma_{ji}$确定$\bm{x}_j$的簇标记$\lambda_j$; \\
										\STATE 将$\bm{x}_j$划入相应的簇：$C_{\lambda_j}=C_{\lambda_j}\cup\{\bm{x}_j\}$; \\
									\ENDFOR
								\end{algorithmic} 
							\end{algorithm}
						\end{itemize}
				\subsection{密度聚类}
					\begin{itemize}
						\item 密度聚类算法从样本密度的角度考察样本之间的可连接性，基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
						\item DBSCAN算法基于一组邻域参数$(\epsilon,MinPts)$来刻画样本分布的紧密程度\begin{itemize}
							\item $\epsilon-$邻域：$N_\epsilon(\bm{x}_j)=\{\bm{x}_i\in D\mid\mathrm{dist}(\bm{x}_i,\bm{x}_j)\le\epsilon\}$
							\item 核心对象：$|N_\epsilon(\bm{x}_j)|\ge MinPts$ $\rightarrow$ $\bm{x}_j$是一个核心对象
							\item $\bm{x}_j$位于$\bm{x}_i$的$\epsilon-$邻域中 $\cap$ $\bm{x}_i$是核心对象 $\rightarrow$ $\bm{x}_j$由$\bm{x}_i$密度直达
							\item 对$\bm{x}_i$与$\bm{x}_j$若存在样本序列$\bm{p}_1,\bm{p}_2,\dots,\bm{p}_n$，其中$\bm{p}_1=\bm{x}_i,\bm{p}_n=\bm{x}_j$，且$\bm{p}_{i+1}$由$\bm{p}_i$密度直达 $\rightarrow$ $\bm{x}_j$由$\bm{x}_i$密度可达
							\item 对$\bm{x}_i$与$\bm{x}_j$，若存在$\bm{x}_k$使得$\bm{x}_i$与$\bm{x}_j$均由$\bm{x}_k$密度可达 $\rightarrow$ $\bm{x}_i$与$\bm{x}_j$密度相连
							\item 簇：由密度可达关系导出的最大的密度相连样本集合，满足``连接性''（簇中任意两个样本密度相连）和``最大性''（簇中任意一个样本密度可达的样本都在该簇中）
						\end{itemize}
						\item 算法描述\begin{algorithm}
							\caption{DBSCAN算法}
							\begin{algorithmic}[1]
								\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、邻域参数$(\epsilon,MinPts)$
								\ENSURE 簇划分$\mathcal{C}=\{C_1,C_2,\dots,C_k\}$
								\STATE 初始化核心对象集合：$\Omega = \emptyset$; \\
								\FOR{$j=1,2,\dots,m$}
									\STATE 确定样本$\bm{x}_j$的$\epsilon$-邻域$N_\epsilon(\bm{x}_j)$; \\
									\IF{$|N_\epsilon(\bm{x}_j)|\ge MinPts$}
										\STATE 将样本$\bm{x}_j$加入核心对象集合：$\Omega = \Omega\cup\{\bm{x}_j\}$; \\
									\ENDIF
								\ENDFOR
								\STATE 初始化聚类簇数和未访问样本集合：$k=0,\quad \Gamma = D$;\\
								\WHILE{$\Omega\neq\emptyset$}
									\STATE 记录当前未访问样本集合：$\Gamma_{\mathrm{old}}=\Gamma$; \\
									\STATE 随机选取一个核心对象$\bm{o}\in\Omega$，初始化队列$Q=\langle\bm{o}\rangle$; \\
									\STATE $\Gamma=\Gamma\backslash\{\bm{o}\}$; \\
									\WHILE{$Q\neq\emptyset$}
										\STATE 取出队列$Q$中的某个样本$\bm{q}$; \\
										\IF{$|N_\epsilon(\bm{q})|\ge MinPts$}
											\STATE 令$\Delta = N_\epsilon(\bm{q})\cap\Gamma$; \\
											\STATE 将$\Delta$中的样本加入队列$Q$; \\
											\STATE $\Gamma = \Gamma\backslash\Delta$; \\
										\ENDIF
									\ENDWHILE
									\STATE $k=k+1$，生成聚类簇$C_k=\Gamma_{\mathrm{old}}\backslash\Gamma$; \\
									\STATE $\Omega = \Omega\backslash C_k$; \\
								\ENDWHILE
							\end{algorithmic} 
						\end{algorithm}
					\end{itemize}
				\subsection{层次聚类}
					\begin{itemize}
						\item AGNES算法：自底向上层次聚类。先将每个样本视作一个初始聚类簇，再不断合并距离最近的两个聚类簇，达到预设的聚类簇个数。
						\item 聚类簇之间的距离计算\begin{align*}
							& \textrm{最小距离：}d_{\mathrm{min}}(C_i,C_j)=\min\limits_{\bm{x}\in C_i,\bm{z}\in C_j}\mathrm{dist}(\bm{x},\bm{z}) \\
							& \textrm{最大距离：}d_{\mathrm{max}}(C_i,C_j)=\max\limits_{\bm{x}\in C_i,\bm{z}\in C_j}\mathrm{dist}(\bm{x},\bm{z}) \\
							& \textrm{平均距离：}d_{\mathrm{avg}}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{\bm{x}\in C_i}^{}\sum_{\bm{z}\in C_j}^{}\mathrm{dist}(\bm{x},\bm{z})
						\end{align*}
						\item 算法描述\begin{algorithm}
							\caption{AGNES算法}
							\begin{algorithmic}[1]
								\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、簇距离度量函数$d$、聚类簇数$k$.
								\ENSURE 簇划分$\mathcal{C}=\{C_1,C_2,\dots,C_k\}$
								\FOR{$j=1,2,\dots,m$}
									\STATE $C_j=\{\bm{x}_j\}$; \\
								\ENDFOR
								\FOR{$i=1,2,\dots,m$}
									\FOR{$j=i+1,\dots,m$}
										\STATE $M(j,i)=M(i,j)=d(C_i,C_j)$; \\
									\ENDFOR
								\ENDFOR
								\STATE 设置当前聚类簇个数：$q=m$; \\
								\WHILE{$q>k$}
									\STATE 找出距离最近的两个聚类簇$C_{i^*}$和$C_{j^*}$; \\
									\STATE 合并$C_{i^*}$和$C_{j^*}$：$C_{i^*}=C_{i^*}\cup C_{j^*}$; \\
									\FOR{$j=j^*+1, j^*+2, \dots, q$}
										\STATE 将聚类簇$C_j$重编号为$C_{j-1}$; \\
									\ENDFOR
									\STATE 删除距离矩阵$M$的第$j^*$行与第$j^*$列; \\
									\FOR{$j=1,2,\dots,q-1$}
										\STATE $M(j,i^*)=M(i^*,j)=d(C_{i^*}, C_j)$; \\
									\ENDFOR
									\STATE $q = q-1$; \\
								\ENDWHILE
							\end{algorithmic} 
						\end{algorithm}
					\end{itemize}
			\section{降维与度量学习}
				\subsection{$k$近邻学习}
					\begin{itemize}
						\item 机制：给定测试样本，基于某种距离度量找出训练集中与其最靠近的$k$个训练样本，并基于它们采用投票法或平均法进行预测。
						\item 是一种``懒惰学习''（训练时间开销为零，收到测试样本后才进行处理，相对于``急切学习''）。
						\item 最近邻分类器的泛化错误率不超过贝叶斯最优分类器的两倍。
					\end{itemize}
				\subsection{低维嵌入}
					\begin{itemize}
						\item 密采样：任意测试样本$\bm{x}$附近任意小的$\delta$距离范围内总能找到一个训练样本。若属性维数过多，满足密采样条件所需的样本过于巨大，导致数据样本稀疏、距离计算困难，引起``维数灾难''。
						\item 降维：通过某种数学变换将原始高维属性空间转变为一个低维子空间。
						\item 多维缩放（MDS）：设$m$个样本在原始空间的距离矩阵为$\mathbf{D}\in\mathbb{R}^{m\times m}$，其中第$i$行第$i$列为样本$\bm{x}_i$到$\bm{x}_j$的距离。目标是获得样本在$d'$维空间的表示$\mathbf{Z}\in\mathbb{R}^{d'\times m},d'\le d$，且任意两个样本在$d'$维空间中的欧氏距离等于原始空间中的距离，即$||\bm{z}_i-\bm{z}_j||=dist_{ij}$。\begin{algorithm}
							\caption{MDS算法}
							\begin{algorithmic}[1]
								\REQUIRE 距离矩阵$\mathbf{D}\in\mathbb{R}^{m\times m}$，其元素$dist_{ij}$为样本$\bm{x}_i$到$\bm{x}_j$的距离、低维空间维数$d'$
								\ENSURE 矩阵$\tilde{\mathbf{V}}\tilde{\bm{\Lambda}}^{1/2}\in\mathbb{R}^{m\times d'}$，每行是一个样本的低维坐标
								\STATE 计算$dist_{i\cdot}^2=\frac{1}{m}\sum_{j=1}^{m}dist_{ij}^2$及$dist_{\cdot j}^2,dist_{\cdot\cdot}^2$; \\
								\STATE 根据$b_{ij}=-\frac{1}{2}(dist_{ij}^2-dist_{i\cdot}^2-dist_{\cdot j}^2+dist(\cdot\cdot)^2)$计算矩阵$\mathbf{B}$; \\
								\STATE 对矩阵$\mathbf{B}$做特征值分解; \\
								\STATE 取$\tilde{\bm{\Lambda}}$为$d'$个最大特征值所构成的对角矩阵，$\tilde{\mathbf{V}}$为相应的特征向量矩阵; \\
							\end{algorithmic} 
						\end{algorithm}
						\item 线性降维方法：给定$d$维空间的样本$\mathbf{X}=(\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m)\in\mathbb{R}^{d\times m}$，变换之后得到$d'\le d$维空间中的样本\[\mathbf{Z}=\mathbf{W}^T\mathbf{X}\]其中$\mathbf{W}\in\mathbb{R}^{d\times d'}$是变换矩阵，$\mathbf{Z}\in\mathbb{R}^{d'\times m}$是样本在新空间中的表达。
					\end{itemize}
				\subsection{主成分分析}
					\begin{itemize}
						\item 对于正交属性空间中的样本点，若存在一个超平面，满足``最近重构性''（样本点到这个超平面的距离都足够近）、``最大可分性''（样本点在这个超平面上的投影能尽可能分开），可分别从这两点推导出主成分分析。
						\item 设投影变换后得到的新坐标系为$W=(\bm{w}_1,\bm{w}_2,\dots,\bm{w}_{d'})$，则PCA的优化目标为\begin{align*}
							& \max\limits_{\mathbf{W}} \quad\mathrm{tr}(\mathbf{W}^T\mathbf{XX}^T\mathbf{W})\\
							& \mathrm{s.t.} \quad\mathbf{W}^T\mathbf{W}=\mathbf{W}
						\end{align*}
						\item 算法描述\begin{algorithm}
							\caption{PCA算法}
							\begin{algorithmic}[1]
								\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、低维空间维数$d'$
								\ENSURE 投影矩阵$\mathbf{W}^*=(\bm{w}_1,\bm{w}_2,\dots,\bm{w}_{d'})$
								\STATE 对所有样本进行中心化：$\bm{x}_i\leftarrow\bm{x}_i-\frac{1}{m}\sum_{i=1}^{m}\bm{x}_i$; \\
								\STATE 计算样本的协方差矩阵：$\mathbf{X}\mathbf{X}^T$; \\
								\STATE 对协方差矩阵$\mathbf{XX}^T$做特征值分解; \\
								\STATE 取最大的$d'$个特征值所对应的特征向量$\bm{w}_1,\bm{w}_2,\dots,\bm{w}_{d'}$; \\
							\end{algorithmic} 
						\end{algorithm}
						\item $d'$值可由用户指定，也可以通过kNN+交叉验证自动取值，也可取使得$\sum_{i=1}^{d'}\lambda_i/\sum_{i=1}^{d}\lambda_i\ge t$的最小$d'$值。
						\item 降维（丢弃$d-d'$个特征值的特征向量）的意义：增大采样密度、减小噪声影响。
					\end{itemize}
				\subsection{核化线性降维}
					\begin{itemize}
						\item 核主成分分析（KPCA）：基于核技巧对PCA进行核化，实现非线性降维。
						\item KPCA的过程\begin{enumerate}
							\item 由PCA中的$\mathbf{XX}^T\bm{w}_i=\lambda_i\bm{w}_i$，设$\bm{z}_i$是样本点$\bm{x}_i$在高维特征空间的像，得$(\sum_{i=1}^{m}\bm{z}_i\bm{z}_i^T)\bm{w}_j=\lambda_j\bm{w}_j$且\[\bm{w}_i=\sum_{i=1}^{m}\bm{z}_i\frac{\bm{z}_i^T\bm{w}_j}{\lambda_j}=\sum_{i=1}^{m}\bm{z}_i\alpha_i^j\]
							\item 假设$\bm{z}_i$是由原始属性空间中的样本点$\bm{x}_i$通过映射$\phi$产生，则\[\bigg(\sum_{i=1}^{m}\phi(\bm{x}_i)\phi(\bm{x}_i)^T\bigg)\bm{w}_j=\lambda_j\bm{w}_j\]\[\bm{w}_j=\sum_{i=1}^{m}\phi(\bm{x}_i)\alpha_i^j\]
							\item 引入核函数\[\kappa(\bm{x}_i,\bm{x}_j)=\phi(\bm{x}_i)^T\phi(\bm{x}_j)\]\[\mathbf{K}\bm{\alpha}^j=\lambda_j\bm{\alpha}^j\]取$\mathbf{K}$最大的$d'$个特征值所对应的特征向量即可。
							\item 对新样本$\bm{x}$，其投影后的第$j$维坐标为\[z_j=\bm{w}_j^T\phi(\bm{x})=\sum_{i=1}^{m}\alpha_i^j\phi(\bm{x}_i)^T\phi(\bm{x})=\sum_{i=1}^{m}\alpha_i^j\kappa(\bm{x}_i,\bm{x})\]
						\end{enumerate}
					\end{itemize}
				\subsection{流形学习}
				
					流形在局部具有欧氏空间的性质，能用欧氏距离进行计算。可以在局部建立降维映射关系。
					\subsubsection{等度量映射}
						\begin{itemize}
							\item 等度量映射（Isomap）：低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性。计算``测地线''距离时，可以利用流形在局部上与欧氏空间同胚这一性质，对每个点基于欧氏距离找出近邻点，然后建立一个近邻连接图，求两点之间最短路径即可。（Dijkstra算法等）
							\item 算法描述\begin{algorithm}
								\caption{Isomap算法}
								\begin{algorithmic}[1]
									\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、近邻参数$k$、低维空间维数$d'$
									\ENSURE 样本集$D$在低维空间的投影$Z=\{\bm{z}_1,\bm{z}_2,\dots,\bm{z}_m\}$
									\FOR{$i=1,2,\dots,m$}
										\STATE 确定$\bm{x}_i$的$k$近邻; \\
										\STATE $\bm{x}_i$与$k$近邻点之间的距离设置为欧氏距离，与其他点的距离设置为无穷大; \\
									\ENDFOR
									\STATE 调用最短路径算法计算任意两样本点之间的距离$\mathrm{dist}(\bm{x}_i,\bm{x}_j)$; \\
									\STATE 将$\mathrm{dist}(\bm{x}_i,\bm{x}_j)$作为MDS算法的输入; \\
									\RETURN MDS算法的输出
								\end{algorithmic} 
							\end{algorithm}
							\item 新样本映射到低维空间的权宜之计：将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器对新样本的低维空间进行预测。
						\end{itemize}
					\subsubsection{局部线性嵌入}
						\begin{itemize}
							\item 局部线性嵌入（LLE）：试图保持邻域内样本之间的线性关系。希望诸如$\bm{x}_i=w_{ij}\bm{x}_j+w_{ik}\bm{x}_k+w_{il}\bm{x}_l$在低维空间中得以保持。
							\item LLE操作过程：\begin{enumerate}
								\item 为每个样本$\bm{x}_i$找到其近邻下标集合$Q_i$，再计算基于$Q_i$中的样本点对$\bm{x}_i$进行线性重构的系数$\bm{w}_i$\begin{align*}
									& \min\limits_{\bm{w}_1,\bm{w}_2,\dots,\bm{w}_m}\quad\sum_{i=1}^{m}\bigg|\bigg|\bm{x}_i-\sum_{j\in Q_i}^{}w_{ij}\bm{x}_j\bigg|\bigg|_2^2\\
									& \mathrm{s.t.}\quad\sum_{j\in Q_i}^{}w_{ij}=1
								\end{align*}
								\item 在低维空间中保持$\bm{w}_i$不变，于是$\bm{x}_i$对应的低维空间坐标$\bm{z}_i$通过下式求解\[\min\limits_{\bm{z}_1,\bm{z}_2,\dots,\bm{z}_m}\sum_{i=1}^{m}\bigg|\bigg|\bm{z}_i-\sum_{j\in Q_i}^{}w_{ij}\bm{z}_j\bigg|\bigg|_2^2\]
								\item 令$\mathbf{Z}=(\bm{z}_1,\bm{z}_2,\dots,\bm{z}_m)\in\mathbb{R}^{d'\times m}$及$(\mathbf{W})_{ij}=w_ij$\[\mathbf{M}=(\mathbf{I}-\mathbf{W})^{\textrm{T}}(\mathbf{I}-\mathbf{W})\]于是优化目标化为\begin{align*}
									& \min\limits_{\mathbf{Z}}\quad\mathrm{tr}(\mathbf{ZMZ}^{\textrm{T}}) \\
									& \mathrm{s.t.}\quad \mathbf{ZZ}^{\textrm{T}}=\mathbf{I}
								\end{align*}
								\item 对$\mathbf{M}$进行特征值分解，最小的$d'$个特征值所对应的特征向量组成的矩阵为$\mathbf{Z}^{\textrm{T}}$。
							\end{enumerate}
							\item 算法描述\begin{algorithm}
								\caption{LLE算法}
								\begin{algorithmic}[1]
									\REQUIRE 样本集$D=\{\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m\}$、近邻参数$k$、低维空间维数$d'$
									\ENSURE 样本集$D$在低维空间的投影$Z=\{\bm{z}_1,\bm{z}_2,\dots,\bm{z}_m\}$
									\FOR{$i=1,2,\dots,m$}
										\STATE 确定$\bm{x}_i$的$k$近邻; \\
										\STATE 求得$w_{ij},j\in Q_i$; \\
										\STATE 对于$j\notin Q_i$，令$w_{ij}=0$; \\
									\ENDFOR
									\STATE 根据$\mathbf{M}=(\mathbf{I}-\mathbf{W})^{\textrm{T}}(\mathbf{I}-\mathbf{W})$求出$\mathbf{M}$; \\
									\STATE 对$\mathbf{M}$进行特征值分解; \\
									\RETURN $\mathbf{M}$的最小$d'$个特征值对应的特征向量
								\end{algorithmic} 
							\end{algorithm}
						\end{itemize}
				\subsection{度量学习}
					\begin{itemize}
						\item 距离度量模型的推广\begin{enumerate}
							\item 若每个维度等权重，对两个$d$维样本$\bm{x}_i$和$\bm{x}_j$，平方欧氏距离为\[\mathrm{dist}_{\mathrm{ed}}^2(\bm{x}_i,\bm{x}_j)=||\bm{x}_i-\bm{x}_j||_2^2=dist_{ij,1}^2+dist_{ij,2}^2+\dots+dist_{ij,d}^2\]
							\item 若不同属性的权重不同，引入属性权重$\bm{w}$。$w_i\ge0$，$\mathbf{W}=\mathrm{diag}(\bm{w})$是一个对角矩阵，$(\mathbf{W})_{ii}=w_i$。\begin{align*}
								\mathrm{dist}_{\mathrm{wed}}^2(\bm{x}_i,\bm{x}_j) = & ||\bm{x}_i-\bm{x}_j||_2^2 \\
								= & w_1\cdot dist_{ij,1}^2+w_2\cdot dist_{ij, 2}^2 +\dots +w_d\cdot dist_{ij,d}^2\\
								= & (\bm{x}_i-\bm{x}_j)^{\textrm{T}}\mathbf{W}(\bm{x}_i-\bm{x}_j)
							\end{align*}
							\item 若属性之间相关，则$\mathbf{W}$被替换为半正定对称矩阵$\mathbf{M}$，得到``马氏距离''为\[\mathrm{dist}_{\mathrm{mah}}^2=(\bm{x}_i-\bm{x}_j)^{\textrm{T}}\mathbf{M}(\bm{x}_i-\bm{x}_j)=||\bm{x}_i-\bm{x}_j||_\mathbf{M}^2\]度量学习就是对度量矩阵$\mathbf{M}$进行学习。
						\end{enumerate}
						\item 近邻成分分析（NCA）：对于任意样本$\bm{x}_j$，其对$\bm{x}_i$分类结果影响的概率为\[p_{ij}=\frac{\exp\big(-||\bm{x}_i-\bm{x}_j||_{\mathbf{M}}^2\big)}{\sum_{l}^{}\exp\big(-||\bm{x}_i-\bm{x}_l||_{\mathbf{M}}^2\big)}\]以留一法正确率最大化为目标，$\bm{x}_i$留一法正确率为\[p_i=\sum_{j\in\Omega_i}^{}p_{ij}\]其中$\Omega_i$表示与$\bm{x}_i$属于相同类别的样本的下标集合。整个样本集的留一法正确率：\[\sum_{i=1}^{m}p_i=\sum_{i=1}^{m}\sum_{j\in\Omega_i}^{}p_{ij}\]考虑$\mathbf{M}=\mathbf{PP}^{\textrm{T}}$，则NCA的优化目标为\[\min\limits_{\mathbf{P}}\quad1-\sum_{i=1}^{m}\sum_{j\in\Omega_i}^{}\frac{\exp\big(-||\mathbf{P}^{\textrm{T}}\bm{x}_i-\mathbf{P}^{\textrm{T}}\bm{x}_j||_2^2\big)}{\sum_{l}^{}\exp\big(-||\mathbf{P}^{\textrm{T}}\bm{x}_i-\mathbf{P}^{\textrm{T}}\bm{x}_l||_2^2\big)}\]
						\item 若已知某些样本相似、某些样本不相似，定义``必连''约束集合$\mathcal{M}$与``勿连''约束集合$\mathcal{C}$。其中$(\bm{x}_i,\bm{x}_j)\in\mathcal{M}$表示$\bm{x}_i$与$\bm{x}_j$相似，$(\bm{x}_i,\bm{x}_k)\in\mathcal{C}$表示$\bm{x}_i$与$\bm{x}_k$不相似。构造如下凸优化问题\begin{align*}
						\min\limits_{\mathbf{M}}\quad & \sum_{(\bm{x}_i,\bm{x}_j)\in\mathcal{M}}^{}||\bm{x}_i-\bm{x}_j||_{\mathbf{M}}^2 \\
						\mathrm{s.t.}\quad & \sum_{(\bm{x}_i,\bm{x}_k)\in\mathcal{C}}^{}||\bm{x}_i-\bm{x}_k||_{\mathbf{M}}\ge1\\
						& \mathbf{M}\succeq0
						\end{align*}
					\end{itemize}
			\section{特征选择与稀疏学习}
				\subsection{子集搜索与评价}
					\begin{itemize}
						\item 特征：属性；相关特征：对当前学习任务有用的属性；无关特征：对当前学习任务用处不大的属性；特征选择：从给定的特征集合中选择出相关特征子集的过程。
						\item 特征选择与降维是处理高维数据的两大主流技术。
						\item 冗余特征：包含的信息能从其它特征推演出来的一类特征。
						\item 没有任何领域知识作为先验假设 $\rightarrow$ 遍历所有的子集 $\rightarrow$ 组合爆炸
						\item 两个关键环节\begin{enumerate}
							\item 子集搜索：贪心策略（仅考虑使本轮选定集最优）\begin{itemize}
								\item 前向搜索：将每个特征看作一个候选子集，对$d$个候选单特征子集进行评价，将最优的单特征添加进去，然后逐渐从剩余的候选单特征子集中择优添加，直到添加后的子集不如上一轮选定集，此时将上一轮选定的集合作为特征选择结果。
								\item 后向搜索：从完整的特征集合开始逐渐去掉特征。
								\item 双向搜索：每一轮逐渐增加选定相关特征同时减少无关特征。
							\end{itemize}
							\item 子集评价：基于信息增益。假定样本属性均为离散型。对属性子集$A$，假定根据其取值将$D$分成了$V$个子集$\{D^1,D^2,\dots,D^V\}$，则属性子集$A$的信息增益为\[\mathrm{Gain}(A)=\mathrm{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\]\[\mathrm{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k\]信息增益越大，则该特征子集包含的有助于分类的信息越多。扩展：只要能估算样本标记信息对$D$的真实划分与特征子集对$D$的划分这两者的差异即可。
						\end{enumerate}
					\end{itemize}
				\subsection{过滤式选择}
					\begin{itemize}
						\item 先对数据集进行特征选择，再训练学习器。
						\item Relief方法：利用``相关统计量''度量特征的重要性。\begin{enumerate}
							\item 对于每个示例$\bm{x}_i$，先在$\bm{x}_i$的同类样本中寻找最近邻$\bm{x}_{i,\mathrm{nh}}$，即为``猜中近邻''。
							\item 再从$\bm{x}_i$的异类样本中寻找其最近邻$\bm{x}_{i,\mathrm{nm}}$，即为``猜错近邻''。
							\item 相关统计量在属性$j$的分量为\[\delta^j=\sum_{i}^{}-\mathrm{diff}(x_i^j,x_{i,\mathrm{nh}}^j)^2+\mathrm{diff}(x_i^j,x_{i,\mathrm{nm}}^j)^2\]若属性$j$为离散型，则$\mathrm{diff}(x_a^j,x_b^j)$为1或0，否则为$|x_a^j-x_b^j|$，此时每个属性上的取值需规范化到$[0,1]$区间。
							\item Relief在数据集上多次采样并相应地估计相关统计量。
						\end{enumerate}
						\item Relief-F方法：处理多分类问题。设$p_l$为第$l$类样本在数据集$D$中所占的比例。\[\delta^j=\sum_{i}^{}-\mathrm{diff}(x_i^j,x_{i,\mathrm{nh}}^j)^2+\sum_{l\neq k}^{}\big(p_l\times \mathrm{diff}(x_i^j,x_{i,\mathrm{i,l,\mathrm{nm}}}^j)^2\big)\]
					\end{itemize}
				\subsection{包裹式选择}
					\begin{itemize}
						\item 包裹式特征选择：直接把最终将要使用的学习器的性能作为特征子集的评价准则。计算开销很大，但从最终学习器性能来看比过滤式特征选择更好。
						\item LVW算法：在Las Vegas方法框架下使用随机策略进行子集搜索，以最终分类器的误差为特征子集评价准则。\begin{framed}
							拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解一定就是正确的解，但有时用拉斯维加斯算法找不到解。而蒙特卡洛方法一定会给出解，虽然给出的解未必满足要求。若无时间限制，则两者都能给出满足要求的解。
						\end{framed}
						\begin{algorithm}
							\caption{LLE算法}
							\begin{algorithmic}[1]
								\REQUIRE 数据集$D$、特征集$A$、学习算法$\mathfrak{L}$、停止条件控制参数$T$
								\ENSURE 特征子集$A^*$
								\STATE $E=\infty$; \\
								\STATE $d=|A|$; \\
								\STATE $A^*=A$; \\
								\STATE $t=0$; \\
								\WHILE{$t<T$}
									\STATE 随机产生特征子集$A'$; \\
									\STATE $d'=|A'|$; \\
									\STATE $E'=\mathrm{CrossValidation}(\mathfrak{L}(D^{A'}))$; \\
									\IF{$(E'<E)\vee((E'=E)\wedge(d'<d))$}
										\STATE $t=0$; \\
										\STATE $E=E'$; \\
										\STATE $d=d'$; \\
										\STATE $A^*=A'$; \\
									\ELSE
										\STATE $t=t+1$; \\
									\ENDIF
								\ENDWHILE
							\end{algorithmic} 
						\end{algorithm}
					\end{itemize}
				\subsection{嵌入式选择与L$_1$正则化}
					\begin{itemize}
						\item 嵌入式特征选择：将特征选择过程与学习器训练过程融合，在同一优化过程中完成。
						\item 线性回归模型中，使用$\mathrm{L}_1$范数正则化，比$\mathrm{L}_2$范数正则化更易于获得稀疏解，即有更多的分量为零。此时的优化目标称为LASSO：\[\min\limits_{\bm{w}}\sum_{i=1}^{m}(y_i-\bm{w}^{\textrm{T}}\bm{x}_i)^2+\lambda||\bm{w}||_1\]如此求解$\mathrm{L}_1$范数正则化的结果是得到了仅采用一部分初始特征的模型，即为一种嵌入式特征选择方法。
						\item 可用近端梯度下降（PGD）求解。
					\end{itemize}
				\subsection{稀疏表示与字典学习}
					\begin{itemize}
						\item 稀疏矩阵：存在很多零元素的矩阵（不一定是整行整列）
						\item 字典学习/稀疏编码：为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，简化学习任务，降低模型复杂度。
						\item 字典学习最简形式：\[\min\limits_{\mathbf{B},\bm{\alpha}_i}\sum_{i=1}^{m}||\bm{x}_i-\mathbf{B}\bm{\alpha}_i||_2^2+\lambda\sum_{i=1}^{m}||\bm{\alpha}_i||_1\]
						其中$\textbf{B}\in\mathbb{R}^{d\times k}$为字典矩阵，$k$为字典词汇量，$\bm{\alpha}_i\in\mathbb{R}^k$为样本$\bm{x}_i\in\mathbb{R}^d$的稀疏表示。第一项使$\bm{\alpha}_i$更好地重构$\bm{x}_i$，第二项使$\bm{\alpha}_i$尽量稀疏。
						\item 求解方法：变量交替优化\begin{enumerate}
							\item 先固定字典$\mathbf{B}$，按分量展开为\[\min\limits_{\bm{\alpha}_i}||\bm{x}_i-\mathbf{B}\bm{\alpha}_i||_2^2+\lambda||\bm{\alpha}_i||_1\]参照LASSO的解法求解。
							\item 以$\bm{\alpha}_i$为初值来更新字典$\mathbf{B}$。目标函数化为\[\min\limits_{\mathbf{B}}||\mathbf{X}-\mathbf{BA}||_{F}^2\]其中$\mathbf{X}=(\bm{x}_1,\bm{x}_2,\dots,\bm{x}_m)\in\mathbb{R}^{d\times m}$，$A=(\bm{\alpha}_1,\bm{\alpha}_2,\dots,\bm{\alpha}_m)\in\mathbb{R}^{k\times m}$，$||\cdot||_F$是Frobenius范数。可用基于逐列更新策略的KSVD求解。
						\end{enumerate}
					\end{itemize}
				\subsection{压缩感知}
					\begin{itemize}
						\item 压缩感知模型：假定有长度为$m$的离散信号$\bm{x}$，不妨假定以远小于奎奈斯特采样定理要求的采样率进行采样，得到长度为$n$的采样后信号$\bm{y}$，有$n\ll m$且$\bm{y}=\bm{\Phi x}$，其中$\Phi\in\mathbb{R}^{n\times m}$是对信号$\bm{x}$的测量矩阵。由$\bm{y}$和$\bm{\Phi}$反推$\bm{x}$，可令$\bm{x}=\bm{\Psi s}$，其中$\bm{s}$具有稀疏性。此时$\bm{\Psi}$为稀疏基，$\mathbf{A}=\bm{\Phi\Psi}$作用类似于字典。
						\item 矩阵补全技术\begin{align*}
							\min\limits_{\mathbf{X}}\quad & \mathrm{rank}(\mathbf{X}) \\
							\mathrm{s.t.}\quad & (\mathbf{X})_{ij}=(\mathbf{A})_{ij},\quad (i,j)\in\Omega
						\end{align*}
						其中$\mathbf{X}$表示需要恢复的稀疏信号。$\Omega$是$\mathbf{A}$中有数据元素的下标集合。这是一个NP难问题。可转化最小化矩阵核范数再通过半正定规划求解。
					\end{itemize}
			\section{计算学习理论}
			\section{半监督学习}
				
			\section{概率图模型}
			\section{规则学习}
			\section{强化学习}
			
\end{document}