esl_notes_compile.lyx

#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass article
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding utf8
\fontencoding global
\font_roman 黑体
\font_sans 仿宋
\font_typewriter 楷体
\font_default_family default
\use_non_tex_fonts true
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
≪统计学习精要(TheElementsofStatisticalLearning)≫课堂笔记
\end_layout

\begin_layout Section
导论和课程大纲
\end_layout

\begin_layout Standard
\align left
前两天微博上转出来的，复旦计算机学院的吴立德吴老师在开
\emph on
《统计学习精要(TheElementsofStatisticalLearning)
\emph default
》这门课，还在张江...大牛的课怎能错过，果断请假去蹭课...为了减轻心理压力，还拉了一帮同事一起去听，eBay浩浩荡荡的十几人杀过去好不壮观！总感觉我们的人有超过复旦本身
学生的阵势，五六十人的教室坐的满满当当，壮观啊。
\end_layout

\begin_layout Standard
\align left
这本书正好前阵子一直在看，所以才会屁颠屁颠的跑过去听。确实是一本深入浅出讲dataminingmodels的好书。作者网站上提供免费的电子版下载，爽！
\begin_inset CommandInset href
LatexCommand href
name "http://www-stat.stanford.edu/~tibs/ElemStatLearn/"
target "http://www-stat.stanford.edu/~tibs/ElemStatLearn/"

\end_inset


\end_layout

\begin_layout Standard
\align left
从这周开始，如无意外我会每周更新课堂笔记。另一方面，也会加上自己的一些理解和实际工作中的感悟。此外，对于datamining感兴趣的，也可以去coursera听
课~貌似这学期开的machinelearning评价不错。我只在coursera上从众选了一门「ModelThinking」，相对来说比较简单，但是相当的优雅！
若有时间会再写写这门课的上课感受。笔记我会尽量用全部中文，但只是尽量...
\end_layout

\begin_layout Standard
\align left
------------课堂笔记开始--------
\end_layout

\begin_layout Standard
\align left
第一次上课，主要是导论，介绍这个领域的关注兴趣以及后续课程安排。对应本书的第一章。
\end_layout

\begin_layout Standard
\align left
1.统计学习是？从数据中学习知识。简单地说，我们有一个想预测的结果(outcome)，记为
\begin_inset Formula $Y$
\end_inset

，可能是离散的也可能是连续的。同时，还有一些观察到的特征(feature)，记为
\begin_inset Formula $X$
\end_inset

，
\begin_inset Formula $X$
\end_inset

既可能是一维的也可能是多维的。对于每一个观测个体，我们都会得到一个行向量
\begin_inset Formula $(x_{1},...,x_{p})$
\end_inset

，对应它的p个特征的观测值，以及一个观测到的结果值
\begin_inset Formula $y$
\end_inset

。如果总共有
\begin_inset Formula $N$
\end_inset

个个体，那么我们对于每个个体都会得到这些值，则有
\begin_inset Formula $(y_{1},...,y_{n})_{T}$
\end_inset

为观测结果的列向量以及
\begin_inset Formula $X(n*p)$
\end_inset

矩阵。这样的数据称之为训练数据集（trainingset）。这里更多是约定一些notation.
\end_layout

\begin_layout Standard
\align left
2.统计学习分类？一般说来，我们有个观测到的结果
\begin_inset Formula $Y$
\end_inset

，然后找到一个适合的模型根据
\begin_inset Formula $X$
\end_inset

预测
\begin_inset Formula $Y$
\end_inset

，这样的称之为有监督的学习（supervisedlearning）。而有些时候，
\begin_inset Formula $Y$
\end_inset

是无法观测到的，那么只是通过
\begin_inset Formula $X$
\end_inset

来学习，称之为无监督的学习（unsupervisedlearning）。这本书主要侧重有监督的学习。
\end_layout

\begin_layout Standard
\align left
3.回归和分类器。这个主要和
\begin_inset Formula $Y$
\end_inset

有关。如果
\begin_inset Formula $Y$
\end_inset

为离散，比如红黄蓝不同颜色，则称之为分类器（学习模型）；反之，若
\begin_inset Formula $Y$
\end_inset

为连续，比如身高，则称之为回归（学习模型）。这里更多只是称谓上的区别。
\end_layout

\begin_layout Standard
\align left
4.统计学习的任务？预测。通过什么来预测？学习模型（learningmodels）。按照什么来学习？需要一定的准则，比如最小均方误差MSE，适用于分类器的0-1准
则等。基于这些准则、优化过的实现方法称之为算法。
\end_layout

\begin_layout Standard
\align left
5.统计学习举例？
\end_layout

\begin_layout Standard
\align left
分类器：依据邮件发信人、内容、标题等判断是否为垃圾邮件；
\end_layout

\begin_layout Standard
\align left
回归：前列腺特异抗原(PSA)水平与癌症等因素的关系；
\end_layout

\begin_layout Standard
\align left
图形识别：手写字母的识别；
\end_layout

\begin_layout Standard
\align left
聚类：根据DNA序列判断样本的相似性，如亲子鉴定。
\end_layout

\begin_layout Standard
\align left
6.课程安排顺序？
\end_layout

\begin_layout Standard
\align left
第二章，是对于有监督的学习模型的概览。
\end_layout

\begin_layout Standard
\align left
第三章和第四章将讨论线性回归模型和线性分类器。
\end_layout

\begin_layout Standard
\align left
第五章将讨论广义线性模型（GLM）。
\end_layout

\begin_layout Standard
\align left
第六章涉及kernel方法和局部回归。
\end_layout

\begin_layout Standard
\align left
第七章是模型评价与选择。
\end_layout

\begin_layout Standard
\align left
第八章是测侧重算法，比如最大似然估计，bootstrap等。本学期预计讲到这里。所以后面的我就暂时不列出了。
\end_layout

\begin_layout Standard
\align left
目测第二节开始将变得越来越难，前阵子自学第二章痛苦不已啊...一个LASSO就折磨了我好久。当时的读书笔记见：
\begin_inset CommandInset href
LatexCommand href
name "降维模型若干感悟"
target "http://www.loyhome.com/%e9%99%8d%e7%bb%b4%e6%a8%a1%e5%9e%8b%e8%8b%a5%e5%b9%b2%e6%84%9f%e6%82%9f/"

\end_inset


\end_layout

\begin_layout Standard
\align left
--------10.15补充---------
\end_layout

\begin_layout Standard
\align left
上周写的时候只是凭着记忆，笔记没在身边。今天重新翻了翻当时记下的课堂笔记，再补充一些吧。
\end_layout

\begin_layout Standard
\align left
第九章是可加模型，即
\begin_inset Formula $f(x_{1},...,x_{p})=f(x_{1})+...+f(x_{p})$
\end_inset


\end_layout

\begin_layout Standard
\align left
第十章是boosting模型
\end_layout

\begin_layout Standard
\align left
第十一章讨论神经网络
\end_layout

\begin_layout Standard
\align left
第十二章讨论支持向量机(SupportVectorMachine)
\end_layout

\begin_layout Standard
\align left
第十三章设计原型方法(Prototype)
\end_layout

\begin_layout Standard
\align left
第十四章从有监督的学习转到无监督的学习（即有
\begin_inset Formula $X$
\end_inset

有
\begin_inset Formula $Y$
\end_inset


\begin_inset Formula $\rightarrow$
\end_inset

有
\begin_inset Formula $X$
\end_inset

无
\begin_inset Formula $Y$
\end_inset

）
\end_layout

\begin_layout Standard
\align left
第十五章讨论随机森林模型（RandomForest）
\end_layout

\begin_layout Standard
\align left
第十六章是集群学习
\end_layout

\begin_layout Standard
\align left
第十七章结构图模型
\end_layout

\begin_layout Standard
\align left
第十八章高维问题（我最近一直念叨的curseofdimensionality...今年搞笑诺贝尔奖也多少与此有关，见
\begin_inset CommandInset href
LatexCommand href
name "http://www.guokr.com/article/344117/"
target "http://www.guokr.com/article/344117/"

\end_inset

，还有一篇
\begin_inset CommandInset href
LatexCommand href
name "相关的paper"
target "http://cver.upei.ca/files/cver/04_Astrological%20associations%20and%20illness_jce.pdf"

\end_inset

）
\end_layout

\begin_layout Standard
\align left
ps.吴老师对于随机森林等等模型的评论也挺有意思的，大致是，大家都没搞清随机森林为什么效果这么好...而且这一类模型都是computatoinalintensive的，
即有一个非常简单的idea然后借助大量的计算来实现。此外，这类方法更多有“猜”的感觉，无法知道来龙去脉，在现实中显得不那么intuitive...（不像econome
trics那般致力于causality呢）。
\end_layout

\begin_layout Section
简单预测方法，OLS和KNN，统计决策理论
\end_layout

\begin_layout Standard
\align left
继续一周一次的课堂笔记:D
\end_layout

\begin_layout Standard
\align left
昨天去晚了站着听讲，感觉好好啊，注意各种集中。想想整个教室里面就是我和老师是站着的，自豪感油然而生。
\end_layout

\begin_layout Standard
\align left
第二次课讲的东西依旧比较简单，是这本书第二章的前半部分。作为一个好久之前已经预习过的孩子，我表示万分的得意（最小二乘法难道不是三四年前就学过的？话说以后我再面人
的时候，就让他推导最小二乘估计量，嘻嘻...考验一下基本功）。
\end_layout

\begin_layout Standard
\align left
------------原谅我的废话，笔记开始------------
\end_layout

\begin_layout Subsection
简单预测方法：最小二乘法（以下沿用计量经济学的习惯，简称OLS）
\end_layout

\begin_layout Standard
\align left
OLS实在是太普遍了，我就不赘述细节了。OLS的思想就是，基于已有的样本信息，找出一条直线，让预测值与真实值之间的残差平方和最小，即
\begin_inset Formula $∑_{n}(y−\hat{y})^{2}$
\end_inset

最小。其中，
\begin_inset Formula $y$
\end_inset

为真实的样本观测值（已有样本），而
\begin_inset Formula $\hat{y}$
\end_inset

是OLS的预测值。用图来讲的话，
\begin_inset Formula $X$
\end_inset

为一维向量的时候，就是用一条直线来最好的拟合各个样本点。
\end_layout

\begin_layout Standard
\align left
这里就很明显了，首先OLS假设是一条直线。那么就是一个参数模型，即我们需要假设一个未知的参数
\begin_inset Formula $β$
\end_inset

，构成一个线性方程
\begin_inset Formula $y=βx$
\end_inset

，然后再去估计β的值。然后呢，直线会有很多条，所以我们要找到一个目标——比如这里，就是最小化残差平方和RSS。换言之，我们寻找的就是最优的向量
\begin_inset Formula $\hat{\beta}$
\end_inset

使得RSS最小。
\end_layout

\begin_layout Standard
\align left
解这个最优化问题很简单，我就不重复了。最后解得的最优估计量为：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\hat{\beta}=(X'X)^{-1}X'Y
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
这里写成矩阵形式，比较简单。
\begin_inset Formula $X$
\end_inset

为一维向量的时候，可以改写成
\begin_inset Formula $∑$
\end_inset

形式，我个人不大喜欢，就不展开了。
\end_layout

\begin_layout Subsection
简单预测方法：K近邻（k nearest neighbor）
\end_layout

\begin_layout Standard
\align left
K近邻的思想就更简单了。不就是想预测某个点x对应的y么？那么就把它的邻居都找来，平均一下好了。不是有句话叫做什么“一个人的收入就大概是他的圈子收入的平均值么？”
\end_layout

\begin_layout Standard
\align left
所以
\begin_inset Formula $\hat{y}=mean(y_{i}|x_{i}\in N_{k}(x))$
\end_inset

，这里
\begin_inset Formula $N_{k}(x)$
\end_inset

表示点
\begin_inset Formula $x$
\end_inset

的K近邻。至于这个近邻怎么定义嘛，嘻嘻，很简单啊，欧几里德距离就可以嘛~
\end_layout

\begin_layout Standard
\align left
评语：吴老师对于这两个算法的直观评价是，OLS呢就是勤奋的学生，预测前先做足功课，预测的时候只要知道X，噼里啪啦一下子y就估计出来了。然而knn则是一个临时抱佛
脚的学生，预测的时候开始找自己的k近邻，然后把它们平均一下就好了。哈哈，大意如此，大家可以体会一下这种精神。我个人感觉呢，OLS属于以不变应万变的，而knn则是
见机行事的。
\end_layout

\begin_layout Subsection
统计决策理论(Statistical Decision Theory)
\end_layout

\begin_layout Standard
\align left
说了这么多，这个模型好不好到底怎么判读呢？凡事总得有个标准呢。这一系列的标准或者说准则，就是统计决策理论了。
\end_layout

\begin_layout Standard
\align left
首先呢，大致我们需要对X,Y有个分布上的描述：用
\begin_inset Formula $P(X,Y)$
\end_inset

记作向量
\begin_inset Formula $(X,Y)$
\end_inset

的联合分布，然后
\begin_inset Formula $p(X,Y)$
\end_inset

为其对应的密度函数。之后为了估计Y，我们会有很多很多模型，即各种
\begin_inset Formula $f(X)$
\end_inset

，而这些
\begin_inset Formula $f(X)$
\end_inset

组成的函数空间记为
\begin_inset Formula $F$
\end_inset

。
\end_layout

\begin_layout Standard
\align left
然后我们定义一个损失函数，比如在均方误差意义下，
\begin_inset Formula $\mathcal{L}(Y,f(X)=(Y-f(X))^{2}$
\end_inset

，这样就有了一个选择的标准——使得损失函数的期望最小：
\begin_inset Formula $EPE(f)=E(Y-f(X))^{2}=\int[y-f(x)]^{2}P(dx,dy)$
\end_inset

。接下来就是，到底在
\begin_inset Formula $F$
\end_inset

空间里面，哪一个
\begin_inset Formula $f$
\end_inset

最符合这个标准呢？
\end_layout

\begin_layout Standard
\align left
首先自然是把联合分布变为条件分布。这个idea显而易见——我们总是知道X的（原谅我吧，全中文确实比较难写，偶尔穿插英文一下 ^_^）。所以conditional
 on X，我们就有了
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
EPE(f)=\int[y-f(x)]^{2}P(dx,dy)=\intop_{x}\left\{ \intop_{y}[y-f(x)]^{2}p(y|x)dy\right\} p(x)dx
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
去解最小化问题，最终我们得到的就是在每个点
\begin_inset Formula $X$
\end_inset

上，
\begin_inset Formula $f(X)=E(y|X=x)$
\end_inset

。通俗的讲就是，对于每个点预测，把和它X向量取值一样的样本点都找出来，然后取他们的平均值就可以了。很直观的不是么？这里也有点最大似然的想法呢——比如预测一个男孩
的身高，最保险的就是把和它同龄的其他男孩的身高平均一下，不是么？
\end_layout

\begin_layout Standard
\align left
但是说来简单啊，很多时候
\begin_inset Formula $P(X,Y)$
\end_inset

都是未知的，根本无法计算嘛。所以只能近似：
\end_layout

\begin_layout Itemize
\align left
回忆一下knn，就是放松了两点：1) 
\begin_inset Formula $x_{k}$
\end_inset

取的是
\begin_inset Formula $x$
\end_inset

的近邻，而不一定是
\begin_inset Formula $x$
\end_inset

； 2)用样本平均数代替了期望 
\end_layout

\begin_layout Itemize
\align left
而OLS呢，也是最后在
\begin_inset Formula $E(\beta)=E[(X'X)^{-1}X'Y]$
\end_inset

这里，用样本平均代替了期望。
\end_layout

\begin_layout Standard
\align left
近似嘛，自然有好的近似和不好的近似。很显然的，当样本比较大、尤其是比较密集的时候，x的邻居应该都离x很近，所以这个误差可以减小；此外，当样本很大的时候，根据大数
定律，平均数收敛于期望。所以，这两种算法应该说，都在大样本下会有更好的效果。
\end_layout

\begin_layout Subsection
模型选择、训练误差与测试误差、过拟合
\end_layout

\begin_layout Standard
\align left
这里讲的比较简单。模型选择就是
\begin_inset Formula $F$
\end_inset

的选择，即选择哪一类函数空间
\begin_inset Formula $F$
\end_inset

，然后再其中找估计最优的
\begin_inset Formula $f(X)$
\end_inset

。很显然，如果只有若干个有限的样本，我们总能把各个样本用直线或者曲线依次连起来，这样的话就有无数个
\begin_inset Formula $f$
\end_inset

可以作为此问题的解。显然这不是我们想要的——这样的称为“不设定问题”，即可能无解、可能多个解、还可能因为一点点
\begin_inset Formula $X$
\end_inset

的变化导致整个解的解答变化。因此我们需要先设定一个解的类别。
\end_layout

\begin_layout Standard
\align left
训练误差：预测模型估计值与训练数据集之间的误差。RSS就是一个典型的训练误差组成的残差平方和。
\end_layout

\begin_layout Standard
\align left
测试误差：用训练集以外的测试数据集带来的误差，显然我们更关心的是测试误差——训练总能训练的很好，让损失函数期望最小，然而测试集则不一定这样。一般说来，测试误差>
训练误差。
\end_layout

\begin_layout Standard
\align left
过拟合：选择一个很复杂的
\begin_inset Formula $f$
\end_inset

，使得训练误差很小，而实际的测试误差不一定小。最极端的就是刚才说的，把训练集的点一个个依次连起来...训练误差肯定是0是不是？
\end_layout

\begin_layout Standard
\align left
我们关心的自然是怎么降低测试误差。显然这东西会跟训练误差有关，但是它还跟
\begin_inset Formula $f$
\end_inset

的复杂度有关。最最棘手的就是，
\begin_inset Formula $f$
\end_inset

的复杂度是一个难以衡量的问题。早期的研究有用自由度来衡量这个复杂度的，但是也不是那么的靠谱...后面的有人鼓捣出来PAC(使得近似正确的概率最大——吴老师原话)，还有
一个VC来衡量复杂度——但几乎实践中无法计算，没几个计算出来的。嗯，水很深哇。
\end_layout

\begin_layout Section
高维空间问题、线性回归方法
\end_layout

\begin_layout Standard
\align left
照例文章第一段跑题，先附上个段子（转载的哦~）：
\end_layout

\begin_layout Quotation
\align left
I hate CS people.
 They don't know linear algebra but want to teach projective geometry.
 They don't know any probability but want to use graphical models.
 They don't understand stats at all but still do machine learning like crazy.
 
\end_layout

\begin_layout Standard
\align left
喵，最近被问了好几次machine learning 和statistical learning的区别在哪里，我觉得大致如上吧。这也是为什么，对后面这个词我的好
感稍稍好于前面那个的原因...科学总是有意义的嘛，不能总是依靠强力乱猜是不是嘛。
\end_layout

\begin_layout Standard
\align left
免责声明：以下个人见解部分局限于我个人的见识和思考范围，不适用于所有场景。请大家弃糟粕取精华，不可一言全信之。
\end_layout

\begin_layout Standard
\align left
-------------笔记+随想开始------------
\end_layout

\begin_layout Subsection
高维空间问题
\end_layout

\begin_layout Standard
\align left
这一段主要是说大名鼎鼎的＂维数灾难＂。我们都知道有两个数字决定着OLS中X矩阵的大小，这就是观测数目
\begin_inset Formula $N$
\end_inset

和观测变量的个数
\begin_inset Formula $p$
\end_inset

。一般说来，我们都喜欢
\begin_inset Formula $N$
\end_inset

比较大，这样可以很容易的应用大数定律什么的。然而对于
\begin_inset Formula $p$
\end_inset

，却是既爱又恨—我们当然喜欢可以观察到个体的很多个特征，但是所谓＂乱花渐欲迷人眼＂，特征越多噪音也越多，搞不好预测的时候就会有麻烦（关于变量的选择问题，应该是下
一节课的内容。心急的可以先看看我以前的一篇
\begin_inset CommandInset href
LatexCommand href
name "自学笔记"
target "http://www.loyhome.com/%e9%99%8d%e7%bb%b4%e6%a8%a1%e5%9e%8b%e8%8b%a5%e5%b9%b2%e6%84%9f%e6%82%9f/"

\end_inset

）。
\end_layout

\begin_layout Standard
\align left
为什么维数增多的时候会麻烦呢？这里主要是随着维数增多带来的高维空间数据稀疏化问题。简单地说：
\end_layout

\begin_layout Itemize
\align left
p=1，则单位球(简化为正值的情况）变为一条[0,1]之间的直线。如果我们有N个点，则在均匀分布的情况下，两点之间的距离为1/N。其实平均分布和完全随机分布的两
两点之间平均距离这个概念大致是等价的，大家可稍微想象一下这个过程。
\end_layout

\begin_layout Itemize
\align left
p=2，单位球则是边长为1的正方形，如果还是只有N个点，则两点之间的平均距离为
\begin_inset Formula $\frac{1}{\sqrt{N}}$
\end_inset

。换言之，如果我们还想维持两点之间平均距离为1/N，那么则需
\begin_inset Formula $N^{2}$
\end_inset

个点。
\end_layout

\begin_layout Itemize
\align left
以此类题，在p维空间，N个点两两之间的平均距离为
\begin_inset Formula $N^{-1/p}$
\end_inset

，或者需要
\begin_inset Formula $N^{p}$
\end_inset

个点来维持1/N的平均距离。
\end_layout

\begin_layout Standard
\align left
由此可见，高维空间使得数据变得更加稀疏。这里有一个重要的定理：
\begin_inset Formula $N$
\end_inset

个点在
\begin_inset Formula $p$
\end_inset

为单位球内随机分布，则随着
\begin_inset Formula $p$
\end_inset

的增大，这些点会越来越远离单位球的中心，转而往外缘分散。这个定理源于各点距单位球中心距离的中间值计算公式：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
d(p,N)=(1-2^{1/N})^{1/p}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
当
\begin_inset Formula $p\rightarrow\infty$
\end_inset

时，
\begin_inset Formula $d(p,N)\rightarrow1$
\end_inset

。（很显然，当
\begin_inset Formula $N$
\end_inset

变大时，这个距离趋近于0。直观的理解就是，想象我们有一堆气体分子，
\begin_inset Formula $p$
\end_inset

变大使得空间变大，所以这些分子开始远离彼此；而
\begin_inset Formula $N$
\end_inset

变大意味着有更多气体分子进来，所以两两之间难免更挤一些。看过《三体》的，大概会觉得这个很熟悉的感觉吧...四维空间下的＂水滴＂再也不完美的无懈可击，而一张一维的纸片就
毁灭了整个地球呢。）
\end_layout

\begin_layout Standard
\align left
这个距离公式的推导就暂时不写了，好麻烦...大致是利用了各个点独立同分布的特性（完全随机情况下），把median距离变为以1/2概率大于中位数的概率集合公式，再进一步
展开为单点距离累乘公式。
\end_layout

\begin_layout Standard
\align left
比如当
\begin_inset Formula $p=10$
\end_inset

, 
\begin_inset Formula $N=500$
\end_inset

的时候， 
\begin_inset Formula $d(p,N)$
\end_inset

约为0.52，也就意味着有一半多的点离中心的距离大于1/2。
\end_layout

\begin_layout Standard
\align left
高维问题为什么是问题呢？回顾一下
\begin_inset Formula $K$
\end_inset

近邻算法，我们用
\begin_inset Formula $x$
\end_inset

的邻居来代替
\begin_inset Formula $x$
\end_inset

，这样就希望他的邻居们不要离他太远。显然高维空间使得点和点之间越来越远。所以说，
\begin_inset Formula $knn$
\end_inset

更适合小
\begin_inset Formula $p$
\end_inset

大
\begin_inset Formula $N$
\end_inset

即低维多观测量的情况，而在高维空间下可能会变得很麻烦。
\end_layout

\begin_layout Standard
\align left
这样，statistical learning的主要两个问题就总结完了：
\end_layout

\begin_layout Itemize
\align left
过拟合：为了控制预测误差，我们要选择适合的函数类。
\end_layout

\begin_layout Itemize
\align left
高维空间：随着维数的增多，我们面临着维数灾难。这对很多算法都有波及，主要体现在高维数据稀疏化。
\end_layout

\begin_layout Subsection
回归的线性方法
\end_layout

\begin_layout Standard
\align left
这里主要是一些linear regression的东西，作为被计量经济学折磨了这么多年的孩子，我表示很淡定...此外还加上我们俗称的generalized
 linear models，即GLM。一些线性变换而已，无伤大雅。
\end_layout

\begin_layout Standard
\align left
这里一定要强调的是，在这里我们亲爱的X居然不是
\series bold
随机变量
\series default
！多大的一个坑啊，我就华丽丽的掉下去了还问老师为什么无偏性不需要假设均值独立什么的...
\begin_inset Formula $X$
\end_inset

不是随机变量意味着什么呢？
\begin_inset Formula $X$
\end_inset

是人为设定或者决定的，比如我一天浇
\begin_inset Formula $200ml$
\end_inset

或者
\begin_inset Formula $500ml$
\end_inset

水，然后看对于植物生长的影响。当时我真的是想＂一口老血喷出来＂，这也太舒服了吧！要知道大多数情况下
\begin_inset Formula $X$
\end_inset

也是随机变量哇，比如身高体重什么的。如果它不是随机变量而只有扰动项是独立的随机变量的话，整个计量经济学怕是要删掉好多篇幅了呢。我想说的只有，这群搞statist
ical learning的好幸福...
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $X$
\end_inset

不是随机变量的时候，为了满足无偏性的假设，只需要扰动项不相关且期望方差存在就可以了。期望不为0不要紧，回归的时候放进去常数项就可以了。
\end_layout

\begin_layout Standard
\align left
此外，对于任意一个正定阵W，我们都可以直接在回归方程两边乘以
\begin_inset Formula $W$
\end_inset

，从而
\begin_inset Formula $\hat{\beta}=(X'W'WX)^{-1}X'W'Y$
\end_inset

。也就是说，我们可以给
\begin_inset Formula $X$
\end_inset

进行加权处理，加权矩阵
\begin_inset Formula $W$
\end_inset

之后可以进行新的OLS估计，且可能会有对应的优良性质。加权最小二乘法我就不在这里复习了，学过计量的应该很熟悉，比如处理异方差什么的。
\end_layout

\begin_layout Standard
\align left
再就是我们可以给
\begin_inset Formula $\beta$
\end_inset

加上一些约束条件，这样的话最小化问题后面就可以简单的使用拉格朗日乘子法来解。
\end_layout

\begin_layout Standard
\align left
这次的收获之一就是OLS估计量的计算。在实践中，我们计算OLS估计值并不是直接使用
\begin_inset Formula $\hat{\beta}=(X'X)^{-1}X'Y$
\end_inset

，而是会事先进行QR分解（利用特征值来算）。即，我们把X分解为化为正交（酉）矩阵Q与实（复）上三角矩阵R的乘积。这样一来，
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\hat{\beta}=(X'X)^{-1}X'Y=(R'Q'QR)^{-1}R'Q'Y=R^{-1}(Q'Y)
\]

\end_inset

 
\end_layout

\begin_layout Standard
\align left
这样可解
\begin_inset Formula $R\beta=Q'Y$
\end_inset

，计算时候的稳定性比直接求逆矩阵来的好很多，因为计算机必竟有数字长度的限制，各种位数带来的精度损耗最后会累积到估计量上。
\end_layout

\begin_layout Standard
\align left
最后就是高斯-马尔科夫定理，就是我们常说的BLUE估计量。我就直接拷贝这个定理了：
\end_layout

\begin_layout Quotation
\align left
在误差零均值，同方差，且互不相关的线性回归模型中，回归系数的最佳无偏线性估计（BLUE）就是最小方差估计。一般而言，任何回归系数的线性组合的最佳无偏线性估计就是
它的最小方差估计。在这个线性回归模型中，误差既不需要假定正态分布，也不需要假定独立（但是需要不相关这个更弱的条件），还不需要假定同分布。
\end_layout

\begin_layout Standard
\align left
进一步的，如果假设扰动项服从正态分布，比如白噪声，那么
\begin_inset Formula $\hat{\beta}$
\end_inset

的估计值也服从正态分布，
\begin_inset Formula $y$
\end_inset

的预测值也服从正态分布，因此可以直接做一系列基于正态分布的假设检验。特别的，在大样本情况下，就算扰动项不是正态分布，我们也还是可以利用大数定律和中心极限定理...事实
上一般也是这么做的。
\end_layout

\begin_layout Standard
\align left
本节课到此结束。老师没有一一推导无偏性最小方差这些性质，我倒是觉得对回归方法感兴趣的还是直接去看计量经济学吧。这东西水还是蛮深的。
\end_layout

\begin_layout Section
OLS和高斯马尔可夫定理
\end_layout

\begin_layout Standard
\align left
照例继续本周笔记。这次我没啥废话了...
\end_layout

\begin_layout Standard
\align left
--------------笔记开始---------------
\end_layout

\begin_layout Subsection
投影矩阵与消灭矩阵
\end_layout

\begin_layout Standard
\align left
首先是上次没证的若干OLS性质。基本都是公式。我就照抄原来econometrics做的笔记了。权当复习了...对计量有兴趣的、线性代数还不错的，建议去看《
\begin_inset CommandInset href
LatexCommand href
name "Microeconometrics- Methods and Applications"
target "http://book.douban.com/subject/2221578"

\end_inset

》（A.
 Colin Cameron / Pravin K.
 Trivedi ）。
\end_layout

\begin_layout Standard
\align left
先定义两个矩阵，这两个矩阵会在某种程度上save your life while learning econometrics...投影矩阵和消灭矩阵。
\end_layout

\begin_layout Standard
\align left
复习一下，OLS估计量是
\begin_inset Formula $\hat{\beta}=(X'X)^{-1}X'Y$
\end_inset

，然后对应的Y估计量是
\begin_inset Formula $\hat{Y}=X\hat{\beta}=X(X'X)^{-1}X'Y$
\end_inset

。所以，我们定义投影矩阵P为
\begin_inset Formula $P=X(X'X)^{-1}X'$
\end_inset

，这样就有了
\begin_inset Formula $\hat{Y}=PY$
\end_inset

。也就是说，我们对
\begin_inset Formula $Y$
\end_inset

进行了一次投影，然后得到了一个估计值。当然定义投影矩阵并不仅仅是写起来比那堆
\begin_inset Formula $X$
\end_inset

简单，而是投影矩阵本身有着一系列良好的性质。
\end_layout

\begin_layout Standard
\align left
我们先来看把
\begin_inset Formula $P$
\end_inset

投在
\begin_inset Formula $X$
\end_inset

上会怎么样。显然，
\begin_inset Formula $PX=X(X'X)^{-1}X'X=X$
\end_inset

，也就是说
\begin_inset Formula $P$
\end_inset

不会改变
\begin_inset Formula $X$
\end_inset

的值（本来就是把一个东西投到
\begin_inset Formula $X$
\end_inset

上嘛~自己投自己怎么会有变化的嘛）。
\end_layout

\begin_layout Standard
\align left
然后呢，对
\begin_inset Formula $P$
\end_inset

进行转置，则
\begin_inset Formula $P'=(X(X'X)^{-1}X')'=P$
\end_inset

，所以接下来
\begin_inset Formula $P^{2}=P'P=X(X'X)^{-1}X'X(X'X)^{-1}X'=P$
\end_inset

。
\end_layout

\begin_layout Standard
\align left
再定义消灭矩阵
\begin_inset Formula $M$
\end_inset

。很简单，我们定义
\begin_inset Formula $M$
\end_inset

为
\begin_inset Formula $M=I-P=I-X(X'X)^{-1}X'$
\end_inset

，其中
\begin_inset Formula $I$
\end_inset

为单位阵（对角线元素为1，其他为0）。这样
\begin_inset Formula $M$
\end_inset

又有什么性质呢？显然
\begin_inset Formula $MY=(I-P)Y=Y-\hat{Y}=\varepsilon$
\end_inset

，也就是说
\begin_inset Formula $M$
\end_inset

对
\begin_inset Formula $Y$
\end_inset

的效果是得到误差项。而与此同时，
\begin_inset Formula $M$
\end_inset

对于
\begin_inset Formula $X$
\end_inset

的作用就是
\begin_inset Formula $MX=(I-P)X=X-X=0$
\end_inset

，所以称为消灭矩阵嘛。继续，进行转置，则
\begin_inset Formula $M'=(I-P)'=I-P=M$
\end_inset

，所以我们还有
\begin_inset Formula $M^{2}=M'M=(I-P)(I-P)=I-P-P+P=I-P=M$
\end_inset

。
\end_layout

\begin_layout Subsection
OLS估计值的方差
\end_layout

\begin_layout Standard
\align left
再次友情提醒，
\begin_inset Formula $X$
\end_inset

不是随机变量，所以不要跟我纠结为什么没有条件期望公式之类的东西...
\end_layout

\begin_layout Standard
\align left
扰动项服从
\begin_inset Formula $N(0,\sigma)$
\end_inset

时，或者大样本下，OLS估计量的方差为：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
Var(\hat{\beta})=E[(\hat{\beta}-\beta)(\hat{\beta}-\beta)']=E[(X'X)^{-1}X'\varepsilon][(X'X)^{-1}X'\varepsilon]'=(X'X)^{-1}E(\varepsilon\varepsilon')=s_{1}^{2}(X'X)^{-1}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
这里 
\begin_inset Formula $s_{1}^{2}$
\end_inset

为样本方差，所以其分布为： 
\begin_inset Formula $\hat{\beta}\sim N(\beta,s_{1}^{2}(X'X)^{-1})$
\end_inset

。这样一来，就有了一个t检验：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
t=\frac{\beta-0}{s_{1}^{2}(X'X)^{-1}}\sim t_{N-K-1}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
大样本下，就直接用正态检验好了。此外，如果我们进一步的有更多的同时检验的约束条件，那就是联合检验F。这个就不赘述了...
\end_layout

\begin_layout Subsection
高斯-马尔可夫定理
\end_layout

\begin_layout Standard
\align left
顺便还证了一下高斯-马尔可夫定理...这个不像OLS，每次我可记不住他的证明，每次都是现翻书...
\end_layout

\begin_layout Standard
\align left
我就直接抄wiki了。
\end_layout

\begin_layout Standard
\align left
选择另外一个线性估计量
\begin_inset Formula $\tilde{\beta}=CY$
\end_inset

，然后
\begin_inset Formula $C$
\end_inset

可以写为
\begin_inset Formula $(X'X)^{-1}X'+D$
\end_inset

，则
\begin_inset Formula $D$
\end_inset

为
\begin_inset Formula $k*n$
\end_inset

的非空矩阵。
\end_layout

\begin_layout Standard
\align left
那么这个估计量
\begin_inset Formula $\tilde{\beta}$
\end_inset

的期望是 ：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\begin{align}
E(CY) & =E(((X'X)^{-1}X'+D)(X\beta+\varepsilon))\\
 & =((X'X)^{-1}X'+D)X\beta+((X'X)^{-1}X'+D)\underbrace{E(\varepsilon)}_{0}\\
 & =(X'X)^{-1}X'X\beta+DX\beta\\
 & =(I_{k}+DX)\beta.
\end{align}

\end_inset


\end_layout

\begin_layout Standard
\align left
所以，为了保证
\begin_inset Formula $\tilde{\beta}$
\end_inset

无偏，则必有
\begin_inset Formula $DX=0$
\end_inset

.
\end_layout

\begin_layout Standard
\align left
继续求方差：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\begin{align}
V(\tilde{\beta}) & =V(CY)=CV(Y)C'=\sigma^{2}CC'\\
 & =\sigma^{2}((X'X)^{-1}X'+D)(X(X'X)^{-1}+D')\\
 & =\sigma^{2}((X'X)^{-1}X'X(X'X)^{-1}+(X'X)^{-1}X'D'+DX(X'X)^{-1}+DD')\\
 & =\sigma^{2}(X'X)^{-1}+\sigma^{2}(X'X)^{-1}(\underbrace{DX}_{0})'+\sigma^{2}\underbrace{DX}_{0}(X'X)^{-1}+\sigma^{2}DD'\\
 & =\underbrace{\sigma^{2}(X'X)^{-1}}_{V(\hat{\beta})}+\sigma^{2}DD'.
\end{align}

\end_inset


\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $DD'$
\end_inset

是一个半正定矩阵，
\begin_inset Formula $V(\tilde{\beta})$
\end_inset

肯定要比
\begin_inset Formula $V(\hat{\beta})$
\end_inset

大~得证。
\end_layout

\begin_layout Subsection
变量选择与收缩方法
\end_layout

\begin_layout Standard
\align left
为了降低测试误差（减少函数的复杂度），有时候会放弃无偏性而进行变量选择。这里首先就是Ridge OLS（岭回归）。还是算一下这个东西好了。
\end_layout

\begin_layout Standard
\align left
岭回归就是对估计量另外加一个约束条件，所以很自然的想到拉格朗日乘子法。ridge regression的目标函数为，
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\hat{\beta}=\arg\min\sum(y-\hat{y})^{2}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
s.t.\sum\hat{\beta}^{2}\leq k
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
可以重写为
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\hat{\beta}=\arg\min(\sum(y-\hat{y})^{2}+\lambda(\hat{\beta}^{2}-k))
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
记 
\begin_inset Formula $\mathcal{L}=\sum(y-\hat{y})^{2}+\lambda(\hat{\beta}^{2}-k)$
\end_inset


\end_layout

\begin_layout Standard
\align left
这样我们就得到两个一阶条件：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\frac{\partial L}{\partial\beta}=X'(X\hat{\beta}-Y)+\lambda\hat{\beta}=0$
\end_inset

和 
\begin_inset Formula $\frac{\partial L}{\partial\lambda}=\hat{\beta}^{2}-k=0$
\end_inset

，所以有：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\hat{\beta}=(X'X+\lambda I)^{-1}X'Y$
\end_inset


\end_layout

\begin_layout Standard
\align left
这里还可以看出，
\begin_inset Formula $\lambda$
\end_inset

的取值都是对应
\begin_inset Formula $k$
\end_inset

的。这里可以看出，约束条件是二阶范式，Lasso则是把 
\begin_inset Formula $L_{2}$
\end_inset

改成 
\begin_inset Formula $L_{1}$
\end_inset

，已经没有解析解了...
\end_layout

\begin_layout Standard
\align left
至于为什么叫收缩方法，可以将X进行奇异值分解，然后可以得出
\begin_inset Formula $\hat{Y}_{ridge}$
\end_inset

的方差将变小...我就不写证明了，感觉这一块儿讲的也不是很透彻。
\end_layout

\begin_layout Section
logit和LDA
\end_layout

\begin_layout Standard
\align left
鉴于我上周写的
\begin_inset CommandInset href
LatexCommand href
name "课堂笔记4"
target "http://www.loyhome.com/%e2%89%aa%e7%bb%9f%e8%ae%a1%e5%ad%a6%e4%b9%a0%e7%b2%be%e8%a6%81the-elements-of-statistical-learning%e2%89%ab%e8%af%be%e5%a0%82%e7%ac%94%e8%ae%b0%ef%bc%88%e5%9b%9b%ef%bc%89/"

\end_inset

让很多人反映太枯燥、太无聊（全是公式...可是这就是笔记嘛，又不是写科普文），我努力让这周的笔记除了公式之外多一点直觉和应用层面的点评。
\end_layout

\begin_layout Standard
\align left
其实
\begin_inset CommandInset href
LatexCommand href
name "笔记1"
target "http://www.loyhome.com/%e2%89%aa%e7%bb%9f%e8%ae%a1%e5%ad%a6%e4%b9%a0%e7%b2%be%e8%a6%81the-elements-of-statistical-learning%e2%89%ab%e8%af%be%e5%a0%82%e7%ac%94%e8%ae%b0%ef%bc%88%e4%b8%80%ef%bc%89/"

\end_inset

到
\begin_inset CommandInset href
LatexCommand href
name "笔记2"
target "http://www.loyhome.com/%e2%89%aa%e7%bb%9f%e8%ae%a1%e5%ad%a6%e4%b9%a0%e7%b2%be%e8%a6%81the-elements-of-statistical-learning%e2%89%ab%e8%af%be%e5%a0%82%e7%ac%94%e8%ae%b0%ef%bc%88%e4%ba%8c%ef%bc%89/"

\end_inset

中说了很多回归和分类器的不同了，那么在经历了线性回归方法之后，就来说说分类器好了。我原来一直觉得回归和分类器没有什么本质不同的...主要是最常用的分类器logit和p
robit都是我在学计量的时候学的，那个时候老师只是简单的说，这两个和OLS都是一致的，只是我们想让预测值在0～1之内所以做一下变换。而且我们那个时候也不叫他们
分类器，而是叫他们“离散被解释变量模型”。前几个月的时候，看data mining的东西，看得晕晕乎乎的，就跑去问精通此类模型的同事MJ，让他跟我科普了一下午为
什么这两个模型大家更经常称之为分类器...汗颜啊，那个时候我才知道原来machine learning是先分supervised learning and
 unsupervised learning，然后才是 regression v.s.
 classification, and clustering...疏通了脉络之后，再看
\emph on
The Elements of Statistical Learning
\emph default
 这本书，就觉得顺畅多了。以前只是零零散散的接触一个个孤立的模型，没有找出一个脉络串起来过，自然也就不知道分别适用于什么场景。
\end_layout

\begin_layout Standard
\align left
其实我挺想说的是，从econometrics到data mining，远远没有想象的那么简单。数学工具上或许很顺畅，但是思维上的转变还是需要时间和实践的。真是为
难坏了我这个学经济学出身的孩子（其实话说回来，我好好的不去研究经济学，好奇什么data mining呀~只能聊以一句“殊途同归”来搪塞自己，对嘛，反正都是doc
tor of philosophy, 只要是科学，本质的思考方式应该是相通的）。不过搞清楚之后，还是觉得很好玩的——以前是雾里看花，觉得什么都漂亮；现在渐渐的能
够分清楚这些美丽之间的差异了，也算是个小进步吧。
\end_layout

\begin_layout Standard
\align left
再有个小废话...记得上小学的时候，老师问大家“长大了想做什么呀？”，我们总是会特别有出息的回答“科学家~”。那个时候有门课叫做《自然》，老师总给我们讲各种各样的发明
，让我们一度觉得这个世界上的问题都被解决完了，还当什么科学家啊。然后老师就给我们讲哥德巴赫猜想，大意是世间还有那么几个悬而未决的皇冠问题，等待大家长大了去攻克。
后来，越读书越发现，有那么多问题人们是不知道答案的，只是从 ambiguity 
\begin_inset Formula $\rightarrow$
\end_inset

uncertainty
\begin_inset Formula $\rightarrow$
\end_inset

possibility
\begin_inset Formula $\rightarrow$
\end_inset

probability
\begin_inset Formula $\rightarrow$
\end_inset

certainty (law)一步步的走下去。有那么多问题，其实都是悬而未决的哲学问题，等待着聪明的大脑去回答。这也是越读书越觉得兴奋的缘故吧，越来越多的时候老
师会被问倒，然后说“不知道”...然后好奇心就又开始勃勃生长...然后又发现更多的很好玩但没有答案的问题...周而复始，有意思的很。
\end_layout

\begin_layout Standard
\align left
-------满足大家的八卦之心之后，笔记开始-------
\end_layout

\begin_layout Subsection
线性分类器
\end_layout

\begin_layout Standard
\align left
对应原书第四章。
\end_layout

\begin_layout Standard
\align left
先是来一点直觉上的东西：分类器顾名思义，就是把一堆样本归到不同的类别中去。那么这类模型的几何直觉是什么呢？很简单，空间分割嘛。最直白的，我们有一群人，组成了一个
大的群体。然后现在要把大家归为男女两类，那么空间自然就是被分割为两个子空间——男和女了。
\end_layout

\begin_layout Standard
\align left
线性分类器是什么呢？分割男和女的时候，可能分割是三个一群，五个一簇的，所以非要画分割的界限的话，八成是山路十八弯的...我们以前说过，这类的模型问题就是可能复杂度比较
高（比如参数的个数较多），导致就算训练误差小，测试误差不一定小。所以呢，我们希望这个分割界限是直线的（二维平面下）、或者平面的（三维空间中），或者超平面的（高位
空间中），这样就比较清晰明了的感觉了。 
\end_layout

\begin_layout Subsection
线性分类器：logit模型（或称logistic regression） 
\end_layout

\begin_layout Standard
\align left
这里也不完全是按照吴老师上课讲的东西了，因为回头再看这本书会发现书中还有一些很好玩的直觉很强的东西。错过不免可惜，一并收纳。
\end_layout

\begin_layout Standard
\align left
首先换一下记号～我们在前面都用$Y$代表被解释变量，从现在开始对于分类问题，我们改用
\begin_inset Formula $G$
\end_inset

。
\end_layout

\begin_layout Standard
\align left
logit模型下，考虑最简单的分为两类，我们有
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\Pr(G=1|X=x)=\frac{\exp(X\beta)}{1+\exp(X\beta)}$
\end_inset


\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\Pr(G=2|X=x)=\frac{1}{1+\exp(X\beta)}$
\end_inset


\end_layout

\begin_layout Standard
\align left
所以有
\begin_inset Formula $\log\frac{\Pr(G=1|X=x)}{\Pr(G=2|X=x)}=X\beta$
\end_inset


\end_layout

\begin_layout Standard
\align left
这样，分别属于这两组之间的比例就可以找到一个线性的边界了（注：log为单调变换~不影响结果）。这样变换的目的其实无非是，保证
\begin_inset Formula $\Pr(G=1|X=x)+\Pr(G=2|X=x)=1$
\end_inset

，而且两个比例之间存在着一种线性的、或者可以通过单调变换成为线性的关系。类似的当然是大名鼎鼎的probit模型，思路是类似的。 
\end_layout

\begin_layout Subsection
损失函数
\end_layout

\begin_layout Standard
\align left
显然线性分类器下，在有很多类的情况中，损失函数定义为OLS的残差平方和是没有多大意义的——分类取值只是一个名义量。所以，这里用0-1损失函数：如果
\begin_inset Formula $\hat{G}=f(x)=G$
\end_inset

，那么损失函数=0；否则，就是没预测准，损失函数=1。写为数学形式，就是损失函数
\begin_inset Formula $\mathcal{L}$
\end_inset

定义为：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\mathcal{L}(G,f(x))=\begin{cases}
0G=f(x)\\
1G\neq f(x)
\end{cases}$
\end_inset


\end_layout

\begin_layout Standard
\align left
所以我们的目标就是，最小化损失函数的期望：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\min\: E(\mathcal{L})=E_{x}[E_{G|x}(\mathcal{L}(G,f(x))|x)]=1-\Pr(G|x)$
\end_inset


\end_layout

\begin_layout Standard
\align left
(条件期望迭代)。 
\end_layout

\begin_layout Subsection
LDA：linear discriminant analysis(贝叶斯意义下)
\end_layout

\begin_layout Standard
\align left
从贝叶斯的角度，我们有
\begin_inset Formula $\Pr(G=k|X=x)=\frac{\Pr(G,X)}{\Pr(X)}=\frac{f_{k}(x)\pi_{k}}{\sum_{k=1}^{K}f_{k}(x)\pi_{k}}$
\end_inset

，
\begin_inset Formula $\pi_{k}$
\end_inset

为
\begin_inset Formula $k$
\end_inset

出现的概率。
\end_layout

\begin_layout Standard
\align left
假设
\begin_inset Formula $X$
\end_inset

服从联合正态分布
\begin_inset Formula $N(\mathbf{\mu}_{,}\sum)$
\end_inset

，那么我们有
\begin_inset Formula $f_{k}(x)=\frac{1}{(2\pi)^{p/2}|\sum_{k}|^{1/2}}e^{-\frac{1}{2}(x-\mu_{k})'\sum_{k}^{-1}(x-\mu_{k})}$
\end_inset

。
\end_layout

\begin_layout Standard
\align left
再假设协方差矩阵
\begin_inset Formula $\sum_{k}=\sum,\forall k$
\end_inset

，所以我们比较两类
\begin_inset Formula $k$
\end_inset

和
\begin_inset Formula $l$
\end_inset

的时候有：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula $\log\frac{\Pr(G=k|X=x)}{\Pr(G=l|X=x)}=\log\frac{f_{k}(x)}{f_{l}(x)}+\log\frac{\pi_{k}}{\pi_{l}}=\log\frac{\pi_{k}}{\pi_{l}}-\frac{1}{2}(\mu_{k}-\mu_{l})'\Sigma^{-1}(\mu_{k}-\mu_{l})+x'\Sigma^{-1}(\mu_{k}-\mu_{l})$
\end_inset


\end_layout

\begin_layout Standard
\align left
这样就形成了一个x的线性方程，所以我们找到了一个超平面，实现了LDA。
\end_layout

\begin_layout Standard
\align left
实践中我们需要估计联合正态分布的参数，一般有
\begin_inset Formula $\hat{\pi_{k}}=N_{k}/N$
\end_inset

，其中
\begin_inset Formula $N_{k}$
\end_inset

为分类
\begin_inset Formula $k$
\end_inset

出现的样本数；
\begin_inset Formula $\hat{\mu_{k}}=\sum_{g_{i}=k}x_{i}/N_{k}$
\end_inset

，即这
\begin_inset Formula $N_{k}$
\end_inset

个样本中，
\begin_inset Formula $x$
\end_inset

观测值的平均数；
\begin_inset Formula $\hat{\Sigma}=\sum_{k=1}^{K}\sum_{g_{i}=k}(x_{i}-\hat{\mu_{k}})(x_{i}-\hat{\mu_{k}})'/(N-K)$
\end_inset

。
\end_layout

\begin_layout Subsection
Fisher视角下的分类器
\end_layout

\begin_layout Standard
\align left
Fisher提出的观点为，分类器应该尽量使不同类别之间距离较远，而相同类别距其中心较近。比如我们有两群，中心分别为
\begin_inset Formula $\mu_{1}$
\end_inset

和
\begin_inset Formula $\mu_{2}$
\end_inset

，那么我们希望
\begin_inset Formula $\left\Vert \mu_{1}-\mu_{2}\right\Vert ^{2}$
\end_inset

尽量大，同时群内方差
\begin_inset Formula $\sum_{1}+\sum_{2}$
\end_inset

尽量小。通过对
\begin_inset Formula $x$
\end_inset

进行投影到
\begin_inset Formula $z=xw$
\end_inset

，我们可以化简的得到
\begin_inset Formula $\left\Vert \mu_{1}-\mu_{2}\right\Vert ^{2}=w'S_{between}w$
\end_inset

且
\begin_inset Formula $\sum_{1}+\sum_{2}=w'(S_{1}+S_{2})w=w'S{}_{within}w$
\end_inset

。这样一来，我们的准则就是：
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\max\frac{w'S_{between}w}{w'S_{within}w}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
由于
\begin_inset Formula $S_{within}$
\end_inset

是正定阵，所以我们可以进一步写为
\end_layout

\begin_layout Standard
\align left
\begin_inset Formula 
\[
\max\frac{u'S_{within}^{-1/2}S_{between}S_{within}^{-1/2}u}{\left\Vert u\right\Vert ^{2}}
\]

\end_inset


\end_layout

\begin_layout Standard
\align left
其中
\begin_inset Formula $u$
\end_inset

是
\begin_inset Formula $S_{within}^{-1/2}S_{between}S_{within}^{-1/2}$
\end_inset

的特征向量。最终可以求的，最优的
\begin_inset Formula $w^{*}$
\end_inset

正是
\begin_inset Formula $S_{within}^{-1/2}S_{between}S_{within}^{-1/2}$
\end_inset

的最大特征向量。
\end_layout

\begin_layout Standard
\align left
说实话，我对LDA（或者QDA）的理解都非常有限...这本书里面还有一节说到LDA和logit怎么选，我也是大概看了一下没有特别的看明白...笔记只是如实记录，海涵。暂时还
不知道讲到Fisher到底是想讲什么...理解力好有限，唉。
\end_layout

\begin_layout Standard
\align left
------最后的碎碎念------
\end_layout

\begin_layout Standard
\align left
除了统计学习精要，Coursera的Model Thinking也终于结课了，做完了期末考试卷，感觉心里空空的。这门课真的是开的非常深入浅出，覆盖了这么多学科、
问题的各种模型，非常有助于逻辑思考和抽象。只是多少有些遗憾的，很多东西来不及细细回味，听过了视频就忘了，没有努力的去理解那些模型背后的逻辑。这也是导致最终的期末
考试做的不怎么好的缘故——我不想去翻课堂视频或者笔记，只是想考验一下自己对于这些模型的理解和记忆能力。事实证明，除了那些跟经济学或者数学紧密相关的模型，其他的都
多多少少记得不是那么清晰了。过阵子应该好好整理一下这门课的笔记，算作是一个良好的回顾吧。
\end_layout

\begin_layout Standard
\align left
不知道为什么，工作之后再去学这些东西，真的感觉力不从心的时刻多了很多。这半年只有这么区区两门课，就让我觉得有时候不得不强迫自己一下赶上进度，强迫的手段之一就是在
落园开始写连载（大家容忍，谢谢~）。不过为了保持一个基本的生活质量，还是应该不时看看这些新东西的，要不生活都腐朽了。
\end_layout

\begin_layout Section
logisitic、LDA和perceptional分类器
\end_layout

\begin_layout Standard
呃，我觉得我的笔记稍稍有点混乱了...这周讲的依旧是线性分类器，logit为主。anyway，大家将就着看吧。
\end_layout

\begin_layout Subsection
logistic regression
\end_layout

\begin_layout Standard
首先我们考虑最一般的，有K种分类的场合。依旧，我们用
\begin_inset Formula $G$
\end_inset

来代替
\begin_inset Formula $Y$
\end_inset

作为观测到的分类结果，那么则有：
\end_layout

\begin_layout Standard
\begin_inset Formula $\hat{G}=\arg\max_{G}\, P(G|X)$
\end_inset

为最优的预测结果。这里我们希望找到一种线性的形式，还需要使用一些单调变换保证预测值在
\begin_inset Formula $[0,1]$
\end_inset

之间。因此，我们对于每个分类
\begin_inset Formula $k$
\end_inset

，假设
\begin_inset Formula $P(G=k|X=x)=\frac{e^{X\beta_{k}}}{\sum_{k=1}^{K}e^{X\beta_{k}}}$
\end_inset


\end_layout

\begin_layout Standard
进一步的，我们取任意类K作为对照组，且各组相加概率之和必为1，所以有：
\end_layout

\begin_layout Standard
\begin_inset Formula $P(G=k|X=x)=\frac{e^{X\beta_{k}}}{1+\sum_{k=1}^{K-1}e^{X\beta_{k}}}$
\end_inset

且
\begin_inset Formula $P(G=K|X=x)=\frac{1}{1+\sum_{k=1}^{K-1}e^{X\beta_{k}}}$
\end_inset


\end_layout

\begin_layout Standard
所以，最终得到两组之间的概率比值为：
\begin_inset Formula $\frac{P(G=k|X=x)}{P(G=K|X=x)}=e^{X\beta_{k}}\Rightarrow\log\left(\frac{P(G=k|X=x)}{P(G=K|X=x)}\right)=X\beta_{k}$
\end_inset


\end_layout

\begin_layout Standard
最后求解的时候，就是直接用最大似然准则，来求解
\begin_inset Formula $\max\,\mathcal{L}(\beta)=\max\,\sum_{i=1}^{N}\log P(G_{i}|X_{i})$
\end_inset


\end_layout

\begin_layout Standard
这个最大似然函数计算起来比较麻烦，通常很多是数值解。下面以
\begin_inset Formula $K=2$
\end_inset

为例，来展示求解过程。
\end_layout

\begin_layout Standard
首先我们这个时候有两类，不妨记作1和0，则
\begin_inset Formula $P(G=1|X=x)=\frac{e^{X\beta}}{1+e^{X\beta}}\equiv\sigma(X\beta)$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $P(G=0|X=x)=\frac{1}{1+e^{X\beta}}=1-\sigma(X\beta)$
\end_inset

则它的对数似然函数:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{eqnarray*}
\mathcal{L}(\beta) & = & \sum_{i=1}^{N}[G_{i}\log P(G_{i}=1|X=x_{i})+(1-G_{i})\log P(G_{i}=0|X=x_{i})\\
 & = & \sum_{i=1}^{N}[G_{i}\log\frac{P(G_{i}=1|X=x_{i})}{P(G_{i}=0|X=x_{i})}+\log P(G_{i}=0|X=x_{i})]\\
 & = & \sum_{i=1}^{N}[G_{i}X_{i}\beta+\log(1-\sigma(X_{i}\beta))]
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
然后我们求导可得：
\begin_inset Formula $\frac{\partial\mathcal{L}(\beta)}{\partial\beta}=\sum_{i=1}^{N}[G_{i}X_{i}-\sigma(X_{i}\beta)X_{i}]=\sum_{i=1}^{N}[G_{i}-\sigma(X_{i}\beta)]X_{i}$
\end_inset


\end_layout

\begin_layout Standard
之后可以用牛顿法迭代求数值解：
\end_layout

\begin_layout Standard
\begin_inset Formula $\beta^{new}=\beta^{old}\pm(\frac{\partial^{2}\mathcal{L}(\beta)}{\partial\beta\partial\beta})^{-1}\frac{\partial\mathcal{L}(\beta)}{\partial\beta}$
\end_inset


\end_layout

\begin_layout Standard
其中二阶导数部分可以化简为：
\begin_inset Formula $\frac{\partial^{2}\mathcal{L}(\beta)}{\partial\beta\partial\beta}=-\sum_{i=1}^{N}X_{i}'X_{i}[\sigma(X_{i}\beta)(1-\sigma(X_{i}\beta))]$
\end_inset


\end_layout

\begin_layout Standard
记
\begin_inset Formula $\Sigma(\beta)=\left[\begin{array}{c}
\sigma(X_{1}\beta)\\
\vdots\\
\sigma(X_{N}\beta)
\end{array}\right]$
\end_inset


\end_layout

\begin_layout Standard
且
\begin_inset Formula $W=\left[\begin{array}{ccc}
\sigma(X_{1}\beta)(1-\sigma(X_{1}\beta))\\
 & \ddots\\
 &  & \sigma(X_{N}\beta)(1-\sigma(X_{N}\beta))
\end{array}\right]$
\end_inset


\end_layout

\begin_layout Standard
则
\begin_inset Formula $\beta^{new}\leftarrow\beta^{old}+(X'WX)^{-1}X'(G-\Sigma(\beta^{old}))=\underbrace{(X'WX)^{-1}X'W}_{OLS}\underbrace{[X\beta^{old}+W^{-1}(G-\Sigma(\beta^{old}))]}_{Z}$
\end_inset


\end_layout

\begin_layout Standard
经过简化之后，这里相当于加权的最小二乘法，目标函数为
\begin_inset Formula $\arg\min_{\beta^{new}}(Z-X\beta)'W(Z-X\beta)$
\end_inset


\end_layout

\begin_layout Standard
所以整个算法可以写作：
\end_layout

\begin_layout Standard
0.
 令
\begin_inset Formula $\beta=0$
\end_inset

或任意起始值
\end_layout

\begin_layout Standard
1.
 计算
\begin_inset Formula $Z$
\end_inset

矩阵.
\end_layout

\begin_layout Standard
2.
 新的
\begin_inset Formula $\beta$
\end_inset

为
\begin_inset Formula $\arg\min_{\beta^{new}}(Z-X\beta)'W(Z-X\beta)$
\end_inset

.
\end_layout

\begin_layout Standard
3.
 重复1，2步直至收敛。
\end_layout

\begin_layout Standard
这类方法成为IRLS（不断重写的加权最小二乘法）。 
\end_layout

\begin_layout Subsection
LDA和logit选择
\end_layout

\begin_layout Standard
其实也没什么定论，两者均为线性，只是一般我们认为LDA需要假设联合正态且方差相等，比较强；而logit假设没有这么强，相比而言更稳定。 perceptional
分类器
\end_layout

\begin_layout Standard
perceptional分类器是一类相对简单的分类算法，以两类场合为例。为了方便起见，我们假设两类为1和-1，则目标是找出一条直线可以完全分割出来两群点。这里转
化成数学的语言，就是找到W使得
\begin_inset Formula $\begin{cases}
G_{i}=1 & X_{i}W>0\\
G_{i}=-1 & X_{i}W<0
\end{cases}$
\end_inset


\end_layout

\begin_layout Standard
或者简化为：
\begin_inset Formula $G_{i}X_{i}W>0$
\end_inset


\end_layout

\begin_layout Standard
算法也很简单：
\end_layout

\begin_layout Standard
1.
 给定任意的W值，比如0.
 如果
\begin_inset Formula $G_{i}X_{i}W\leq0$
\end_inset

，出错。
\end_layout

\begin_layout Standard
2.
 令新的
\begin_inset Formula $W\leftarrow W+G_{i}X_{i}$
\end_inset

，重复第一步。
\end_layout

\begin_layout Standard
这里可证一个定理：如果原数据集是线性可分的（即W存在），那么在有限步内perceptional算法收敛。其实从第二步可以看出，这样的改进总是趋近于目标的：
\begin_inset Formula $G_{i}X_{i}W^{new}=G_{i}X_{i}W^{old}+X_{i}'X_{i}$
\end_inset

，一定是在逐步增加的。
\end_layout

\begin_layout Standard
同样的算法推广到多累场合，我们就需要引入特征向量
\begin_inset Formula $\Phi(x,G)\beta_{k}$
\end_inset

，使得条件概率
\begin_inset Formula $P(G=k|X=x)=\Phi(x,G)\beta_{k}$
\end_inset

。这样我们的目标就是找到
\begin_inset Formula $\beta$
\end_inset

使得
\begin_inset Formula $\hat{G_{i}}=\arg\max\Phi(x,G)\beta$
\end_inset


\end_layout

\begin_layout Standard
同样的，
\begin_inset Formula $\beta$
\end_inset

从0开始，当
\begin_inset Formula $\hat{G_{i}}\neq G_{i}$
\end_inset

时，
\begin_inset Formula $\beta\leftarrow\beta+[\Phi(x_{i},G_{i})-\Phi(x_{i},\hat{G_{i}})]$
\end_inset

，直至收敛。
\end_layout

\begin_layout Standard
不过有意思的是，实践证明，最后使用
\begin_inset Formula $\beta$
\end_inset

训练过程中的
\begin_inset Formula $\beta_{1},...,\beta_{m}$
\end_inset

的平均值效果会更好，而不是最终的
\begin_inset Formula $\beta$
\end_inset

值。
\end_layout

\begin_layout Standard
--------笔记结束，废话开始--------
\end_layout

\begin_layout Standard
到这里，分类器吴老师已经介绍了三类：LDA，Logit和perceptional。其实我一直觉得比较好玩的是分类器和聚类方法的对比——虽然一个是有监督，一个是无
监督的学习，不过有的时候我们就算有$Y$的观测值也不一定直接就去用——聚类方法某种程度上显得更加自然一些。这也是大家把模型与实际业务相结合起来的成果吧，总要更符
合业务上的直觉才可以。是自然的展现群落的形态，还是给定一些条条框框只是去预测？实践中真的是，都去试试才知道那种更符合一个具体案例的需求。这也是在industry
玩的比较开心的缘故，没有那么多条条框框，没有那么多“约定俗成“的规矩，需要自己去一步步挖掘这些算法的用武之地。看着一个个自己熟悉或者陌生的模型被逐渐的改造和应用
，也是一件蛮开心的事情呢。
\end_layout

\begin_layout Section
B-splines（样条）
\end_layout

\begin_layout Standard
貌似是第五章，不过老师一直在讲一些非常基础的数学预备工具：基展开与正则化，其中用到泛函概念若干。我不知道该开心呢，还是不开心呢，还是开心呢，毕竟泛函学过，毕竟泛
函忘得也差不多了...
 
\end_layout

\begin_layout Subsection
预备知识
\end_layout

\begin_layout Standard
在P维欧氏空间内，我们定义两个运算：加法（
\begin_inset Formula $x+y$
\end_inset

）和数乘(
\begin_inset Formula $\alpha x$
\end_inset

)，然后定义一下函数空间：
\begin_inset Formula $\mathbb{R}$
\end_inset

上的平方可积函数
\begin_inset Formula $L^{2}(\mathbb{R})=\{f|f^{2}(x)dxlt;;\infty\}$
\end_inset

，同样的定义加法和数乘：
\begin_inset Formula $f+g$
\end_inset

和
\begin_inset Formula $\alpha f$
\end_inset

).
\end_layout

\begin_layout Standard
接下来还有若干概念...呜呼： 
\end_layout

\begin_layout Itemize
线性组合：
\begin_inset Formula $\alpha_{1}x_{1}+...+\alpha_{p}x_{p}$
\end_inset


\end_layout

\begin_layout Itemize
线性独立
\end_layout

\begin_layout Itemize
线性子空间：我们可以定义线性子空间，
\begin_inset Formula $\forall x\in L,y\in L$
\end_inset

 , 有
\begin_inset Formula $\alpha x+\beta y\in L$
\end_inset

.
\end_layout

\begin_layout Itemize
基
\end_layout

\begin_layout Itemize
维数
\end_layout

\begin_layout Standard
这些概念连上运算加法和数乘一起，构成线性空间。进一步的，我们可以定义内积空间：
\end_layout

\begin_layout Itemize
内积：（离散）
\begin_inset Formula $<x,y>=\sum x_{i}y_{i}$
\end_inset

或连续
\begin_inset Formula $<f,g>=\intop f(x)g(x)dx$
\end_inset


\end_layout

\begin_layout Itemize
之后的正交就很容易定义了：
\begin_inset Formula $<x,y>=0$
\end_inset

或者
\begin_inset Formula $<f,g>=\intop f(x)g(x)dx=0$
\end_inset


\end_layout

\begin_layout Itemize
还可以定义正交基..
\end_layout

\begin_layout Itemize
还有正交子空间：
\begin_inset Formula $L_{1}\bot L_{2}\Leftrightarrow<x,y>=0,\forall x\in L_{1},y\in L_{2}$
\end_inset


\end_layout

\begin_layout Itemize
正交补：
\begin_inset Formula $\exists L_{2}$
\end_inset

 , 使得
\begin_inset Formula $L_{1}\bot L_{2}$
\end_inset

 且
\begin_inset Formula $L_{1}\oplus L_{2}=\mathbb{R}$
\end_inset

，比如最简单的二维空间里面，X轴和Y轴..
\end_layout

\begin_layout Itemize
范数：
\begin_inset Formula $||x||^{2}=<x,x>$
\end_inset


\end_layout

\begin_layout Standard
有了范数以后，我们就可以进一步的定义极限：如果
\begin_inset Formula $||x_{n}-x||\rightarrow0$
\end_inset

 , 则
\begin_inset Formula $x_{n}\rightarrow x$
\end_inset

 ；或者连续的，
\begin_inset Formula $||f_{n}(x)-f(x)||^{2}=\int(f_{n}(x)-f(x))dx=0$
\end_inset

。
\end_layout

\begin_layout Standard
然后就是闭子空间的概念了：如果
\begin_inset Formula $x_{n}\in L$
\end_inset

 ，且
\begin_inset Formula $\forall x_{n}\rightarrow x$
\end_inset

 ，则必有
\begin_inset Formula $x\in L$
\end_inset

 ，即极限点都在空间内。注，在有限维空间内，只有空集和全集既开又闭。
\end_layout

\begin_layout Standard
还有完备基...总之大致的就是一步步的：定义内积
\begin_inset Formula $\rightarrow$
\end_inset

内积空间
\begin_inset Formula $\rightarrow$
\end_inset

存在可数的完备正交基
\begin_inset Formula $\rightarrow$
\end_inset

Hilbert空间（有限维完备空间）
\end_layout

\begin_layout Subsection
B-splines（样条）
\end_layout

\begin_layout Subsubsection
定义
\end_layout

\begin_layout Standard
B-splines更多的是一种用离散逼近连续的感觉...好吧我承认我是完全的没有接触过这个东西，扫盲中...
\end_layout

\begin_layout Standard
首先，我们有一个闭区间
\begin_inset Formula $[a,b]$
\end_inset

,然后有
\begin_inset Formula $x_{0},...,x_{N}$
\end_inset

个点聚集在其中，且依次增大。然后我们就可以定义一个函数集合：
\begin_inset Formula $\{B_{k}^{d}(x),k=-d,..,N,d=0,1,...\}$
\end_inset

 ，然后对于
\begin_inset Formula $d=0$
\end_inset

 ,定义分段函数
\begin_inset Formula $B_{k}^{0}(x)=\begin{cases}
1,x_{k}<x<x_{k+1}\\
0,else
\end{cases}$
\end_inset

 ，然后就可以递归的定义
\end_layout

\begin_layout Standard
\begin_inset Formula $B_{k}^{d}(x)=\frac{x-x_{k}}{x_{k+d}-x_{k}}B_{k}^{d-1}(x)+\frac{x_{k+d+1}-x}{x_{k+d+1}-x_{k+d}}B_{k+1}^{d-1}(x)$
\end_inset


\end_layout

\begin_layout Standard
举个例子呢，就有
\begin_inset Formula $B_{0}^{1}(x)=\frac{x-x_{0}}{x_{1}-x_{0}}B_{0}^{0}(x)+\frac{x_{2}-x}{x_{2}-x_{1}}B_{1}^{0}(x)$
\end_inset

.
 这样下去，有：
\end_layout

\begin_layout Itemize
\begin_inset Formula $d=0$
\end_inset

，0阶的时候，只有一段函数上有非零值；
\end_layout

\begin_layout Itemize
\begin_inset Formula $d=1$
\end_inset

，1阶的时候，有两段函数有非零值；
\end_layout

\begin_layout Itemize
\begin_inset Formula $d=2$
\end_inset

，2阶的时候，有三段函数有非零值...
\end_layout

\begin_layout Subsubsection
性质
\end_layout

\begin_layout Itemize
性质一：
\begin_inset Formula $B_{k}^{d}(x)$
\end_inset

 是分段的d次多项式；
\end_layout

\begin_layout Itemize
性质二：局部性：
\begin_inset Formula $B_{k}^{d}(x)=0$
\end_inset

， 当
\begin_inset Formula $x<x_{k}$
\end_inset

 或者
\begin_inset Formula $x>x_{k+d}$
\end_inset

；
\end_layout

\begin_layout Itemize
性质三：光滑：
\begin_inset Formula $B_{k}^{d}(x)$
\end_inset

是
\begin_inset Formula $d-1$
\end_inset

阶光滑的多项式，即
\begin_inset Formula $d-1$
\end_inset

阶导数都等于0；
\end_layout

\begin_layout Itemize
性质四：如果某一函数满足性质三，则必然和
\begin_inset Formula $B_{k}^{d}(x)$
\end_inset

只相差一个常数因子。
\end_layout

\begin_layout Subsubsection
d阶B-splines
\end_layout

\begin_layout Standard
我们可以用B-splines来逼近任意一个函数，则有
\begin_inset Formula $f(x)=\sum_{k=1}\alpha_{k}B_{k}^{d}(x)$
\end_inset

，从这个角度看B-splines有点基底的味道。从分段多项式，到光滑的分段多项式，再到
\begin_inset Formula $d-1$
\end_inset

阶光滑的
\begin_inset Formula $d$
\end_inset

次多项式，我们就有了
\begin_inset Formula $d$
\end_inset

阶B-splines...
\end_layout

\begin_layout Standard
------笔记结束---------
\end_layout

\begin_layout Standard
讲了这么多，我一直在猜这些到底是用来干什么的呢...不知道接下来的哪些内容用到了完备内积空间、基展开和线性逼近呢？
\end_layout

\begin_layout Section
平滑splines、子波分析
\end_layout

\begin_layout Subsection
平滑splines 
\end_layout

\begin_layout Standard
有数据集
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后定义目标函数
\begin_inset Formula $\sum_{i=1}^{N}(y_{i}-f(x_{i}))^{2}+\lambda\int_{a}^{b}f''(x)^{2}dx$
\end_inset

，记为(1)
\end_layout

\begin_layout Standard
式。然后我们有如下结论：使（1）最小化的解一定是分段三次多项式。
\end_layout

\begin_layout Standard
证明如下。
\end_layout

\begin_layout Standard
记
\begin_inset Formula $\mathcal{F}$
\end_inset

为函数族
\begin_inset Formula $a=x_{0}<\cdots<xn<x_{n+1}=b$
\end_inset

上的分段三次多项式（splines），且在首尾两段
\begin_inset Formula $[x_{0},x_{1}]$
\end_inset

和
\begin_inset Formula $[x_{n},x_{n+1}]$
\end_inset

上是一次多项式，那么他一定有
\begin_inset Formula $4(N-1)+2*2-3N=N$
\end_inset

的自由度。
\end_layout

\begin_layout Standard
若
\begin_inset Formula $f\in\mathcal{F}$
\end_inset

，则当
\begin_inset Formula $x\in[x_{0},x_{1}],\,\, x\in[x_{n},x_{n+1}]$
\end_inset

时，有
\begin_inset Formula $f''(x)=0$
\end_inset

。
\end_layout

\begin_layout Standard
(2) 我们设
\begin_inset Formula $g(x)$
\end_inset

也是(1)式的解，则下面证明一定能找到
\begin_inset Formula $f*$
\end_inset

使得目标函数比
\begin_inset Formula $g(x)$
\end_inset

小，则
\begin_inset Formula $f*\in F$
\end_inset

,
\end_layout

\begin_layout Standard
\begin_inset Formula $f*(x_{i})=g(x_{i}),\forall1\leq i\leq N$
\end_inset

.
\end_layout

\begin_layout Standard
(3)记
\begin_inset Formula $h(x)=g(x)-f*(x)$
\end_inset

，则
\begin_inset Formula $h(x_{i})=0,\forall1\leq i\leq N$
\end_inset


\end_layout

\begin_layout Standard
(4) 下面我们证明，
\begin_inset Formula $h''(x)\perp f*''$
\end_inset

（两者内积为0），即
\begin_inset Formula $\int_{a}^{b}h''(x)f*(x)''dx=0$
\end_inset

。
\end_layout

\begin_layout Standard
\begin_inset Formula $\int_{a}^{b}h''(x)f*(x)''dx=\int_{a}^{b}f*(x)''dh'(x)=\underbrace{f*(x)''h'(x)\mid_{a}^{b}}_{0}-\int_{a}^{b}h'(x)df*(x)''$
\end_inset


\end_layout

\begin_layout Standard
且
\begin_inset Formula $-\int_{a}^{b}h'(x)df*(x)''=-[\int_{a}^{x_{1}}+\sum_{i=1}^{N-1}\int_{x_{i}}^{x_{i+1}}+\int_{X_{N}}^{b}]=\begin{cases}
\int_{a}^{x_{1}}h'(x)f*(x)'''dx & \equiv0\\
\int_{X_{N}}^{b}h'(x)f*(x)'''dx & \equiv0\\
\int_{x_{i}}^{x_{i+1}}h'(x)\underbrace{f*(x)'''}_{constant}dx & =f*(x)'''\underbrace{\int_{x_{i}}^{x_{i+1}}h'(x)dx}_{0}
\end{cases}$
\end_inset


\end_layout

\begin_layout Standard
所以得到
\begin_inset Formula $h''(x)\perp f*''$
\end_inset

。
\end_layout

\begin_layout Standard
(5)有了上述结论后，我们有
\begin_inset Formula $g(x)=f*(x)+h(x)\Rightarrow g''(x)=f*(x)''+h''(x)$
\end_inset

，然后有
\begin_inset Formula $\left\Vert g''(x)\right\Vert ^{2}=\left\Vert f*(x)''+h''(x)\right\Vert ^{2}=\left\Vert f*(x)''\right\Vert ^{2}+\left\Vert h''(x)\right\Vert ^{2}\geq\left\Vert f*(x)''\right\Vert ^{2}$
\end_inset

，所以对于所有的
\begin_inset Formula $g$
\end_inset

，我们都有其二阶导数的范数小于
\begin_inset Formula $f$
\end_inset

的二阶导数的范数，故在(1)式中代入
\begin_inset Formula $g$
\end_inset

总比代入
\begin_inset Formula $f$
\end_inset

大（或者相等）。这样我们就把一个无限维的最优化问题变为了有限维。 
\end_layout

\begin_layout Subsection
子波分析 
\end_layout

\begin_layout Subsubsection
1.
 函数的平移与缩放
\end_layout

\begin_layout Standard
平移：
\begin_inset Formula $f_{k}(x)=f(x-k)$
\end_inset


\end_layout

\begin_layout Standard
缩放：
\begin_inset Formula $f^{d}(x)=2^{d}f(2^{d}x)$
\end_inset


\end_layout

\begin_layout Standard
组合起来就是
\begin_inset Formula $f_{k}^{d}(x)=2^{d}f(2^{d}x-k)$
\end_inset

。由此，对于每个
\begin_inset Formula $d$
\end_inset

，我们可以定义一个函数族
\begin_inset Formula $\mathcal{F}^{d}:\{f_{k}^{d}(x),k\in\mathbb{Z}\}$
\end_inset

，写成矩阵形式就是
\end_layout

\begin_layout Standard
\begin_inset Formula $\underbrace{\begin{array}{cccccccc}
 &  &  &  & k\\
 & \cdots & -2 & -1 & 0 & 1 & 2 & \cdots\\
 & -2\\
d & -1 &  & \ddots\\
 & 0 &  &  & f_{0}^{0}(x)\\
 & 1 &  &  &  & f_{1}^{1}(x)\\
 & 2 &  &  &  &  & \ddots\\
 & \vdots
\end{array}}_{\mathcal{F}^{d}}$
\end_inset


\end_layout

\begin_layout Subsubsection
2.
 Hoar函数
\end_layout

\begin_layout Standard
(1)定义：
\begin_inset Formula $h(x)=\begin{cases}
0 & 0\leq x\leq1\\
1 & else
\end{cases}$
\end_inset

。
\end_layout

\begin_layout Standard
(2)Hoar函数的平滑与缩放。定义Hoar函数族为
\begin_inset Formula $\mathcal{H}^{d}:\{h_{k}^{d}(x),k\in\mathbb{Z}\}$
\end_inset

,
\end_layout

\begin_layout Standard
\begin_inset Formula $\forall d\in\mathbb{Z}$
\end_inset

。这样我们每个
\begin_inset Formula $\mathcal{H}^{d}$
\end_inset

为一组（胖瘦一样）。
\end_layout

\begin_layout Standard
定理1（正交）：
\begin_inset Formula $\mathcal{H}^{d}$
\end_inset

是
\begin_inset Formula $L^{2}(\mathbb{R})$
\end_inset

平方可积函数的一个正交基，即对于任意的
\begin_inset Formula $k\neq g$
\end_inset

，有
\begin_inset Formula $<h_{k}^{d}(x),h_{g}^{d}(x)>=\int h_{k}^{d}h_{g}^{d}dx=0$
\end_inset

。
\end_layout

\begin_layout Standard
定理2（增长）：随着
\begin_inset Formula $d$
\end_inset

的增加，
\begin_inset Formula $\mathcal{H}^{d}$
\end_inset

张成的闭子空间逐渐增大，且
\begin_inset Formula $\overline{\mathcal{H}^{d}}\subseteq\overline{\mathcal{H}^{d+r}}$
\end_inset

。这样，
\begin_inset Formula $d$
\end_inset

比较小的函数一定能用
\begin_inset Formula $d$
\end_inset

比较大的函数（正交基）来表示，比如
\begin_inset Formula $h_{0}^{0}(x)=h_{0}^{1}(x)+h_{1}^{1}(x)/2$
\end_inset

。直观的理解就是，
\begin_inset Formula $d$
\end_inset

越大，分辨率越高。
\end_layout

\begin_layout Standard
定理3（完备）：
\begin_inset Formula $\overline{\mathcal{H}^{d}}\uparrow L^{2}(\mathbb{R})$
\end_inset


\end_layout

\begin_layout Standard
(3)定义
\begin_inset Formula $\omega^{d}$
\end_inset

，使
\begin_inset Formula $\omega^{d}=\mathcal{H}^{d+1}\ominus\mathcal{H}^{d}$
\end_inset

，或者
\begin_inset Formula $\mathcal{H}^{d+1}=\omega^{d}\oplus\mathcal{H}^{d}$
\end_inset

。
\end_layout

\begin_layout Standard
(4)定义
\begin_inset Formula $w(x)=\begin{cases}
1 & 0\leq x\leq\frac{1}{2}\\
-1 & \frac{1}{2}\leq x\leq1\\
0 & else
\end{cases}$
\end_inset

，然后
\begin_inset Formula $w_{k}^{d}(x)=2^{d}w(2^{d}x-k),k,d\in\mathbb{Z}$
\end_inset

。
\end_layout

\begin_layout Standard
定理4：函数族
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\omega^{d}:\{w_{k}^{d}(x),k\in\mathbb{Z}\}$
\end_inset

,
\begin_inset Formula $\forall d\in\mathbb{Z}$
\end_inset

，则
\begin_inset Formula $\oplus_{d}\omega^{d}=L^{2}(\mathbb{R})$
\end_inset

亦为完备基，且
\begin_inset Formula $\omega^{d}\perp\omega^{d\text{’}}$
\end_inset

，如果
\begin_inset Formula $d\neq d'$
\end_inset

。也就是说，
\begin_inset Formula $\overline{\mathcal{H}^{d+1}}$
\end_inset

和
\begin_inset Formula $\overline{\mathcal{H}^{d}}$
\end_inset

之间的空间随着d的增加，彼此正交，且所有的叠起来之后亦为完备空间。
\end_layout

\begin_layout Standard
如此，我们称
\begin_inset Formula $w(x)$
\end_inset

为子波（mother）而
\begin_inset Formula $h(x)$
\end_inset

为father函数。注意，这里Hoar函数非连续。
\end_layout

\begin_layout Standard
在更一般的场合，我们寻找
\begin_inset Formula $f(x)$
\end_inset

为father函数，然后定义
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\mathcal{F}^{d}:\{f_{k}^{d}(x),k\in\mathbb{Z}\}$
\end_inset

，满足
\begin_inset Formula $<f_{k}^{d}(x),f_{g}^{d}(x)>=0$
\end_inset

（正交），且
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit

\begin_inset Formula $\overline{\mathcal{\mathcal{F}}^{d}}\subseteq\overline{\mathcal{F}^{d+r}}$
\end_inset

（增长），
\begin_inset Formula $\overline{\mathcal{F}^{d}}\uparrow L^{2}(\mathbb{R})$
\end_inset

（完备）。
\end_layout

\begin_layout Standard
再寻找mother函数
\begin_inset Formula $g(x)$
\end_inset

满足
\begin_inset Formula $<g_{k}^{d}(x),g_{g}^{d}(x)>=0$
\end_inset

（同层次内正交）、
\begin_inset Formula $\mathcal{\mathcal{F}}^{d+1}=\mathcal{G}^{d}\oplus\mathcal{F}^{d}$
\end_inset

(相邻层次正交补）和
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\oplus_{d}\mathcal{G}^{d}=L^{2}(\mathbb{R})$
\end_inset


\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit
完备。
\end_layout

\begin_layout Standard
这样的
\begin_inset Formula $f(x)$
\end_inset

和
\begin_inset Formula $g(x)$
\end_inset

到底存不存在呢？实证结论是存在，而且很多，不过坏消息是他们的形式都不算简单。
\end_layout

\begin_layout Subsection
spline和子波分析
\end_layout

\begin_layout Standard
spline和子波分析都提供了一组线性基底，其线性组合可以定义函数类。由此，我们可以定义广义线性模型的函数族，为统计学习模型的函数族做约束。
\end_layout

\begin_layout Section
核平滑与局部方法
\end_layout

\begin_layout Subsection
核平滑器
\end_layout

\begin_layout Subsubsection
K-NN（K近邻）
\end_layout

\begin_layout Standard
KNN的思想已经说过很多遍了，大致就是找点x的k个近邻，然后取其
\begin_inset Formula $y_{i}$
\end_inset

平均值作为x点y的预测值
\begin_inset Formula $\hat{y}$
\end_inset

。不过这里我们就在想了，可不可以加权呀~于是从最简单的
\begin_inset Formula $\hat{y}=\frac{1}{k}\sum_{x_{i}\in N_{k}(x)}y_{i}$
\end_inset

，我们给他按距离算个加权平均：
\begin_inset Formula $\hat{y}=\sum_{x_{i}\in N_{k}(x)}w_{i}y_{i}$
\end_inset

,其中
\begin_inset Formula $w_{i}$
\end_inset

代表权重，离x点越近越大，越远越小。这样听起来更make sense一点嘛~近朱者赤，近墨者黑。
\end_layout

\begin_layout Subsubsection
单峰函数
\end_layout

\begin_layout Standard
顾名思义，就是长得像一个山峰的函数，比如我们最经典的正态钟型函数，或者翻过来的二次抛物线函数等等。
\end_layout

\begin_layout Subsubsection
权重（按距离）
\end_layout

\begin_layout Standard
我们定义权重
\begin_inset Formula $k_{\lambda}(x,x_{i})=D\left(\frac{\left\Vert x-x_{i}\right\Vert ^{2}}{\lambda}\right)$
\end_inset

，再进一步归一化：
\begin_inset Formula $\frac{k_{\lambda}(x,x_{i})}{\sum_{j=1}^{N}k_{\lambda}(x,x_{j})},1\leq i\leq N$
\end_inset

。
\end_layout

\begin_layout Standard
多维的情况下，写成矩阵形式就是
\begin_inset Formula $k_{\lambda}(x,x_{i})=D\left(\frac{(x-x_{i})^{'}A(x-x_{i})}{\lambda}\right)$
\end_inset

，其中A为正定对角阵，然后我们就可以加权了。
\end_layout

\begin_layout Subsection
局部方法
\end_layout

\begin_layout Subsubsection
一般概念
\end_layout

\begin_layout Standard
我们有数据集
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后定义函数族
\begin_inset Formula $\mathcal{F}=\{f(x|\theta),\theta\in\Theta\}$
\end_inset

。再定义损失函数
\begin_inset Formula $\mathcal{L}(y,f(x))$
\end_inset

, 我们的目标就是最小化
\begin_inset Formula $\sum_{i}\mathcal{L}(y_{i},f(x_{i}))$
\end_inset

。
\end_layout

\begin_layout Standard
相应的引入了加权的概念之后，我们就可以定义加权损失函数：
\begin_inset Formula $\sum_{i}\frac{k_{\lambda}(x,x_{i})}{\sum_{j=1}^{N}k_{\lambda}(x,x_{j})}\mathcal{L}(y_{i},f(x_{i}|\theta))$
\end_inset

，然后对于每个x做优化，寻找使其最小化的
\begin_inset Formula $\theta$
\end_inset

。
\end_layout

\begin_layout Subsubsection
具体例子
\end_layout

\begin_layout Standard
(i) 局部回归： 
\begin_inset Formula $y=f(x|\theta)=\theta'x=\sum_{j=1}^{p}\theta_{j}x_{j}$
\end_inset

，则损失函数为
\begin_inset Formula $\sum_{1}^{N}\bar{k}_{\lambda}(x,x_{i})[y_{i}-f(x_{i}|\theta)]^{2}$
\end_inset

，其中
\begin_inset Formula $\bar{k}_{\lambda}(x,x_{i})$
\end_inset

代表已经归一化的权重。
\end_layout

\begin_layout Standard
在线性的情况下，我们有
\begin_inset Formula $\sum_{1}^{N}\bar{k}_{\lambda}(x,x_{i})[y_{i}-\sum_{1}^{p}\theta_{j}x_{ij}]^{2}$
\end_inset

，有点类似于我们常见的加权最小二乘法。这里的思想也是，在x点附近的点权重会比较大，离x远的权重则比较小，整体感觉就是在x点附近做了一个回归分析。
\end_layout

\begin_layout Standard
(ii) 局部似然：和局部回归蛮像的，只是把损失函数换成（对数）似然函数，即从最大化 
\begin_inset Formula $\sum_{1}^{N}\log P(y_{i}|x_{i},\theta)$
\end_inset

到现在的最大化加权似然函数
\begin_inset Formula $\sum_{1}^{N}\bar{k}_{\lambda}(x,x_{i})\log P(y_{i}|x_{i},\theta)$
\end_inset

。
\end_layout

\begin_layout Subsection
密度估计与分类
\end_layout

\begin_layout Standard
(1) 密度与分类: 我们有x和观测结果G的联合分布：
\begin_inset Formula $P(x,G)=P(G)P(x|G)$
\end_inset

，其中
\begin_inset Formula $p(G)$
\end_inset

为先验的结果分布，在有K类结果的情况下，写成 
\begin_inset Formula $\pi_{k}=P(G=k)$
\end_inset

。这样，也可以写开为
\begin_inset Formula $P_{k}(x)=P(x|G=k),$
\end_inset

 其中
\begin_inset Formula $1\leq k\leq K$
\end_inset

。
\end_layout

\begin_layout Standard
反过来，后验概率
\begin_inset Formula $P(G|x)=\frac{P(G,x)}{P(x)}=\frac{\pi_{k}P_{k}(x)}{\sum_{1}^{K}\pi_{l}P_{l}(x)}$
\end_inset

，所以我们有贝叶斯分类器 
\begin_inset Formula $\hat{G}=\arg\max P(G|x)$
\end_inset

。
\end_layout

\begin_layout Standard
(2) 密度估计
\end_layout

\begin_layout Standard
为了使用贝叶斯分类器，我们需要先对密度进行估计。
\end_layout

\begin_layout Standard
(i) 直方图： 最简单的就是根据直方图来估计密度，这个没什么好说的...
\end_layout

\begin_layout Standard
(ii) 核估计方法（Parzen）：Parzen提出的核密度估计为
\begin_inset Formula $\hat{f(x)}=\frac{1}{N}k_{\lambda}\left(\frac{\left\Vert x-x_{i}\right\Vert ^{2}}{\lambda}\right)=\frac{1}{N}\sum_{i=1}^{N}\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(x-x_{i})^{2}}{2\sigma^{2}}}$
\end_inset

，该估计当
\begin_inset Formula $N\rightarrow\infty$
\end_inset

且
\begin_inset Formula $\sigma$
\end_inset

在减小的时候，收敛于
\begin_inset Formula $f(x)$
\end_inset

。
\end_layout

\begin_layout Subsection
核作为基函数
\end_layout

\begin_layout Standard
密度函数
\begin_inset Formula $f(x)=\sum_{i=1}^{N}w_{i}k_{\lambda}\left(\frac{\left\Vert x-x_{i}\right\Vert ^{2}}{\lambda}\right)$
\end_inset

，然后定义函数族
\begin_inset Formula $\mathcal{F}=\{\sum_{i=1}^{N}w_{i}k\left(\frac{\left\Vert x-x_{i}\right\Vert ^{2}}{\lambda}\right)\}$
\end_inset

，则其中
\begin_inset Formula $w_{i}$
\end_inset

我iyigexianxingde参数，
\begin_inset Formula $k$
\end_inset

为指定的函数类，
\begin_inset Formula $\lambda$
\end_inset

亦为函数参数。这样的话我们有三个函数的参数，指定某一个便可以简化函数形式。不过这里的问题是，没有很好的算法来求解优化问题。比如对于正态分布，我们以写出来
\begin_inset Formula $\min_{\{w_{i}\},\{\sigma_{j}\},\{\mu_{j}\}}\mathcal{L}=\min_{\{w_{i}\},\{\sigma_{j}\},\{\mu_{j}\}}\sum_{i=1}^{N}(y_{i}-\sum_{j=1}^{m}w_{j}\frac{1}{\sqrt{2\pi\sigma_{j}^{2}}}e^{-\frac{(x_{i}-\mu_{j})^{2}}{2\sigma_{j}^{2}}})$
\end_inset

，然后的求解就比较复杂了。
\end_layout

\begin_layout Standard
上面的两个是非参数方法，下面说一些参数方法。
\end_layout

\begin_layout Standard
(iii) 混合模型（GMM, Gauss Mixed Model）
\end_layout

\begin_layout Standard
\begin_inset Formula $f(x|\theta)=\sum_{k=1}^{K}\pi_{k}\frac{1}{\sqrt{2\pi\sigma_{k}^{2}}}e^{-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}}$
\end_inset

，其中参数有
\begin_inset Formula $\theta=\{\{\pi_{k}\},\{\mu_{k}\},\{\sigma_{k}\}\}$
\end_inset

，然后可以利用最大似然准则，最大化
\begin_inset Formula $\prod_{i=1}^{N}f(x_{i}|\theta)=\max_{\theta}\sum_{i=1}^{N}\log f(x_{i}|\theta)$
\end_inset

，具体算法可用EM，下节课详述。
\end_layout

\begin_layout Standard
-----稍稍跑题------
\end_layout

\begin_layout Standard
GMM，我印象中它怎么是 Generalized Moment Method, 广义矩估计呢？果然是被计量经济学祸害太深了...
\end_layout

\begin_layout Section
MM、EM和GMM
\end_layout

\begin_layout Standard
继续上一讲，先说说EM算法。
\end_layout

\begin_layout Subsection
MM、EM和GMM
\end_layout

\begin_layout Subsubsection
MM（混合模型）
\end_layout

\begin_layout Standard
(1) 定义：
\begin_inset Formula $P(x)=\sum_{k=1}^{K}\pi_{k}P_{k}(x)$
\end_inset

，其中
\begin_inset Formula $\pi_{k}\geq0$
\end_inset

，
\begin_inset Formula $\sum_{k=1}^{K}\pi_{k}=1$
\end_inset

，构成一个离散分布。同时有
\begin_inset Formula $P_{k}(x)\geq0$
\end_inset

，且
\begin_inset Formula $\int P_{k}(x)dx=1$
\end_inset

，
\begin_inset Formula $1\leq k\leq K$
\end_inset

。
\end_layout

\begin_layout Standard
(2) 隐变量
\end_layout

\begin_layout Standard
我们有数据
\begin_inset Formula $(x,G)$
\end_inset

，同时依据条件概率分布，有
\begin_inset Formula $P(x,G)=P(G)P(x|G)$
\end_inset

。记
\begin_inset Formula $P(G)=\pi_{k}$
\end_inset

，则
\begin_inset Formula $P(x|G=k)=P_{k}(x)$
\end_inset

，其中
\begin_inset Formula $1\leq k\leq K$
\end_inset

。
\end_layout

\begin_layout Standard
则有
\begin_inset Formula $P(x)=\sum_{G}P(x,G)=\sum_{G}P(G)P(x|G)=\sum_{k=1}^{K}\pi_{k}P_{k}(x)$
\end_inset

为x的边际分布。
\end_layout

\begin_layout Standard
(3) GMM（正态混合模型）
\end_layout

\begin_layout Standard
当
\begin_inset Formula $P_{k}(x)=\frac{1}{\sqrt{2\pi\sigma_{k}^{2}}}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right)$
\end_inset

，
\begin_inset Formula $1\leq k\leq K$
\end_inset

，我们有
\begin_inset Formula $P(x)=\sum_{k=1}^{K}\pi_{k}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right)$
\end_inset

，且
\begin_inset Formula $P(x,G=k)=\pi_{k}\exp\left(-\frac{(x-\mu_{k})^{2}}{2\sigma_{k}^{2}}\right)$
\end_inset

，
\begin_inset Formula $1\leq k\leq K$
\end_inset

。
\end_layout

\begin_layout Standard
(4) 对数似然函数和最大似然估计
\end_layout

\begin_layout Standard
对数似然函数写为
\begin_inset Formula $l(\theta)=\sum_{i=1}^{N}\log P(x|\theta)=\sum_{i=1}^{N}\log\sum_{i=1}^{N}P(x_{i},G=k|\theta)=\sum_{i=1}^{N}\log(\sum_{k=1}^{K}P(G=k|\theta)P(x_{k}|G=k,\theta))$
\end_inset

。则我们要求的就是
\begin_inset Formula $\theta^{*}=\arg\max_{\theta}l(\theta)$
\end_inset

，其中
\begin_inset Formula $\theta=\{\{\pi_{k}\},\{\mu_{k}\},\{\sigma_{k}^{2}\}\}$
\end_inset

。
\end_layout

\begin_layout Subsubsection
EM算法 (expectation maximum，期望最大方法)
\end_layout

\begin_layout Standard
(1) 迭代方法： 给定起始值
\begin_inset Formula $\theta^{(0)}$
\end_inset

，迭代出
\begin_inset Formula $\theta^{(1)},..,\theta^{(t)},...$
\end_inset

。那么问题就是，如何在已知
\begin_inset Formula $\theta^{(t)}$
\end_inset

的情况下，求
\begin_inset Formula $\theta^{(t+1)}$
\end_inset

？
\end_layout

\begin_layout Standard
(2) E1步：求
\begin_inset Formula $P(G|x_{i},\theta^{(t)})$
\end_inset

。函数形式已知，故可以求各种条件概率什么的。所以有：
\end_layout

\begin_layout Standard
\begin_inset Formula $P(G|x_{i},\theta^{(t)})=\frac{P(x_{i},G=k)}{P(x_{i})}=\frac{\pi_{k}P_{k}(x)}{\sum_{l=1}^{K}\pi_{l}P_{l}(x)}\triangleq\gamma_{ik}^{(t)}$
\end_inset

。
\end_layout

\begin_layout Standard
E2步：计算
\begin_inset Formula $\mathcal{L}(\theta|\theta^{(t)})=\sum_{i=1}^{N}\sum_{k=1}^{K}\underbrace{(\log P(x_{i},G=k|\theta))P(G=k|x_{i},\theta^{(t)})}_{expectation}$
\end_inset

，由于函数形式已知，我们可以计算并将
\begin_inset Formula $\sum$
\end_inset

移出来，所以换成线性形式。
\end_layout

\begin_layout Standard
(3) M步：求
\begin_inset Formula $\theta^{(t+1)}=\arg\max_{\theta}\mathcal{L}(\theta|\theta^{(t)})$
\end_inset

，这样就完成了迭代。需要证明的性质是：随着迭代，
\begin_inset Formula $l$
\end_inset

越来越大，且收敛。
\end_layout

\begin_layout Standard
(4) 定理：
\begin_inset Formula $l(\theta^{(t+1)})\geq l(\theta^{(t)})$
\end_inset

。
\end_layout

\begin_layout Standard
证明：
\begin_inset Formula 
\begin{eqnarray*}
\mathcal{L}(\theta|\theta^{(t)}) & = & \sum_{i=1}^{N}\sum_{k=1}^{K}\log P(x_{i}|\theta))P(G=k|x_{i},\theta^{(t)})+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta^{(t)})P(G=k|x_{i},\theta^{(t)})\\
 & = & l(\theta)+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta^{(t)})P(G=k|x_{i},\theta^{(t)})\\
 &  & -\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta)P(G=k|x_{i},\theta^{(t)})+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(G=k|x_{i},\theta)P(G=k|x_{i},\theta^{(t)})\\
 & = & l(\theta)-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\sum_{k=1}^{K}KL(\theta^{(t)}|\theta)
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
其中
\begin_inset Formula $H_{i}(\theta^{(t)})=-\sum_{k=1}^{K}\log P(G|x_{i},\theta)P(G|x_{i},\theta^{(t)})$
\end_inset

，且
\begin_inset Formula $KL(\theta^{(t)}|\theta)\equiv\sum_{k=1}^{K}[\log P(G|x_{i},\theta^{(t)})P(G|x_{i},\theta^{(t)})-\log P(G|x_{i},\theta)P(G|x_{i},\theta^{(t)})]=\sum_{k=1}^{K}\log\frac{P(G|x_{i},\theta^{(t)})}{P(G|x_{i},\theta)}-P(G|x_{i},\theta^{(t)})>0$
\end_inset

，定义为两分布的KL距离。
\end_layout

\begin_layout Standard
所以
\begin_inset Formula $\mathcal{L}(\theta^{(t+1)}|\theta^{(t)})=l(\theta^{(t+1)})-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\sum_{k=1}^{K}KL(\theta^{(t)}|\theta^{(t+1)})$
\end_inset

，且
\begin_inset Formula $\mathcal{L}(\theta^{(t)}|\theta^{(t)})=l(\theta^{(t)})-\sum_{i=1}^{N}H_{i}(\theta^{(t)})-\underbrace{\sum_{k=1}^{K}KL(\theta^{(t)}|\theta^{(t)})}_{0}$
\end_inset

。而由M步，
\begin_inset Formula $\mathcal{L}(\theta^{(t+1)}|\theta^{(t)})-\mathcal{L}(\theta^{(t)}|\theta^{(t)})\geq0$
\end_inset

，故有
\begin_inset Formula $l(\theta^{(t+1)})-l(\theta^{(t)})=KL(\theta^{(t)}|\theta^{(t+1)})\geq0$
\end_inset

。
\end_layout

\begin_layout Standard
在GMM的情况下，应用EM算法，则有：
\end_layout

\begin_layout Standard
(1) E1步：
\begin_inset Formula $\gamma_{ik}^{(t)}=\frac{\pi_{k}(2\pi\sigma_{k}^{2})^{-1/2}\exp(-(x_{i}-\mu_{k})^{2}/2\sigma^{2})}{\sum_{l=1}^{K}\pi_{l}P_{l}(x)}$
\end_inset

，可以直接计算。
\end_layout

\begin_layout Standard
(2) E2步：
\begin_inset Formula $\mathcal{L}(\theta|\theta^{(t)})=\sum_{i=1}^{N}\sum_{k=1}^{K}\gamma_{ik}^{(t)}[\log\pi_{k}^{(t)}-\frac{1}{2}\log\pi-\frac{1}{2}\log(\sigma_{k}^{2})-\frac{(x-\mu_{k})^{2}}{2\left(\sigma_{k}^{(t)}\right)^{2}}]$
\end_inset

。
\end_layout

\begin_layout Standard
(3) M步：注意有约束条件
\begin_inset Formula $\sum_{k=1}^{K}\pi_{k}=1$
\end_inset

，所以使用拉格朗日乘子法：
\end_layout

\begin_layout Standard
\begin_inset Formula $L(\theta)=\mathcal{L}(\theta|\theta^{t})+\lambda(\sum\pi_{k}-1)$
\end_inset

，故有一阶条件：
\begin_inset Formula $\frac{\partial L}{\partial\pi_{k}}=\sum_{i=1}^{N}\gamma_{ik}^{(t)}\frac{1}{\pi_{k}^{(t)}}+\lambda=0$
\end_inset

。从而
\begin_inset Formula $\pi_{k}^{t+1}=\frac{N_{k}^{(t)}}{N}$
\end_inset

，其中
\begin_inset Formula $N_{k}^{(t)}=\sum_{i=1}^{N}\gamma_{ik}^{(t)}$
\end_inset

。
\end_layout

\begin_layout Standard
还有一阶条件：
\begin_inset Formula $\frac{\partial L}{\partial\mu_{k}}=\sum_{i=1}^{N}-\frac{2(x_{i}-\mu_{k}^{(t)})(-1)}{2\left(\sigma_{k}^{(t)}\right)^{2}}=0$
\end_inset

，得到
\begin_inset Formula $\mu_{k}^{(t+1)}=\frac{1}{N_{k}}\sum_{i=1}^{N}x_{i}$
\end_inset

。
\end_layout

\begin_layout Standard
最后，
\begin_inset Formula $\frac{\partial L}{\partial(\sigma_{k}^{2})}=0$
\end_inset

，有
\begin_inset Formula $\left(\sigma_{k}^{t+1}\right)^{2}=\frac{1}{N_{k}}\sum_{i=1}^{N}(x_{i}-\mu_{k}^{(t+1)})^{2}$
\end_inset

。
\end_layout

\begin_layout Standard
对GMM而言，E步和M步在k=2的时候，求解过程可参见书上。
\end_layout

\begin_layout Subsection
第七章：模型评估与选择
\end_layout

\begin_layout Standard
1.
 概念： 我们有数据集
\begin_inset Formula $D$
\end_inset

，函数族
\begin_inset Formula $\mathcal{F}$
\end_inset

和损失函数
\begin_inset Formula $\mathcal{L}$
\end_inset

，这样得到最优的
\begin_inset Formula $f(x)\in\mathcal{F}$
\end_inset

，然后求得
\begin_inset Formula $\hat{y}=f(x)$
\end_inset

 （有监督的学习）。之后就是对模型进行评估：
\begin_inset Formula $\hat{y}$
\end_inset

的精度如何（使用测试集）？模型的选择就是
\begin_inset Formula $\mathcal{F}$
\end_inset

的选择，使得测试误差比较小。
\end_layout

\begin_layout Standard
2.
 方法： 
\end_layout

\begin_layout Standard
(1) 数据充分：分成三块，1/2用来训练(train)，1/4用来检验(validation)，1/4用来测试(test)。其中validation
 的概念是，在
\begin_inset Formula $\sum_{i=1}^{N}\mathcal{L}(y_{i},f(x_{i}))+\lambda J(f)$
\end_inset

中，加入J函数来考虑函数族的复杂度，以避免过拟合。而validation就是来调正和选择这里的
\begin_inset Formula $\lambda$
\end_inset

，再用train和validation重新训练模型。
\end_layout

\begin_layout Standard
最后，用test数据集，测试并且评估测试误差。
\end_layout

\begin_layout Standard
(2) 数据不充分：一种是cross-validation，分成k（比如5-10）份，极端的就是K=N，ave-win-out；另一种是bootstrap，后续
章节详述。
\end_layout

\begin_layout Section
BootStrap、MLE、模型评估与选择
\end_layout

\begin_layout Standard
上海的冬天越来越冷了，这门课也越来越临近这学期结束了。这节课公式推导不多，有也是那种烂熟于胸无数次的，所以可以稍稍歪楼，不时掺杂一点八卦什么的。
\end_layout

\begin_layout Subsection
BootStrap
\end_layout

\begin_layout Subsubsection
d定义 
\end_layout

\begin_layout Standard
BootStrap的基本思想就仨字：重抽样。先开始八卦：跟高斯窥探天机猜出来正态分布的密度函数表达式相似，Efron搞出来BootStrap的时候，大概也在偷偷
的抿嘴而笑吧。“上帝到底掷不掷骰子呢？”，每次我们都在揣测天意，也是现在越来越有点理解为什么牛顿老先生晚年致力于神学了。每当我们猜中一次，就会有一个新的突破到来
。BootStrap思想简单到如斯，以至于我的一位朋友在当高中老师的时候（可惜是美国不是中国），就尝试着跟teenagers介绍BootStrap思想了（貌似用
的还是Econometrica上的一篇文章，我瞬间声讨“你们这群高中老师真凶残 -_-|| ”）——结果显然是我多虑了，那群熊孩子居然表示理解毫无压力！可见Bo
otStrap这个东西是有多么的平易近人。什么测度论什么高等代数都不需要，会摸球就可以了！
\end_layout

\begin_layout Standard
顺便抄一下杨灿童鞋《
\begin_inset CommandInset href
LatexCommand href
name "那些年，我们一起追的EB"
target "http://cos.name/2012/05/chase-after-eb/"

\end_inset

》上的一段八卦：
\end_layout

\begin_layout Quote
五十多年前，Efron为 Stanford 的一本幽默杂志 Chapparal 做主编。那年，他们恶搞 (parody) 了著名杂志 Playboy。估计是恶搞
得太给力了，还受到当时三藩的大主教的批评。幽默的力量使 Efron 在“错误”的道路上越走越远，差点就不回 Stanford 读 PhD 了。借用前段时间冰岛外
长的语录：“Efron 从事娱乐时尚界的工作，是科学界的一大损失！”在关键时刻，Efron 在周围朋友的关心和支持下，终于回到 Stanford，开始把他的犀利
与机智用在 statistics 上。告别了娱乐时尚界的 EB，从此研究成果犹如滔滔江水，连绵不绝，citation 又如黄河泛滥，一发不可收拾...
\end_layout

\begin_layout Standard
所以说嘛，天才之人做什么都是能闪光的，Efron从事科学界的工作，怕也是美国几亿人民周末娱乐的损失吧。好了，满足了你们这群越来越挑剔的读者八卦的胃口了，开始正儿
八经的说BootStrap。
\end_layout

\begin_layout Standard
我们有观测数据集
\begin_inset Formula $D:\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后对这N个样本，进行有放回的重抽样。每轮我们还是抽N个，然后一共抽B轮（比如几百轮，话说前几天weibo上有人问“如果给你一万个人，你要做什么”，放在这里我
就要他们不停的抽小球抽小球抽小球，哈哈！）。这样就得到了新的观测样本
\begin_inset Formula $D^{b}:\{(x_{i}^{b},y_{i}^{b}),1\leq i\leq N\},\,1\leq b\leq B$
\end_inset

。
\end_layout

\begin_layout Subsubsection
应用
\end_layout

\begin_layout Standard
BootStrap几乎可以用来干各种合法的不合法的事儿，只要是跟数据估计有关的...这就如同你问一个画家，“什么最好画？”“上帝和魔鬼，因为大家都没有见过。”大家都没
有那么明确的知道BootStrap的界限在哪里，所以BootStrap就被应用在各种跟估计有关的地方了。
\end_layout

\begin_layout Standard
在统计学习中，我们最常用的可能就是估计精度：对于每一个
\begin_inset Formula $D^{b}$
\end_inset

，我们都可以得到一个预测函数
\begin_inset Formula $f(x)$
\end_inset

，然后就对于给定的
\begin_inset Formula $x_{i}$
\end_inset

，有B个预测值
\begin_inset Formula $\hat{y_{i}}$
\end_inset

，这样就可以做直方图什么的，还可以排排序算出来
\begin_inset Formula $\hat{y_{i}}$
\end_inset

的置信区间。
\end_layout

\begin_layout Subsection
最大似然估计（MLE）
\end_layout

\begin_layout Standard
我们有一族密度函数
\begin_inset Formula $P(x|\theta)$
\end_inset

，其中
\begin_inset Formula $\theta$
\end_inset

为参数集，可不止一个参数。按照概率的定义，我们有
\begin_inset Formula $P(x|\theta)\geq0$
\end_inset

，而且
\begin_inset Formula $\int P(x|\theta)dx=1$
\end_inset

。
\end_layout

\begin_layout Standard
数据方面，我们有一组数据
\begin_inset Formula $D:\{x_{i},1\leq i\leq N\}$
\end_inset

，为
\emph on
i.i.d
\emph default
（独立同分布）。
\end_layout

\begin_layout Standard
这样就可以写出来似然函数： 
\begin_inset Formula $L(\theta|D)=\prod_{i=1}^{N}P(x_{i}|\theta)$
\end_inset

，从而可以写出来对数似然函数：
\begin_inset Formula $l(\theta)=\log L(\theta|D)=\sum_{i=1}^{N}\log P(x_{i}|\theta)$
\end_inset

。接下来驾轻就熟的，我们就有最大似然估计量：
\begin_inset Formula $\hat{\theta}=\arg\max_{\theta}\log L(\theta|D)$
\end_inset

。
\end_layout

\begin_layout Standard
最大似然估计之所以这么受欢迎，主要是他有一个非常好的性质：一致性，即当
\begin_inset Formula $N\rightarrow\infty$
\end_inset

，
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
估计值
\begin_inset Formula $\hat{\theta}$
\end_inset

收敛于真值
\begin_inset Formula $\theta_{0}$
\end_inset

。
\end_layout

\begin_layout Standard
仅仅渐进一致还不够，我们当然更喜欢的是MLE的附加优良性质：渐进正态，即
\begin_inset Formula $\hat{\theta}_{MLE}\sim N(\theta,I(\theta_{0})^{-1})$
\end_inset

，其中
\begin_inset Formula $I(\theta_{0})$
\end_inset

称为信息矩阵，定义为
\begin_inset Formula $I(\theta_{0})=-\frac{\partial^{2}l(\theta)}{\partial\theta\partial\theta^{T}}$
\end_inset

。实际中，如果我们不知道真值
\begin_inset Formula $\theta_{0}$
\end_inset

，则会用估计值来代替正态分布中的参数。（没想到事隔这么多年，我居然又手动推导了一遍MLE...真的是，我跟统计的缘分怎么这么纠缠不断呀）。
\end_layout

\begin_layout Standard
MLE大都要求数值解的，少数情况下可以求解解析解。比如正态分布。
\end_layout

\begin_layout Standard
正态分布的密度函数为：
\begin_inset Formula $f(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\, e^{\frac{-(x-\mu)^{2}}{2\sigma^{2}}}$
\end_inset

，所以我们有对数似然函数：
\end_layout

\begin_layout Standard
\begin_inset Formula $\ln\mathcal{L}(\mu,\sigma^{2})=\sum_{i=1}^{n}\ln f(x_{i};\,\mu,\sigma^{2})=-\frac{n}{2}\ln(2\pi)-\frac{n}{2}\ln\sigma^{2}-\frac{1}{2\sigma^{2}}\sum_{i=1}^{n}(x_{i}-\mu)^{2}.$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\hat{\mu}=\overline{x}\equiv\frac{1}{n}\sum_{i=1}^{n}x_{i},\qquad\hat{\sigma}^{2}=\frac{1}{n}\sum_{i=1}^{n}(x_{i}-\overline{x})^{2}$
\end_inset


\end_layout

\begin_layout Standard
还有一个特例是正态线性回归模型（Gauss-Markov），即
\begin_inset Formula $y=X\beta+\varepsilon$
\end_inset

，其中
\begin_inset Formula $\varepsilon\sim i.i.d.\, N(0,\sigma^{2})$
\end_inset

，这个就和OLS的BLUE性质蛮像了，MLE和OLS对于此种情形估计值是完全一样的。所以说高斯王子在搞出OLS的时候，也是各种深思熟虑过的...揣测上帝的“旨意”也不
是件信手拈来的事儿的。
\end_layout

\begin_layout Standard
简单情形下，我们可以直接求得估计量的置信区间，但是在复杂的情形下，就只能用BootStrap了。人们的思路就从传统的数学推倒，越来越多的转换到计算能力了。有的时
候稍稍感觉这更符合统计学的思维——归纳嘛，这也是统计学在computer area和数学渐行渐远的表现之一么？
\end_layout

\begin_layout Standard
吴老师总结了一句话：BootStrap类方法，就是
\series bold
思想简单、实际有效，虽然不知道为什
\series default
么...
\end_layout

\begin_layout Subsection
模型平均
\end_layout

\begin_layout Standard
模型平均也是有点延续上面的BootStrap思想，就是我有很多重抽样出来的模型之后，要怎么平均这些结果来找出最优模型的。
\end_layout

\begin_layout Standard
1.
 Bagging方法。 这个就有点直截了当了。利用BootStrap，我可以
\begin_inset Formula $D\rightarrow D^{b}$
\end_inset

，然后自然收集了一堆
\begin_inset Formula $f^{b}(x|D^{b})$
\end_inset

，所以简单一点就平均一下：
\begin_inset Formula $f_{bag}(x)=\frac{1}{B}\sum_{b=1}^{B}f^{b}(x)$
\end_inset


\end_layout

\begin_layout Standard
2.
 Stacking方法。这个就稍稍动了一点心思，直接平均看起来好简单粗暴呀，还是加权平均一下比较细致一点。所以：
\begin_inset Formula $f_{sta}(x)=\sum_{b=1}^{B}w^{b}f^{b}(x)$
\end_inset

，其中权重
\begin_inset Formula $\sum w^{b}=1$
\end_inset

。实际操作中，
\begin_inset Formula $w^{b}$
\end_inset

的选取也是一个蛮tricky的事儿。可以利用validation集来优化...
\end_layout

\begin_layout Standard
3.
 Bumpping (优选)方法。
\begin_inset Formula $f_{bum}(x)=\arg\max\sum_{i=1}^{N}(y_{i}-f^{b}(x_{i}))^{2}$
\end_inset

，即在所有的
\begin_inset Formula $f^{b}$
\end_inset

中，选择最好的那个，使得一定标准下的损失最小。
\end_layout

\begin_layout Standard
话说，Machine learning或者统计学习，无非就是四件事儿：数据(D)、函数族(
\begin_inset Formula $\mathcal{F}$
\end_inset

)、准则(
\begin_inset Formula $L$
\end_inset

)、算法(A)。说来说去，每一样改进都是在这四个的某一方面或者某几方面进行提升的。
\end_layout

\begin_layout Section
可加模型、树模型
\end_layout

\begin_layout Standard
第九章 可加模型、树模型相关方法
\end_layout

\begin_layout Subsection
可加模型（additive model）
\end_layout

\begin_layout Standard
大家都知道线性模型是最简单好用的，但是往往现实中很多效应都是非线性的。前两个举过一个学历的例子，再抄一下：
\end_layout

\begin_layout Standard
一方面，学历是你受教育的体现，也就是在取得学历的过程中完成了一定程度的知识积累。当然一定程度的学校录取证实了你一定程度的才智，但是也不是只有天才没有汗水就可以毕
业的。更有意思的是，知识的积累往往是厚积而薄发，或者说是个非线性的...这也是为什么在衡量劳动者劳动价值的时候会放入受教育年限和其二次方的一个缘故（至少我是这么理解那
个著名的xx公式中的二次方项的）。
\end_layout

\begin_layout Standard
也就是说，在线性模型中，我们最简单的方法就是利用多项式拟合非线性，不是有个著名的魏尔斯特拉斯（Weierstrass）逼近定理么？闭区间上的连续函数可用多项式级
数一致逼近。 这个定理貌似在数分、实变、复变、泛函都有证明（如果我没记错名字的话）...泰勒（局部展开）也是一种局部使用多项式逼近的思路。不过 人类的智慧显然是无穷的
，自然有了应对各种各样情况的“万能药”和“特效药”，任君对症下药什么的。
\end_layout

\begin_layout Standard
这一节主要是讲generalized additive models，即广义可加模型。广义可加模型假设的是：各个自变量之间不相关，即
\begin_inset Formula $X_{1},...,X_{p}$
\end_inset

可以被拆分开（虽然书上是用期望定义为
\begin_inset Formula $E(Y|X_{1},...,X_{p})=\alpha+f_{1}(X_{1})+\cdots+f_{p}(X_{p})$
\end_inset

，但是我觉得加入一些认为认定的交叉项再扩展开是没有问题的~）。数学表达式就是：
\end_layout

\begin_layout Standard
(1) 定义：
\begin_inset Formula $f(x)=\sum_{j=1}^{p}f_{j}(x_{j})\Rightarrow g(\alpha+\sum_{j=1}^{p}f_{j}(x_{j}))$
\end_inset

，其中
\begin_inset Formula $g(\cdot)$
\end_inset

是已知的，而
\begin_inset Formula $\alpha$
\end_inset

和
\begin_inset Formula $f_{j}(x_{j})$
\end_inset

是需要估计的。可见，如果只是从我们线性模型的
\begin_inset Formula $f(x)=\alpha+\beta_{1}x_{1}+\cdots+\beta_{p}x_{p}$
\end_inset

进化到
\begin_inset Formula $f(x)=\sum_{j=1}^{p}f_{j}(x_{j})$
\end_inset

，那么我们是放松了对于
\begin_inset Formula $X_{j}$
\end_inset

是线性的要求，可以对每个自变量进行非线性回归，但y和这些
\begin_inset Formula $f_{j}(x_{j})$
\end_inset

之间依旧是线性关系；如果进一步放松，那么就可以引入新的非线性函数
\begin_inset Formula $g(\cdot)$
\end_inset

，那么y和那一堆
\begin_inset Formula $f_{j}(x_{j})$
\end_inset

之外还可以再套一层非线性函数。不过这里就要求给定一个g了，常用的就是那些指数函数对数函数等。
\end_layout

\begin_layout Standard
不过这里我们还要要求
\begin_inset Formula $g(\cdot)$
\end_inset

有一些比较优良的性质，首当其中就是可逆...（对于连续函数来说，可逆必定单调...因为可逆
\begin_inset Formula $\Leftrightarrow$
\end_inset

一一映射，又是连续的函数，不单调这就没法玩了呀！）好在我们一般就用一些比较简单的exp和log...常用的
\begin_inset Formula $g(\cdot)$
\end_inset

有：
\begin_inset Formula $y=e^{x}$
\end_inset

，
\begin_inset Formula $y=\log x$
\end_inset

 ，
\begin_inset Formula $y=\theta(x)=\frac{e^{x}}{1+e^{x}}$
\end_inset

，这样
\begin_inset Formula $\theta^{-1}(x)=\log\frac{x}{1-x}$
\end_inset

...其中最后一个就是我们常用的logit regression。这样我们就可以定义“广义可加的logit模型”：
\begin_inset Formula $f(x)=\theta^{-1}(f(x))=\theta^{-1}(\alpha+\sum_{j=1}^{p}f_{j}(x_{j}))$
\end_inset

。
\end_layout

\begin_layout Standard
(2) 算法。还是一样的，有了大致的idea我们还得有好用的算法。下面介绍一种比较一般性的方法。
\end_layout

\begin_layout Standard
数据集依旧记作：
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后我们使用OLS准则：
\begin_inset Formula $\min\sum_{i=1}^{N}(y_{i}-f(x_{i}))^{2}=\min\sum_{i=1}^{N}(y_{i}-\alpha-f_{1}(x_{1})-\cdots-f_{p}(x_{p}))^{2}$
\end_inset

。然后我们有迭代算法：即已知
\begin_inset Formula $f_{j}^{(t)}(x_{j})$
\end_inset

，如何迭代到t+1？
\end_layout

\begin_layout Standard
p个小步：每一次我们都是用给定的其他
\begin_inset Formula $f_{j}^{(t)}(x_{j})$
\end_inset

，其中
\begin_inset Formula $j\neq k$
\end_inset

，求得
\begin_inset Formula $y_{i}'$
\end_inset

，来最小化计算第k个变量的系数
\begin_inset Formula $\sum(y_{i}'-f_{k}(x_{k}))^{2}$
\end_inset

，求的
\begin_inset Formula $f_{k}^{(t+1)}(x_{k})$
\end_inset

。这样的方法称为一维平滑值（one dimension smoother）。而在这个过程中，需要利用B-splines来求
\begin_inset Formula $f_{k}^{(t+1)}(x_{k})$
\end_inset

。所以“其实本来该模型的卖点是非参数，但是最后做一维平滑的时候还要利用参数化的B-splines...”，所以有点打折扣的感觉对不？
\end_layout

\begin_layout Standard
每p个小步构成一个
\begin_inset Formula $t\rightarrow t+1$
\end_inset

的大步。如果最后是用B-splines来拟合，那么其实一开始就可以代入各种参数一次性完成参数化计算。
\end_layout

\begin_layout Standard
唯一值得考量的就是，这个迭代可能是局部最优化而不是全局最优化，有点取决于起始值的味道...我有点怀疑这个起始函数要怎么给...
\end_layout

\begin_layout Standard
(3) Naïve Bayes Assumption（朴素贝叶斯假定）
\end_layout

\begin_layout Standard
有个有趣的结论：在Naïve Bayes 假定下，分类器一定是可加模型。
\end_layout

\begin_layout Standard
直觉上讲，Naïve Bayes假定其实也是假定分量独立：
\begin_inset Formula $P_{k}(x)=P(X=x|G=k)=\prod_{j=1}^{P}P(X_{j}=x_{j}|G=k)$
\end_inset

。
\end_layout

\begin_layout Standard
这样就很容易推导这个结论了：我们有后验概率
\begin_inset Formula $P(G=k|X=x)=\frac{P(X=x,G=k)}{P(X=x)}=\frac{P(G=k)P(X=x|G=k)}{P(X=x)}=\frac{\pi_{k}P_{k}(x)}{\sum_{l=1}^{K}\pi_{l}P_{l}(x)}$
\end_inset

。取个对数，我们有
\begin_inset Formula $\log P(G=k|X=x)=\log\pi_{k}+\log P_{k}(x)-\underbrace{\sum_{l=1}^{K}\pi_{l}P_{l}(x)}_{constant}=\log\pi_{k}+\sum_{j=1}^{P}\log P_{j}(x_{j})$
\end_inset

，所以就成了可加模型的形式。这样，Naïve Bayes 假定比可加模型的假定就更弱一点。关于这点，我又去搜了一下，呃，找到了一点有关的信息：http://ww
w.gabormelli.com/RKB/Generalized_Additive_Model，抄如下：
\end_layout

\begin_layout Quote
In supervised classification, inputs x and their labels y arise from an
 unknown joint probability p(x; y).
 If we can approximate p(x,y) using a parametric family of models G = {pθ(x,y),θ
 in Θ}, then a natural classifier is obtained by first estimating the class-cond
itional densities, then classifying each new data point to the class with
 highest posterior probability.
 This approach is called 
\emph on
generative classification.

\emph default
 
\end_layout

\begin_layout Quote
However, if the overall goal is to find the classification rule with the
 smallest error rate, this depends only on the conditional density p(y|x).
 Discriminative methods directly model the conditional distribution, without
 assuming anything about the input distribution p(x).
 Well known generative-discriminative pairs include Linear Discriminant
 Analysis (LDA) vs.
 Linear logistic regression and naive Bayes vs.
 Generalized Additive Models (GAM).
 Many authors have already studied these models e.g.
 [5,6].
 Under the assumption that the underlying distributions are Gaussian with
 equal covariances, it is known that LDA requires less data than its discriminat
ive counterpart, linear logistic regression [3].
 More generally, it is known that generative classifiers have a smaller
 variance than.
 
\end_layout

\begin_layout Quote
Conversely, the generative approach converges to the best model for the
 joint distribution p(x,y) but the resulting conditional density is usually
 a biased classifier unless its pθ(x) part is an accurate model for p(x).
 In real world problems the assumed generative model is rarely exact, and
 asymptotically, a discriminative classifier should typically be preferred
 [9, 5].
 The key argument is that the discriminative estimator converges to the
 conditional density that minimizes the negative log-likelihood classification
 loss against the true density p(x, y) [2].
 For finite sample sizes, there is a bias-variance tradeoff and it is less
 obvious how to choose between generative and discriminative classifiers.
 
\end_layout

\begin_layout Standard
简单的说，就是“判别式模型与生成式模型”的问题。如果我们使用参数方法逼近联合分布
\begin_inset Formula $p(x,y)$
\end_inset

，那么就是生成式模型（
\emph on
generative models
\emph default
）；相对的，如果我们直接对条件密度p(y|x)建模而不对p(x)进行任何假定，那么就是判别式模型（
\emph on
Discriminative methods
\emph default
）。我们常见的就是LDA和线性logit模型、朴素贝叶斯和广义可加模型。在一些已知如高斯分布的情况下，我们发现LDA优于logit并且有更小的方差，但是生成式模
型的问题就是他的参数假定不满足...所以估计可能是有偏的。所以现实中，我们需要在无偏性和方差之间做一个trade off。关于这里的总结我搜到一篇：Discrimin
ative vs Informative Learning - Stanford University（http://www.stanford.edu/~hasti
e/Papers/kdd97.pdf），习惯中文的可以参考一下http://www.leexiang.com/discriminative-model-and-gen
erative-model。其实这里看看这些概念和思想之争也挺好玩的，以前完全没有从这个角度看过回归模型...可见计量经济学关心的完全不是这些东西。我现在完全没概念我
在machine learning这个深潭里面到底涉足多深了，但是可以明显的感觉统计学习的一些思维已经开始影响我的思维方式了...需要再继续融会贯通一下。
\end_layout

\begin_layout Subsection
树模型(Tree Model)
\end_layout

\begin_layout Standard
(1) 树的一般概念：见过二叉树么?差不多的样子可以有多个叉叉...自行脑补一下分形去吧。
\end_layout

\begin_layout Standard
(2) 回归树（regression tree）
\end_layout

\begin_layout Standard
还是数据集
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后我们可以根据不同的门限来分类，比如x<1分在左边枝子上
\begin_inset Formula $x\geq1$
\end_inset

放在右边枝子上。然后在下一层继续分叉分叉...一层又一层。感觉当初发明树模型的孩子一定很喜欢生物学尤其是植物学吧！有没有类似于顶端优势的定理呢？嘻嘻，可以叫做歪脖子树
定理嘛！（八卦来源：http://life.21cn.com/news/2012/12/25/14154838.shtml）
\end_layout

\begin_layout Standard
对于一颗树T，我们采用如下记号：
\end_layout

\begin_layout Standard
\begin_inset Formula $\left|T\right|$
\end_inset

:叶子的总数
\end_layout

\begin_layout Standard
\begin_inset Formula $R_{m}$
\end_inset

 ：
\begin_inset Formula $1\leq m\leq\left|T\right|$
\end_inset

，某个叶子或者根节点。
\end_layout

\begin_layout Standard
\begin_inset Formula $N_{m}$
\end_inset

：叶子节点
\begin_inset Formula $R_{m}$
\end_inset

 中的样本数。
\end_layout

\begin_layout Standard
\begin_inset Formula $C_{m}$
\end_inset

：
\begin_inset Formula $\frac{1}{N_{m}}\sum y_{i}$
\end_inset

，这
\begin_inset Formula $N_{m}$
\end_inset

个点y的平均值。
\end_layout

\begin_layout Standard
\begin_inset Formula $\sigma_{m}^{2}$
\end_inset

：
\begin_inset Formula $\frac{1}{N_{m}}\sum(y_{i}-C_{m})^{2}$
\end_inset

，每个
\begin_inset Formula $R_{m}$
\end_inset

 中的均方误差（方差）。
\end_layout

\begin_layout Standard
这样一颗树的质量
\begin_inset Formula $Q(T)$
\end_inset

就可以定义为
\begin_inset Formula $Q(T)=\sum_{m=1}^{M}\sigma_{m}^{2}N_{m}$
\end_inset

。这样给定一棵树，有了一个函数
\begin_inset Formula $y=f(x|T)$
\end_inset

，然后就可以预测了。
\end_layout

\begin_layout Standard
树的生长：这就是叶子和层次的选择，显然我们一共有
\begin_inset Formula $P(n+1)$
\end_inset

中选择。需要从中选出最好的
\begin_inset Formula $P_{i}$
\end_inset

和
\begin_inset Formula $t_{i}$
\end_inset

。当生长不动的时候，停止。而长得太大的时候，就是过拟合的问题。所以我们需要剪枝。
\end_layout

\begin_layout Standard
树的剪枝：准则需要变，
\begin_inset Formula $Q(T)+\alpha\left|T\right|$
\end_inset

，即加入一个惩罚项，然后就可以使用cross-validation或者bootstrap了。
\end_layout

\begin_layout Standard
(3) 分类树
\end_layout

\begin_layout Standard
同样的，只是我们需要定义新的准则，类似于0-1准则。
\begin_inset Formula $\hat{P_{km}}=\frac{1}{N_{m}}\sum I(y_{i}=k)$
\end_inset

，也就是节点中属于第k类的比例，所以
\begin_inset Formula $\sum_{k}P_{k}=1$
\end_inset

。
\end_layout

\begin_layout Standard
这样我们就有
\begin_inset Formula $\hat{P}_{k^{*}m}=\max_{k}\hat{P_{km}}$
\end_inset

，即主导类别占据该节点。
\end_layout

\begin_layout Standard
定义1：我们的预测误差就是
\begin_inset Formula $1-\hat{P}_{k^{*}m}$
\end_inset

，就可以定义
\begin_inset Formula $Q(T)=\sum_{k=1}^{K}N_{mk}(1-\hat{P}_{k^{*}m})$
\end_inset

。
\end_layout

\begin_layout Standard
定义2：熵。我们定义
\begin_inset Formula $I_{m}=-\sum\hat{P_{km}}\log\hat{P_{km}}$
\end_inset

，这样就可以定义
\begin_inset Formula $Q(T)=\sum_{m}N_{m}I_{m}$
\end_inset

。
\end_layout

\begin_layout Standard
定义3： 基尼准则（Gini），定义函数
\begin_inset Formula $G_{m}=\sum_{k}\hat{P_{km}}(1-\hat{P_{km}})$
\end_inset

，然后
\begin_inset Formula $Q(T)=\sum_{m}N_{m}G_{m}$
\end_inset

。
\end_layout

\begin_layout Standard
有了准则之后，我们就可以生长、剪枝和预测了。
\end_layout

\begin_layout Standard
为啥我觉得这就是决策树呢？喵了个咪的，就是一个质量定义问题嘛。回归和分类器之鸿沟一直延续呀，无论是线性模型还是树模型...
\end_layout

\begin_layout Section
MARS、PRIM、HME、基函数模型
\end_layout

\begin_layout Standard
本学期最后一堂课的笔记...就这样，每周上班的时候都没有惦念的了，我是有多么喜欢教室和课堂呀。或者说，真的是太习惯学校的生活方式了吧...
\end_layout

\begin_layout Standard
这一节主要是在上一节的基础上，介绍一些可加模型或者树模型的相关（改进）方法。
\end_layout

\begin_layout Subsection
MARSd
\end_layout

\begin_layout Standard
MARS全称为Multivarible Adaptive Regression Splines，看名字就能猜出来大致他是做啥的。MARS这家伙与CART一脉相承
（话说CART的竞争对手就是大名鼎鼎的C4.5）。不过，还是先说一下MARS到底是怎么玩的吧。
\end_layout

\begin_layout Standard
数据集依旧记作
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，然后就是splines的思想：我们定义
\begin_inset Formula $\mathcal{C}=\{(x^{j}-x_{i}^{j})_{+},(x{}_{j}^{i}-x^{j})_{+},1\leq j\leq p,1\leq i\leq N\}$
\end_inset

，其中
\begin_inset Formula $(x-t)_{+}=\begin{cases}
x-t & ,x\geq t\\
0 & ,else
\end{cases}$
\end_inset

和
\begin_inset Formula $(t-x)_{+}=\begin{cases}
t-x & ,x\leq t\\
0 & ,else
\end{cases}$
\end_inset

，画出图形来就是。
\end_layout

\begin_layout Standard
这样就可以定义I函数了：
\begin_inset Formula $I(x\geq t)=\begin{cases}
1 & ,x\geq t\\
0 & ,else
\end{cases}$
\end_inset

，以及
\begin_inset Formula $I(t\geq x)=\begin{cases}
1 & ,t\geq x\\
0 & ,else
\end{cases}$
\end_inset

，越来越有spines味道了是不是？
\end_layout

\begin_layout Standard
之后就是定义f函数：
\begin_inset Formula $f_{J}(x)=\sum_{j=1}^{J}\beta_{j}h_{j}(x)$
\end_inset

，然后有意思的就来了：
\begin_inset Formula $h_{j}(x)$
\end_inset

是
\begin_inset Formula $\mathcal{C}$
\end_inset

中函数或者几个函数的乘积，选定了
\begin_inset Formula $h_{j}(x)$
\end_inset

之后我们就可以用最小二乘法来求解相应的
\begin_inset Formula $\beta$
\end_inset

了。然后在接下来的每一步，我们都添加
\begin_inset Formula $\beta_{m+1}h(x)(x^{j}-x_{i}^{j})+\beta_{m+2}h(x)(x_{i}^{j}-x^{j})+\cdots$
\end_inset

这样，一步步的，
\begin_inset Formula $f_{J}(x)=\sum_{j=1}^{J}\beta_{j}h_{j}(x)$
\end_inset

就开始增长。当我们用完了
\begin_inset Formula $h_{j}(x)$
\end_inset

之后，显然有 over-fit的嫌疑，所以开始逐步的减少一些
\begin_inset Formula $h_{j}(x)$
\end_inset

——考虑移除那些对减少残差平方和贡献比较小的项目。沿着cross-validation的思路，就可以定义函数
\begin_inset Formula $GCV=\frac{\sum_{i=1}^{N}(y_{i}-\hat{f}_{\lambda}(x_{i}))^{2}}{(1-M(\lambda)/N)^{2}}$
\end_inset

。
\end_layout

\begin_layout Standard
<h3>PRIM</h3>
\end_layout

\begin_layout Standard
PRIM的全称为Patient Rule Induction Method，呃看名字貌似是一种比较耐心的一步步递归的方法。果不其然，最开始就是我们要先定义“削皮
”：选取
\begin_inset Formula $(0,1)$
\end_inset

区间内任意的
\begin_inset Formula $\alpha$
\end_inset

，比如0.1，然后开始削皮~削皮的策略大概就是，选定一个维度，去掉这个维度比如最大10%或者最小10%的样本，然后看剩余部分的y均值有没有增长。总共有p个维度，所
以我们有
\begin_inset Formula $2^{p}$
\end_inset

中削皮法。选择其中上升最高的方法，削皮。然后继续来一遍，直到不能再增长的时候，停止，最终得到一块“精华”（贪心的算法）。之后，我们又要开始粘贴，即再贴上去一块儿
，看看是否能涨。这样我们得到一个
\begin_inset Formula $R_{1}$
\end_inset

区，区域均值为
\begin_inset Formula $\beta_{1}$
\end_inset

。
\end_layout

\begin_layout Standard
从总体中扔掉这
\begin_inset Formula $R_{1}$
\end_inset

区中的样本，然后继续做下去，比如一共J次，得到J个区域（这些区域的空间可能是有交集的），这样的策略称为Bump-Hunting（肿块寻找），最终得到若干个区域，
各区域中的样本均值作为
\begin_inset Formula $\beta$
\end_inset

（以第一次出现的空间为准）。
\end_layout

\begin_layout Subsection
HME
\end_layout

\begin_layout Standard
HME的全称为Hierarchical Mixture of Experts，听起来像是一个智囊团的感觉。画出来呢，就是一个树的形状。大致的思想就是，以概率分配
到各个枝条（软分类器），这样有
\begin_inset Formula $\frac{e^{\gamma_{i}x}}{\sum_{l}e^{\gamma_{i}x}}=P(j|x)$
\end_inset

。对于最下面一层的expert net，可以用分类树或者其他任何的分类器。对于HME，可用EM算法来解。两类的情形，就有
\begin_inset Formula $P(1|x)=\frac{e^{\gamma_{11}x}}{e^{\gamma_{11}x}+1}$
\end_inset

，有点像logit的变形有没有？
\end_layout

\begin_layout Standard
一句话的总结呢，就是这些方法看上去合理，比较容易follow the intuition，但是树类的结构弄得很难用现有的方法证明原理和一些相关性质（完全非线性呀
）。
\end_layout

\begin_layout Subsection
模型的总结：广义线性模型和基函数模型
\end_layout

\begin_layout Standard
从第一章到第九章，我们探索了很多个模型。说到底，模型就是
\begin_inset Formula $y=f(x)$
\end_inset

，然后我们有参数模型
\begin_inset Formula $y=f(x|\theta)$
\end_inset

，其中
\begin_inset Formula $\theta\in\Theta$
\end_inset

，
\begin_inset Formula $x\in\mathbb{R}^{p}$
\end_inset

。
\end_layout

\begin_layout Standard
最简单的来说，就是线性模型，形式为
\begin_inset Formula $f(x|\theta)=\mathbf{x\theta}=\sum\theta_{j}x_{j}$
\end_inset

，其中
\begin_inset Formula $1\leq j\leq p$
\end_inset

。显然，线性模型便是参数模型。
\end_layout

\begin_layout Standard
然后就是广义线性模型（GLM），我们可以先扩张x，就有
\begin_inset Formula $f(x|\theta)=\sum_{m=1}^{M}\theta_{m}\underbrace{h_{m}(x)}_{x's\, function}=\sum_{m=1}^{M}\theta_{m}\tilde{X_{m}}$
\end_inset

。说到底，就是已知的
\begin_inset Formula $h(\cdot)$
\end_inset

把数据从
\begin_inset Formula $\mathbb{R}^{p}$
\end_inset

空间映射到一个新的
\begin_inset Formula $\mathbb{R}^{M}$
\end_inset

空间。然后还可以把y再广义化，用一个可逆的已知函数
\begin_inset Formula $g(\cdot)$
\end_inset

变成
\begin_inset Formula $\tilde{y}$
\end_inset

。这样，就有
\begin_inset Formula $y=g[\sum_{m=1}^{M}\theta_{m}\tilde{X_{m}}]\Rightarrow$
\end_inset


\begin_inset Formula $g^{-1}(y)=\sum_{m=1}^{M}\theta_{m}\tilde{X_{m}}$
\end_inset

，最终说来
\begin_inset Formula $\tilde{Y}$
\end_inset

和
\begin_inset Formula $\tilde{X}$
\end_inset

这两个空间实现了一种线性的映射关系。
\end_layout

\begin_layout Standard
接下来我们就会看到一种形状很类似的树模型，但不是GLM：
\begin_inset Formula $f(x|T)=\sum_{m=1}^{M}I(x\in R_{m})$
\end_inset

。显然这里
\begin_inset Formula $R_{m}$
\end_inset

远非线性的，而且是变量。
\end_layout

\begin_layout Standard
接着参数化，我们就有
\begin_inset Formula $f(x|\theta)=\sum\beta_{m}g(x|\gamma_{m})$
\end_inset

，若
\begin_inset Formula $\gamma_{m}$
\end_inset

未知，即
\begin_inset Formula $g(\cdot)$
\end_inset

可变，则非GLM。这类的模型更适合的名字是：自适应基函数模型，即我们试图构造一些可以自适应的基函数，然后通过其线性组合构造最终的模型。这类模型经典如：树模型、G
MM（高斯混合模型）、神经网络等。
\end_layout

\begin_layout Section
Boost(AdaBoost)、自适应基函数模型、前向分布算法、指数损失函数
\end_layout

\begin_layout Standard
提升与梯度树
\end_layout

\begin_layout Subsection
Boost(AdaBoost)
\end_layout

\begin_layout Standard
这里讲的AdaBoost是仅针对二类分类器的提升。大致的思想就是，给我一个弱分类器，还你一个强分类器。听起来蛮神奇的对不对?
\end_layout

\begin_layout Standard
先说算法实现。
\end_layout

\begin_layout Standard
第一步：初始化。
\begin_inset Formula $f_{0}(x)=0$
\end_inset

,权重初始值 
\begin_inset Formula $w_{i}=\frac{1}{N}\,\forall i\in\{1,...,n\}$
\end_inset

。
\end_layout

\begin_layout Standard
第二步：迭代。
\end_layout

\begin_layout Standard
for m = 1 to M
\end_layout

\begin_layout Itemize
根据已有算法（即弱分类器）和{
\begin_inset Formula $w_{i}$
\end_inset

}得到一个分类器
\begin_inset Formula $G_{m}(x)$
\end_inset

.
\end_layout

\begin_layout Itemize
计算误差：
\begin_inset Formula $err_{m}=\frac{\sum_{1}^{N}I(y_{i}\neq G_{m}(x_{i}))\cdot w_{i}}{\sum_{i=1}^{N}w_{i}}$
\end_inset

，这里我们把权重进行归一化。
\end_layout

\begin_layout Itemize
计算
\begin_inset Formula $G_{m}$
\end_inset

权重：
\begin_inset Formula $\alpha_{m}=\log\frac{1-err_{m}}{err_{m}}$
\end_inset


\end_layout

\begin_layout Itemize
修改样本权重
\begin_inset Formula $w_{i}$
\end_inset

：
\begin_inset Formula $w_{i}=w_{i}\cdot\exp(\alpha_{m}\cdot I(y_{i}\neq G_{m}(x_{i}))$
\end_inset


\end_layout

\begin_layout Standard
也就是说，我们不断的生成新的权重，当分类器分错的时候更改权重。
\end_layout

\begin_layout Standard
第三步：输出。最终的分类器为前面的加权。
\end_layout

\begin_layout Standard
\begin_inset Formula $G(x)=sign(\sum_{m=1}^{M}\alpha_{m}G_{m}(x))$
\end_inset


\end_layout

\begin_layout Standard
这样就实现了从一个弱分类器改善到一个强分类器。这里弱分类器是指误差比随机猜的1/2少一点。
\end_layout

\begin_layout Standard
另注：在修改权重那一步的时候，也可以定义
\begin_inset Formula $\beta_{m}=\frac{\alpha_{m}}{2}$
\end_inset

，然后
\begin_inset Formula $w_{i}=w_{i}\cdot\begin{cases}
e^{\beta_{m}} & if\, right\\
e^{-\beta_{m}} & if\, wrong
\end{cases}$
\end_inset

，这样在最后的时候也可以改成
\begin_inset Formula $G(x)=sign(\sum_{m=1}^{M}\beta_{m}G_{m}(x))$
\end_inset

。总之这里的直觉是，如果分对了，那么权重下降；反之，分错的时候这些样本的权重上升。最后take average就可以了。
\end_layout

\begin_layout Subsection
自适应基函数模型、前向分布算法
\end_layout

\begin_layout Standard
之所以上面又引入
\begin_inset Formula $\beta_{m}$
\end_inset

，便是为了更好地理解这一类模型：自适应基函数模型。
\end_layout

\begin_layout Standard
1.
 我们称 
\begin_inset Formula $f(x)=\sum_{m=1}^{M}\beta_{m}b(x,\gamma_{m})$
\end_inset

为基函数模型，其中
\begin_inset Formula $\{b(x,\gamma),\gamma\in\Gamma\}$
\end_inset

成为基函数基。注意这里和GLM有很大的不同，广义线性模型后面的
\begin_inset Formula $\gamma_{m}$
\end_inset

为确定的。
\end_layout

\begin_layout Standard
2.
 前向分步算法。
\end_layout

\begin_layout Standard
数据集记作
\begin_inset Formula $\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

。定义一个损失函数，比如常见的
\begin_inset Formula $\mathcal{L}_{2}$
\end_inset

均方误差, 
\begin_inset Formula $(y-f(x))^{2}$
\end_inset

，或者0-1准则。
\end_layout

\begin_layout Standard
然后步骤为：
\end_layout

\begin_layout Itemize
初始化：
\begin_inset Formula $f_{0}(x)=0$
\end_inset


\end_layout

\begin_layout Itemize
迭代：For m=1 to M，
\begin_inset Formula $(\beta_{m},\gamma_{m})=\arg\min\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+\beta b(x_{i},\gamma))$
\end_inset


\end_layout

\begin_layout Itemize
令
\begin_inset Formula $f_{m}(x)=f_{m-1}(x)+\beta_{m}b(x_{i},\gamma)$
\end_inset

。
\end_layout

\begin_layout Itemize
输出
\begin_inset Formula $f_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Standard
这样我们就把这个最优化问题转变成了M步，每步只做一个参数的最优化（近似方法）。
\end_layout

\begin_layout Subsection
指数损失函数与AdaBoost
\end_layout

\begin_layout Standard
有了这么一个一般性的框架，我们就可以套用具体的形式。
\end_layout

\begin_layout Standard
1.
 定义指数损失函数： 
\begin_inset Formula $L(y,f(x))=\exp(-yf(x))$
\end_inset

。
\end_layout

\begin_layout Standard
2.
 两类分类、指数损失函数的自适应基函数模型。
\end_layout

\begin_layout Standard
前向分布算法：
\end_layout

\begin_layout Standard
(i) 
\begin_inset Formula 
\begin{eqnarray*}
 &  & \sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+\beta b(x_{i},\gamma))\\
 & = & \sum_{i=1}^{N}\exp\left[-y_{i}(f_{m-1}(x_{i})+\beta b(x_{i},\gamma))\right]\\
 & = & \sum_{i=1}^{N}w_{i}^{(m)}\cdot\exp(-\beta y_{i}b(x_{i},\gamma)),\, w_{i}^{(m)}=\exp(-y_{i}f_{m-1}(x_{i}))\\
 & = & e^{\beta}(\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)})+e^{-\beta}(\sum_{y=b(x_{i},\gamma)}w_{i}^{(m)})\\
 & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[e^{\beta}\frac{\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}+e^{-\beta}\frac{\sum_{y=b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}\right]
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
定义
\begin_inset Formula 
\[
err_{m}^{(\gamma)}=\frac{\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}}{\sum_{i=1}^{N}w_{i}^{(m)}}
\]

\end_inset


\end_layout

\begin_layout Standard
这样上式就可以化作
\begin_inset Formula 
\begin{eqnarray*}
 & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[e^{\beta}err_{m}^{(\gamma)}+e^{-\beta}(1-err_{m}^{(\gamma)})\right]\\
 & = & \sum_{i=1}^{N}w_{i}^{(m)}\left[(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})+e^{-\beta}\right]
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
(ii) 固定
\begin_inset Formula $\beta>0$
\end_inset

，优化
\begin_inset Formula $\gamma$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\sum_{y\neq b(x_{i},\gamma)}w_{i}^{(m)}=\sum_{i=1}^{N}w_{i}^{(m)}I(y\neq b(x_{i},\gamma))
\]

\end_inset


\end_layout

\begin_layout Standard
然后最小化，则
\begin_inset Formula $\gamma=\arg\min\sum_{i=1}^{N}w_{i}^{(m)}I(y\neq b(x_{i},\gamma))$
\end_inset

。假定
\begin_inset Formula $\gamma$
\end_inset

已被优化，然后继续。
\end_layout

\begin_layout Standard
(iii)优化
\begin_inset Formula $\beta$
\end_inset

。 
\begin_inset Formula $\beta_{m}=\arg\min\sum_{i=1}^{N}w_{i}^{(m)}\left[(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})+e^{-\beta}\right]$
\end_inset


\end_layout

\begin_layout Standard
取一阶条件FOC，则有
\begin_inset Formula 
\[
(e^{\beta}-e^{-\beta})err_{m}^{(\gamma)})-e^{-\beta}=0
\]

\end_inset


\end_layout

\begin_layout Standard
这样最后
\begin_inset Formula 
\[
\beta=\left[\log\frac{1-err_{m}}{err_{m}}\right]/2
\]

\end_inset


\end_layout

\begin_layout Standard
这样就看出来上面那个AdaBoost里面的
\begin_inset Formula $\beta$
\end_inset

是怎么来的了吧?
\end_layout

\begin_layout Standard
(iv) 回到AdaBoost
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{eqnarray*}
f_{m}(x) & = & f_{m-1}(x)+\beta_{m}b(x_{i},\gamma)\\
w_{i}^{(m)} & = & \exp(-y_{i}f_{m-1}(x))\\
 & = & \exp(-y_{i}[f_{m-1}(x_{i})+\beta_{m}b(x_{i},\gamma)])\\
 & = & w_{i}^{(m)}\exp(-y_{i}\beta_{m}b(x_{i},\gamma))\\
 & = & w_{i}^{(m)}\exp\beta_{m}\left[-y_{i}b(x_{i},\gamma)\right]
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
看出来最后的AdaBoost雏形了吧？
\end_layout

\begin_layout Section
梯度树提升算法(GTBA)
\end_layout

\begin_layout Standard
梯度树提升算法(GTBA, gradient tree boosting algorithm)
\end_layout

\begin_layout Standard
继续boosting类算法哎。小小预告一下，下节课会直接跳到随机森林，老师貌似是想把各种分类器都一下子讲到，然后有点前后照应的比较~真有意思，若是以前扔给我这种
问题我肯定run一个logit regression就不管了，现在倒是有各种线性的、广义线性的、非线性的模型可以试着玩了，爽哎~
\end_layout

\begin_layout Standard
------------------
\end_layout

\begin_layout Subsection
自适应基函数模型
\end_layout

\begin_layout Standard
小小的复习一下上节课那个框架。
\end_layout

\begin_layout Standard
1.
 数据。
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset


\end_layout

\begin_layout Standard
2.
 模型。 
\begin_inset Formula $f(x)=\sum_{m=1}^{M}\beta_{m}b(x,\gamma_{m})$
\end_inset

为基函数模型，其中
\begin_inset Formula $\{b(x,\gamma),\gamma\in\Gamma\}$
\end_inset

成为基函数集合。
\begin_inset Formula $\{(\beta_{m},\gamma_{m})\}_{1}^{M}$
\end_inset

为参数。
\end_layout

\begin_layout Standard
3.
 损失函数（准则）。 
\begin_inset Formula $\mathcal{L}(y,f(x))$
\end_inset

为损失函数，然后就转为一个优化问题：
\end_layout

\begin_layout Standard
\begin_inset Formula $\{(\beta_{m}^{*},\gamma_{m}^{*})\}_{1}^{M}=\arg\min\sum_{i=1}^{N}\mathcal{L}(y,f(x))=\arg\min\sum_{i=1}^{N}\mathcal{L}(y_{i},\sum_{m=1}^{M}\beta_{m}b(x,\gamma_{m}))$
\end_inset


\end_layout

\begin_layout Standard
4.
 算法。 前向分步算法。
\end_layout

\begin_layout Itemize
初始化：
\begin_inset Formula $f_{0}(x)=0$
\end_inset


\end_layout

\begin_layout Itemize
迭代：For m=1 to M，
\begin_inset Formula $(\beta_{m},\gamma_{m})=\arg\min\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_{i})+\beta b(x_{i},\gamma))$
\end_inset


\end_layout

\begin_layout Itemize
令
\begin_inset Formula $f_{m}(x)=f_{m-1}(x)+\beta_{m}b(x_{i},\gamma)$
\end_inset

。
\end_layout

\begin_layout Itemize
输出
\begin_inset Formula $f_{m}(x)$
\end_inset

。<
\end_layout

\begin_layout Standard
在此框架之下，除了上节课的Adaboost之外，还可以套用多种其他的基函数，然后1）定义损失函数 2）给出迭代那一步的优化算法，就可以实现一种boost提升算法
了。
\end_layout

\begin_layout Subsection
应用回归问题
\end_layout

\begin_layout Standard
先采用均方误差的损失函数，定义
\begin_inset Formula $\mathcal{L}(y,f(x))=(y-f(x))^{2}$
\end_inset

，这样就可以得到
\end_layout

\begin_layout Standard
\begin_inset Formula $(\beta,\gamma)=\arg\min\sum_{i=1}^{N}(y_{i}-f_{m-1}(x_{i})-\beta b(x_{i},\gamma))^{2}$
\end_inset


\end_layout

\begin_layout Standard
然后定义：
\end_layout

\begin_layout Standard
\begin_inset Formula $r_{im}\triangleq y_{i}-f_{m-1}(x_{i}),1\leq i\leq N$
\end_inset

，
\begin_inset Formula $\Rightarrow\arg\min_{\beta,\gamma}\sum_{i=1}^{N}(r_{im}-\beta b(x_{i},\gamma))^{2}$
\end_inset

。这里
\begin_inset Formula $(x_{i},r_{im})$
\end_inset

之后用回归树来求的话，就是梯度回归树算法。
\end_layout

\begin_layout Subsection
梯度回归树提升算法
\end_layout

\begin_layout Itemize
初始化：
\begin_inset Formula $f_{0}(x)=0$
\end_inset


\end_layout

\begin_layout Itemize
迭代：For m=1 to M，计算
\begin_inset Formula $r_{im}=y_{i}-f_{m-1}(x_{i})$
\end_inset

。由
\begin_inset Formula $(x_{i},r_{im})$
\end_inset

用回归树求得
\begin_inset Formula $T_{m}(x)$
\end_inset

.
\end_layout

\begin_layout Itemize
令
\begin_inset Formula $f_{m}(x)=f_{m-1}(x)+T_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Itemize
输出
\begin_inset Formula $f_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Subsection
GTBA，梯度树提升算法
\end_layout

\begin_layout Standard
先吹捧一下：这个算法就是此书作者本人开发的，然后已经搞出来了软件包，可以做回归也可以做分类，貌似效果还胜过随机森林（当然是作者自己给出的那些例子...）。
\end_layout

\begin_layout Standard
损失函数
\begin_inset Formula $\mathcal{L}(y,f(x))$
\end_inset

为可微的。
\end_layout

\begin_layout Standard
我们的优化目标是
\begin_inset Formula $\sum_{i=1}^{N}\mathcal{L}(y_{i},f(x_{i}))$
\end_inset

，也就是说实际上我们不是直接对
\begin_inset Formula $\mathcal{L}(y,f(x))$
\end_inset

进行优化，而是仅仅在所有观测的数据点上优化，所以仅跟
\begin_inset Formula $f(\cdot)$
\end_inset

在这些观测点上的值有关。感觉这里就是说，我们使用有限的观测到的信息来推断一个连续的函数，然后类推并用于其他未观测到的点。
\end_layout

\begin_layout Standard
定义：
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{f}=\left[\begin{array}{c}
f(x_{1})\\
f(x_{2})\\
\vdots\\
\vdots\\
f(x_{N})
\end{array}\right]$
\end_inset

，这样这个问题就从一个直接优化
\begin_inset Formula $f(\cdot)$
\end_inset

的泛函问题转化为一个优化多元函数的问题...而对于一个多元函数，我们可以直接用梯度下降法。定义梯度为：
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{f}^{0},\,\,\frac{\partial L}{\partial\bar{f}}|_{\bar{f}^{0}}=\bar{g}^{0}$
\end_inset

，这样
\begin_inset Formula $\bar{f}^{1}=\bar{f}^{0}-\bar{g}^{0}$
\end_inset

。类似的，我们可以定义
\begin_inset Formula $\bar{f}^{m}=\bar{f}^{m-1}-\tau\bar{g}^{m-1}$
\end_inset

，其中
\begin_inset Formula $\bar{g}^{m-1}=\frac{\partial L}{\partial\bar{f}}|_{\bar{f}^{m-1}}$
\end_inset

。累加起来，就是
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{f}^{m}=\bar{f}^{0}-\tau\bar{g}^{m-1}-\cdots-\tau\bar{g}^{0}$
\end_inset

，这里
\begin_inset Formula $\tau$
\end_inset

可以是常量也可以随着
\begin_inset Formula $m$
\end_inset

改变。
\end_layout

\begin_layout Standard
定义完梯度下降之后，就是GTBA算法了。
\end_layout

\begin_layout Itemize
初始化。
\end_layout

\begin_layout Itemize
迭代：For m=1 to M，计算
\begin_inset Formula $r_{im}=\frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}|f_{m-1}$
\end_inset

，然后由
\begin_inset Formula $\{(x_{i},r_{im}),1\leq i\leq N\}$
\end_inset

用回归树求得
\begin_inset Formula $T_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Itemize
令
\begin_inset Formula $f_{m}(x)=f_{m-1}(x)+T_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Itemize
输出
\begin_inset Formula $f_{m}(x)$
\end_inset

。
\end_layout

\begin_layout Subsubsection
一些梳理
\end_layout

\begin_layout Standard
1.
 参数。这里显然有如下参数需要设定：
\end_layout

\begin_layout Itemize
M：迭代次数。这是这个算法最主要的参数，需要用Cross-validation来算。
\end_layout

\begin_layout Itemize
J：树的大小。建议4-8，默认为6。
\end_layout

\begin_layout Itemize
\begin_inset Formula $\mu$
\end_inset

：收缩系数。
\begin_inset Formula $f_{m}(x)=f_{m-1}(x)+\mu T_{m}(x)$
\end_inset

这里可以加上
\begin_inset Formula $\mu$
\end_inset

这个参数，决定收缩的速度，0-1之间。
\end_layout

\begin_layout Itemize
\begin_inset Formula $\eta$
\end_inset

：次采样率，0-1直接，默认0.5。用于做subsampling。
\end_layout

\begin_layout Standard
2.
 特征变量评价
\end_layout

\begin_layout Standard
这个算法的一大优势就是可以给出各个自变量的评价。比如
\begin_inset Formula $P>N$
\end_inset

的时候我们可能面临特征变量选择问题。
\end_layout

\begin_layout Standard
用t表示树中的节点，
\begin_inset Formula $v(t)$
\end_inset

表示t节点所用的变量，
\begin_inset Formula $\tau^{2}(t)$
\end_inset

表示t节点产生的均方误差的减小值。之后定义：
\end_layout

\begin_layout Standard
\begin_inset Formula $x^{\tau}=\sum_{t}I(v(t)=x^{\tau})\tau^{2}(t)$
\end_inset

，可用这个值来刻画变量的重要性，从而进行特征评价。
\end_layout

\begin_layout Standard
3.
 通用工具
\end_layout

\begin_layout Standard
该算法对于数据无特殊要求，有一批
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

都可以扔进去试试，故可以作为其他算法的benchmark。
\end_layout

\begin_layout Standard
此外，从贝叶斯分类器的角度，我们要找的是
\begin_inset Formula $f(x)=\arg\max P(G|x)$
\end_inset

，这样除了原有可以观测到的
\begin_inset Formula $(x_{i},G_{i})$
\end_inset

之上，还可以衍生出一个
\begin_inset Formula $G_{i}$
\end_inset

向量，即
\begin_inset Formula $G_{i}=(0,0,..,1,..,0)$
\end_inset

，第k个位置为1如果观测到的
\begin_inset Formula $(x_{i})$
\end_inset

对应第k类。一下子就可以扩展整个数据集，也可以进一步对每类都赋一个概率，不单单是0-1这样。
\end_layout

\begin_layout Section
随机森林(Random Forest)
\end_layout

\begin_layout Standard
第十五章 随机森林(Random Forest)
\end_layout

\begin_layout Standard
终于讲到这个神奇的算法了...若是百年前的算命术士们知道有此等高深之术，怕是要写成一本《随机真经》作为武林宝典世代相传了吧？猜得准才是王道嘛。
\end_layout

\begin_layout Standard
p.s.
 以前没看过的童鞋不要急，这节课只是从boosting直接跳讲到十五章，并不是已经快结课啦。
\end_layout

\begin_layout Standard
--------------- 
\end_layout

\begin_layout Subsection
定义和算法 
\end_layout

\begin_layout Subsubsection
算法：
\end_layout

\begin_layout Standard
1.
 For b = 1 to B
\end_layout

\begin_layout Standard
生成一个自生样本
\begin_inset Formula $D_{b}$
\end_inset

(via bootstrap) 由
\begin_inset Formula $D_{b}$
\end_inset

生成树
\begin_inset Formula $T_{b}$
\end_inset

:
\end_layout

\begin_layout Standard
随机选取m(
\begin_inset Formula $\leq p$
\end_inset

)个变量（相应的
\begin_inset Formula $D_{b}^{p}\rightarrow D_{b}^{m}$
\end_inset

，取了
\begin_inset Formula $m$
\end_inset

维子集）。一切的神奇都在于这里是随机降维的。 由
\begin_inset Formula $D_{b}^{m}$
\end_inset

生成树
\begin_inset Formula $T_{b}$
\end_inset

。
\end_layout

\begin_layout Standard
输出
\begin_inset Formula $\{T_{b}(x)\}_{b=1}^{B}$
\end_inset

(即森林）。
\end_layout

\begin_layout Standard
随机森林算法的参数主要就是决策树的参数
\begin_inset Formula $n_{min}$
\end_inset

，用来控制树的生长的：保证每个叶子中的实例数不大于
\begin_inset Formula $n_{min}$
\end_inset

。 
\end_layout

\begin_layout Subsubsection
应用 
\end_layout

\begin_layout Standard
1) 回归 在回归的情况下采取均值，最终输出的就是
\begin_inset Formula $\hat{f}(x)=\frac{1}{B}\sum_{b=1}^{B}T_{b}(x)$
\end_inset

.
\end_layout

\begin_layout Standard
2) 分类 分类的情况下进行投票，
\begin_inset Formula $\hat{G}(x)=\max\,\, vote(\{T_{b}(x)\}_{b=1}^{B})$
\end_inset

，得票最多的那类获胜。 参数 总结的来看，参数主要有如下几个：
\end_layout

\begin_layout Itemize
B：试验次数。一般为几百到几千，所以是computational intensive.
 
\end_layout

\begin_layout Itemize
m：降维的力度。作者建议回归的情况下采用
\begin_inset Formula $p/3$
\end_inset

，然后分类的情况下采用
\begin_inset Formula $[\sqrt{p}]$
\end_inset

。
\end_layout

\begin_layout Itemize
\begin_inset Formula $n_{min}$
\end_inset

：建议回归的时候设为5，分类的时候设为1（彻底分到底）
\end_layout

\begin_layout Standard
伪代码 其实上面已经写的比较清楚了...我只是再抄个伪代码过来而已。
\end_layout

\begin_layout Quote
select m variables at random out of the M variables
\end_layout

\begin_layout Quote
For j = 1 ..
 m
\end_layout

\begin_layout Quote
If j'th attribute is categorical
\end_layout

\begin_layout Quote
\begin_inset Formula $IG_{j}=IG(Y|X_{j})$
\end_inset

(see Information Gain)
\end_layout

\begin_layout Quote
Else (j'th attribute is real-valued)
\end_layout

\begin_layout Quote
\begin_inset Formula $IG_{j}=IG*(Y|X_{j})$
\end_inset

(see Information Gain)
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $j*=argmax_{j}IG_{j}$
\end_inset

 (this is the splitting attribute we'll use)
\end_layout

\begin_layout Quote
If j{*} is categorical then
\end_layout

\begin_layout Quote
For each value v of the j'th attribute
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $X^{v}$
\end_inset

 = subset of rows of X in which
\begin_inset Formula $X_{i}j=v$
\end_inset

.
 Let 
\begin_inset Formula $Y^{v}$
\end_inset

= corresponding subset of Y
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $Child^{v}$
\end_inset

 = LearnUnprunedTree
\begin_inset Formula $(X^{v},Y^{v})$
\end_inset


\end_layout

\begin_layout Quote
Return a decision tree node, splitting on j'th attribute.
 The number of children equals the number of values of the j'th attribute,
 and the v'th child is Childv
\end_layout

\begin_layout Quote
Else j{*} is real-valued and let t be the best split threshold
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $X^{LO}$
\end_inset

 = subset of rows of X in which 
\begin_inset Formula $X_{ij}\leq t$
\end_inset

.
 
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $Y^{LO}$
\end_inset

 = corresponding subset of Y
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $Child^{LO}$
\end_inset

= Learn Unpruned Tree
\begin_inset Formula $(X^{LO},Y^{LO})$
\end_inset


\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $X^{HI}$
\end_inset

 = subset of rows of X in which 
\begin_inset Formula $X_{ij}>t$
\end_inset

.
 
\end_layout

\begin_layout Quote
Let
\begin_inset Formula $Y^{HI}$
\end_inset

= corresponding subset of Y
\end_layout

\begin_layout Quote
Let 
\begin_inset Formula $Child^{HI}$
\end_inset

= Learn Unpruned Tree
\begin_inset Formula $(X^{HI},Y^{HI})$
\end_inset


\end_layout

\begin_layout Quote
Return a decision tree node, splitting on j'th attribute.
 It has two children corresponding to whether the j'th attribute is above
 or below the given threshold.
 2.
 为什么要“随机” bootstrap：通过多次重抽样减小误差。
\end_layout

\begin_layout Standard
考虑下面的情况：
\end_layout

\begin_layout Standard
1) 
\begin_inset Formula $X_{1},...,X_{N}$
\end_inset

为随机变量，且$E(X)=0$,$E(x^{2})=
\backslash
sigma^{2}$。
\end_layout

\begin_layout Standard
(i)当
\begin_inset Formula $X_{1},...,X_{N}$
\end_inset

相互独立的时候，
\begin_inset Formula $E\frac{x_{1}+...+x_{N}}{N}=0$
\end_inset

，且
\begin_inset Formula $E\left(\frac{x_{1}+...+x_{N}}{N}\right)^{2}=\frac{\sigma^{2}}{N}$
\end_inset

。
\end_layout

\begin_layout Standard
(ii)当
\begin_inset Formula $X_{1},...,X_{N}$
\end_inset

相互不独立的时候，我们有
\begin_inset Formula $E(x_{i}x_{j})=\rho\sigma^{2}$
\end_inset

。这样接下来就有
\end_layout

\begin_layout Standard
\begin_inset Formula $E\left(\frac{x_{1}+...+x_{N}}{N}\right)^{2}=\frac{1}{N^{2}}E(\sigma^{2}N+2\frac{(N-1)N}{2}\rho\sigma^{2})=\rho\sigma^{2}+\frac{1-\rho}{N}\sigma^{2}$
\end_inset


\end_layout

\begin_layout Standard
如斯，仅使用bootstrap的话压缩的是方差的第二部分，而随机选的的M可以减小样本之间的相关性，从而减少不同树之间的相关性。
\end_layout

\begin_layout Standard
2）OOB(out of bag)实例
\end_layout

\begin_layout Standard
OOB的概率：
\begin_inset Formula $(1-\frac{1}{N})^{N}\underrightarrow{N\rightarrow\infty}e^{-1}\approx33\%$
\end_inset

。这样就是说，在一次抽样中约有1/3的样本没有被抽到。
\end_layout

\begin_layout Standard
两次bootstrap抽样的话，样本约有40%的重叠，这样的重叠概率会影响到上面的(ii)中，两次抽样得到的样本重叠很高，相互不独立。
\end_layout

\begin_layout Standard
这样我们用67%的样本训练数据，用剩下33%来测试。
\end_layout

\begin_layout Standard
3.
 其他应用
\end_layout

\begin_layout Standard
1)变量的重要性（feature selection，俗称的特征选择）
\end_layout

\begin_layout Standard
第一种方法可以和上节课梯度树那里的一样，用
\begin_inset Formula $\sum_{t}I(v(t)=x^{i})\tau^{2}(t)$
\end_inset

来刻画变量的重要性。
\end_layout

\begin_layout Standard
第二种方法则是比较有意思。对于一棵树
\begin_inset Formula $T_{b}(x)$
\end_inset

，我们用OOB样本可以得到测试误差1。
\end_layout

\begin_layout Standard
OOB样本大概长成这个样子：
\end_layout

\begin_layout Standard
\begin_inset Formula $OOB=\left[\begin{array}{ccccc}
x_{11} & \cdots & x{}_{1j} & \cdots & x_{1p}\\
\vdots & \vdots & \vdots & \vdots & \vdots\\
x_{k1} & \cdots & x{}_{kj} & \cdots & x_{kp}
\end{array}\right]$
\end_inset

，样本量足够大的情况下
\begin_inset Formula $k\approx\frac{1}{3}N$
\end_inset

。
\end_layout

\begin_layout Standard
然后随机改变OOB样本的第j列：保持其他列不变，对第j列进行随机的上下置换，得到误差2。至此，我们可以用误差1-误差2来刻画变量j的重要性。当然这里loss
 function可以自己定。这里的大致思想就是，如果一个变量j足够重要，那么改变它会极大的增加测试误差；反之，如果改变它测试误差没有增大，则说明该变量不是那么
的重要。（典型的实用主义啊！管用才是真，才不管他什么证明不证明呢！自从开始接触机器学习的这些算法，我真的是被他们的各种天真烂漫的想法打败的一塌糊涂，只要直觉上过
得去、实际效果看起来比较好就可以了呢，规则真简单）。
\end_layout

\begin_layout Standard
2) 相似图(proximity plots)
\end_layout

\begin_layout Standard
除了用户变量选择之外，Random Forest也可以给出各个观测实例之间的相似度。
\end_layout

\begin_layout Standard
Proximity plots记作
\begin_inset Formula $P(i,j)|_{i,j=1}^{N}=$
\end_inset

在一个叶子结点
\begin_inset Formula $x_{i},x_{j}$
\end_inset

同时出现的次数，其实大致就是一个相关性矩阵的样子。思想其实就是，如果两个观测样本之间比较相关，他们在树分枝的过程中就比较难以分开，所以会经常一起出现。我们故而可
以用一起出现的次数给这种相似程度打分。 树类算法 至此，我们大概一口气过掉了所有跟树相关的算法。
\end_layout

\begin_layout Standard
先是单一的决策树，然后是基于已有弱分类器的改良算法，比如梯度树，然后就是和梯度树不相伯仲的随机森林。我感觉随机森林真的是起了一个好名字，在我没学机器学习之前就听
到无数人跟我说起随机森林，而梯度树却只是正儿八经开始看了才记住的名字...
\end_layout

\begin_layout Standard
下下周开始，会依次讲到神经网络和SVM...看来supervised learning就快拉上帷幕咯。
\end_layout

\begin_layout Section
神经网络（一）
\end_layout

\begin_layout Standard
神经网络(Start of Deep Learning?)
\end_layout

\begin_layout Standard
神经网络的历史和大起大落还是可以八卦一下的...
\end_layout

\begin_layout Quote
第一波：人工神经网络起源于上世纪40年代，到今天已经70年历史了。第一个神经元模型是1943年McCulloch和Pitts提出的，称为threshold
 logic，它可以实现一些逻辑运算的功能。自此以后，神经网络的研究分化为两个方向，一个专注于生物信息处理的过程，称为生物神经网络；一个专注于工程应用，称为人工
神经网络。
\end_layout

\begin_layout Quote
第二波：上世纪80年代神经网络的研究热潮。带反馈的神经网络开始兴起，其中以Stephen Grossberg和John Hopfield的工作最具代表性。很多复
杂的认知现象比如联想记忆都可以用反馈神经网络进行模拟和解释。一位在神经网络领域非常资深的学者跟我聊天时说，在那个年代，只要你的文章跟神经网络扯上点关系，无论什么
杂志，都很容易发表。
\end_layout

\begin_layout Quote
第三波：直到2006年深度网络（deep network）和深度学习（deep learning）概念的提出，神经网络又开始焕发一轮新的生命。深度网络，从字面上
理解就是深层次的神经网络。至于为什么不沿用以前的术语“多层神经网络”，个人猜测可能是为了与以前的神经网络相区分，表示这是一个新的概念。这个名词由多伦多大学的Ge
off Hinton研究组于2006年创造[3]。事实上，Hinton研究组提出的这个深度网络从结构上讲与传统的多层感知机没有什么不同，并且在做有监督学习时算法
也是一样的。唯一的不同是这个网络在做有监督学习前要先做非监督学习，然后将非监督学习学到的权值当作有监督学习的初值进行训练。
\end_layout

\begin_layout Standard
上述来自：http://www.caai.cn/contents/118/1934.html
\end_layout

\begin_layout Standard
有没有感觉最近deep learning热得一塌糊涂？好像是个人都知道有这么个词儿但是真正知道他干什么的、怎么来的的人却不怎么多。嗯，貌似从这节课开始，要掀起d
eep learning的篇章咯。顿时感觉好洋气哇。
\end_layout

\begin_layout Standard
----------正文的分割线-----------
\end_layout

\begin_layout Standard
这节课先介绍七十多年前的Perceptron模型。
\end_layout

\begin_layout Subsection
Perceptron模型。
\end_layout

\begin_layout Standard
1.
 神经元
\end_layout

\begin_layout Standard
大致就是这样一张图片。神经元细胞有个大大的细胞核，然后有个轴突。如果神经元细胞拼在一起，可以构成一个神经网络。
\end_layout

\begin_layout Standard
（我觉得这个细胞模型和后面的东西其实没太直接的联系...就是一个很好看的图...）
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename ../../perceptron.gif

\end_inset


\end_layout

\begin_layout Standard
2.
 Perceptron模型
\end_layout

\begin_layout Standard
Perceptron模型有若干输入：
\begin_inset Formula $x_{1},...,x_{n}$
\end_inset

，标记为
\begin_inset Formula $\{x_{n}\}$
\end_inset

序列。
\end_layout

\begin_layout Standard
每个输入都有一个权重（某种程度上可以理解为信息损失）：
\begin_inset Formula $w_{1},...,w_{n}$
\end_inset

，标记为
\begin_inset Formula $\{w_{n}\}$
\end_inset

序列。
\end_layout

\begin_layout Standard
最后每个“细胞”还有一个偏（门限）：b，即我们常说的常数项截距。
\end_layout

\begin_layout Standard
最终的状态：
\begin_inset Formula $s=\sum_{i=1}^{N}x_{i}w_{i}-b$
\end_inset


\end_layout

\begin_layout Standard
输出：
\begin_inset Formula $y=\sigma(s)$
\end_inset

，比较简单的情况下，
\begin_inset Formula $\sigma(\cdot)$
\end_inset

可以是一个二元输出函数，比如
\begin_inset Formula $\sigma(s)=\begin{cases}
1 & s>0\\
0 & s<0
\end{cases}$
\end_inset

或者写作
\begin_inset Formula $\sigma(s)=I(s>0)$
\end_inset

。但是比较讨厌的是这个函数不可微，所以我们可以转成一个可微的函数（有点类似logistic regression的思路，用概率的密度函数来做）。
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename ../../sigmoid.gif

\end_inset


\end_layout

\begin_layout Standard
可微的情况下，这个输出就是：
\begin_inset Formula $y=\frac{1}{1+e^{-s}}$
\end_inset

，这样就可以做成一个光滑的曲线了。
\end_layout

\begin_layout Standard
3.
 Perceptron算法
\end_layout

\begin_layout Standard
给定一批数据
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

, 我们希望求得
\begin_inset Formula $w^{*}$
\end_inset

使得
\begin_inset Formula $w\cdot x_{i}>0$
\end_inset

，如果
\begin_inset Formula $y_{i}=1$
\end_inset

；否则，
\begin_inset Formula $w\cdot x_{i}<0$
\end_inset

(即
\begin_inset Formula $w^{*}(y_{i}x_{i})>0$
\end_inset

。
\end_layout

\begin_layout Standard
算法：先是我们可以不断重复的无限复制数据：
\begin_inset Formula $(x_{1}y_{1}),...,(x_{n},y_{n}),(x_{1}y_{1}),...,(x_{n},y_{n}),(x_{1}y_{1}),...,(x_{n},y_{n})...$
\end_inset


\end_layout

\begin_layout Standard
然后初始化：
\begin_inset Formula $k=0$
\end_inset

,
\begin_inset Formula $w(k)=0$
\end_inset

。
\end_layout

\begin_layout Standard
开始循环：
\end_layout

\begin_layout Standard
For 
\begin_inset Formula $k=1,2,...$
\end_inset


\end_layout

\begin_layout Standard
IF 
\begin_inset Formula $w(k)\cdot(y(k)x(k))<0$
\end_inset

，then 
\begin_inset Formula $w(k+1)=w(k)+y(k)x(k)$
\end_inset


\end_layout

\begin_layout Standard
定理 如果存在w使得
\begin_inset Formula $w^{*}(y_{i}x_{i})>0,\,\forall i$
\end_inset

成立（即平面线性可分），则Perceptron算法在有限步收敛。
\end_layout

\begin_layout Standard
证明：
\end_layout

\begin_layout Itemize
\begin_inset Formula $w(k)=\sum_{k=1}^{K-1}y(k)x(k)$
\end_inset

（仅计算改过的）
\begin_inset Formula $=w(k-1)+\cdots$
\end_inset


\begin_inset Formula $\Rightarrow\left\Vert w(k)\right\Vert ^{2}\leq\left\Vert x_{1}\right\Vert ^{2}+\cdots\left\Vert x_{k-1}\right\Vert ^{2}\leq(k-1)\underbrace{\max\left\Vert x_{i}\right\Vert }_{Constant}$
\end_inset

。
\end_layout

\begin_layout Itemize
存在
\begin_inset Formula $w*$
\end_inset

使得
\begin_inset Formula $w^{*}(y_{i}x_{i})>0,\,\forall i$
\end_inset

，那么我们有
\begin_inset Formula $\delta=\min w^{*}(y_{i}x_{i})>0$
\end_inset

，
\begin_inset Formula $\left\Vert w^{*}w(k)\right\Vert ^{2}\leq\left\Vert w^{*}\right\Vert ^{2}\left\Vert w(k)\right\Vert ^{2}$
\end_inset

，同时我们有
\begin_inset Formula $\left\Vert w^{*}w(k)\right\Vert ^{2}=\left\Vert w^{*}\sum y(k)x(k)\right\Vert ^{2}=\left\Vert \sum w^{*}y(k)x(k)\right\Vert ^{2}\geq K^{2}\delta^{2}$
\end_inset


\end_layout

\begin_layout Standard
这样就会有
\begin_inset Formula $KC\geq\left\Vert w(k)\right\Vert ^{2}\geq\frac{1}{\left\Vert w^{*}\right\Vert ^{2}}K^{2}\delta^{2}$
\end_inset

，当k趋近无穷大的时候，显然左式不成立。所以必有在某个k的时候停止迭代。
\end_layout

\begin_layout Standard
4.
 推广至多类——Collins算法（2002）
\end_layout

\begin_layout Standard
(1) Collins表述
\end_layout

\begin_layout Standard
给定 
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\},\Phi(x,y)\in\mathbb{R}$
\end_inset

，求w使得
\begin_inset Formula $y_{i}^{*}=\arg\max_{y\neq y_{i}}w\cdot\Phi(x_{i},y),\forall i$
\end_inset

，除了
\begin_inset Formula $y_{i}$
\end_inset

外最大。这样
\begin_inset Formula $w\cdot\Phi(x_{i},y_{i})>w\cdot\Phi(x_{i},y),y\neq y_{i}$
\end_inset

。
\begin_inset Formula $y^{*}=\arg\max_{y}\Phi(x,y)$
\end_inset

。
\end_layout

\begin_layout Standard
(2)算法：
\begin_inset Formula $\Delta\Phi(x_{i},y_{i}^{*})=\Phi(x_{i},y_{i})-\Phi(x_{i},y_{i}^{*})$
\end_inset

, 
\begin_inset Formula $y_{i}^{*}=\arg\min_{y\neq y_{i}}w\cdot\Phi(x_{i},y)$
\end_inset

。
\end_layout

\begin_layout Standard
初始化：
\begin_inset Formula $k=0$
\end_inset

,
\begin_inset Formula $w(k)=0$
\end_inset

.
\end_layout

\begin_layout Standard
For 
\begin_inset Formula $k=1,2,...$
\end_inset


\end_layout

\begin_layout Standard
计算 
\begin_inset Formula $\Delta\Phi(x_{i},y_{i}^{*}(k))<0$
\end_inset

，
\begin_inset Formula $w(k+1)=w(k)+\Delta\Phi(x(k),y^{*}(k))$
\end_inset


\end_layout

\begin_layout Standard
输出：
\begin_inset Formula $w^{*}=\frac{1}{K}\sum_{1}^{K}w(k)$
\end_inset


\end_layout

\begin_layout Standard
(3)定理。若为线性平面可分，则在有限步内收敛。
\end_layout

\begin_layout Section
神经网络（二）
\end_layout

\begin_layout Standard
前馈神经网，BP算法，AE（自编码器，Auto-Encoders)
\end_layout

\begin_layout Subsection
前馈神经网（Multilayer Feedforward Network）
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename ../../fig 12.8.jpg

\end_inset


\end_layout

\begin_layout Standard
前馈神经网大致就是这个样子，一层一层的结构。这样，我们就由第一代的神经元系统繁殖出来了一个神经元群落...看起来很高深的样子。
\end_layout

\begin_layout Standard
先说一些参数和记号：
\end_layout

\begin_layout Itemize
L：网络的层次
\begin_inset Formula $n_{l}$
\end_inset

，
\begin_inset Formula $1\leq l\leq L$
\end_inset

：表示第
\begin_inset Formula $l$
\end_inset

层中神经元的个数。特别的，
\begin_inset Formula $n_{0}=p$
\end_inset

为所有输入变量的个数（x的维数），
\begin_inset Formula $n_{L}$
\end_inset

是网络输出的个数。
\end_layout

\begin_layout Itemize
\begin_inset Formula $w_{jk}^{l}$
\end_inset

，
\begin_inset Formula $1\leq j\leq n_{l}$
\end_inset

，
\begin_inset Formula $1\leq k\leq n_{l-1}$
\end_inset

：相邻两层（
\begin_inset Formula $l$
\end_inset

到
\begin_inset Formula $l-1$
\end_inset

)之间的连接的权重。
\end_layout

\begin_layout Itemize
\begin_inset Formula $b_{j}^{l}$
\end_inset

：第
\begin_inset Formula $l$
\end_inset

层第
\begin_inset Formula $j$
\end_inset

个神经元的偏置值。
\end_layout

\begin_layout Itemize
\begin_inset Formula $s_{j}^{l}$
\end_inset

,
\begin_inset Formula $1\leq j\leq n_{l}$
\end_inset

,
\begin_inset Formula $1\leq l\leq L$
\end_inset

：第
\begin_inset Formula $l$
\end_inset

层第
\begin_inset Formula $j$
\end_inset

个神经元的状态值。
\end_layout

\begin_layout Itemize
\begin_inset Formula $a_{j}^{l}$
\end_inset

,
\begin_inset Formula $1\leq j\leq n_{l}$
\end_inset

,
\begin_inset Formula $1\leq l\leq L$
\end_inset

：第
\begin_inset Formula $l$
\end_inset

层第
\begin_inset Formula $j$
\end_inset

个神经元的活性（activation)，或称为输出。
\end_layout

\begin_layout Standard
基本关系：
\end_layout

\begin_layout Standard
\begin_inset Formula $a_{j}^{l}=\sigma(s_{j}^{l})$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s_{j}^{l+1}=\sum_{k=1}^{n_{l}}(w_{jk}^{k+1}a_{k}^{l})+b_{j}^{l+1}=\sum_{k=1}^{n_{l}}(w_{jk}^{k+1}\sigma(s_{j}^{l}))+b_{j}^{l+1}$
\end_inset

，
\begin_inset Formula $1\leq j\leq n_{l+1}$
\end_inset

，
\begin_inset Formula $1\leq l\leq L$
\end_inset


\end_layout

\begin_layout Standard
模型：
\begin_inset Formula $\{f(x;w,b)\}$
\end_inset

为
\begin_inset Formula $\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}^{n_{L}}$
\end_inset

的映射。
\end_layout

\begin_layout Subsection
BP算法（网络学习/拟合）
\end_layout

\begin_layout Standard
给定数据
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，定义
\end_layout

\begin_layout Standard
\begin_inset Formula $J(w,b;x(i),y(i))=\frac{1}{2}[y(i)-f(x(i);w,b)]^{2}$
\end_inset


\end_layout

\begin_layout Standard
那么
\end_layout

\begin_layout Standard
\begin_inset Formula $J(w,b)=\underbrace{\frac{1}{N}\sum_{i=1}^{N}J(w,b;x(i),y(i))}_{empirical\, error}+\underbrace{\sum_{l=1}^{L}\sum_{j=1}^{n_{l}}\sum_{k=1}^{n_{l-1}}(w_{jk}^{l})^{2}\frac{\lambda}{2}}_{regularization}$
\end_inset


\end_layout

\begin_layout Standard
接下来的拟合优化问题就是最小化
\begin_inset Formula $J(w,b)$
\end_inset

。这里可以采用梯度下降：
\end_layout

\begin_layout Standard
\begin_inset Formula $w^{t+1}\leftarrow w^{t}-\alpha\frac{\partial J}{\partial w}|_{t}$
\end_inset

，
\begin_inset Formula $b^{t+1}\leftarrow b^{t}-\alpha\frac{\partial J}{\partial b}|_{t}$
\end_inset

，所以需要求得这两个梯度（偏导）项。
\end_layout

\begin_layout Standard
定义
\begin_inset Formula $\delta_{j}^{l}=\frac{\partial J(w,b;x,y)}{\partial s_{j}^{l}}$
\end_inset

，这样
\begin_inset Formula $\frac{\partial J(w,b;x,y)}{\partial w_{jk}^{l}}=\frac{\partial J(w,b;x,y)}{\partial s_{j}^{l}}\frac{\partial s_{j}^{l}}{\partial w_{jk}^{l}}=\delta_{j}^{l}\sigma(s_{k}^{l-1})$
\end_inset

，其中
\begin_inset Formula $s_{j}^{l}=\sum_{k=1}^{n_{l-1}}w_{jk}^{l}\sigma(s_{k}^{l-1})+b_{j}^{l}$
\end_inset

。
\end_layout

\begin_layout Standard
类似的，
\begin_inset Formula $\frac{\partial J(w,b;x,y)}{\partial b_{j}^{l}}=\frac{\partial J(w,b;x,y)}{\partial s_{j}^{l}}\frac{\partial s_{j}^{l}}{\partial b_{j}^{l}}=\delta_{j}^{l}$
\end_inset


\end_layout

\begin_layout Standard
为了解
\begin_inset Formula $\delta_{j}^{l}$
\end_inset

这个东西，我们需要后向递归。
\end_layout

\begin_layout Standard
首先在第L层：
\begin_inset Formula $\frac{\partial}{\partial s_{j}^{l}}\frac{1}{2}(y-a_{j}^{L})^{2}=\frac{\partial}{\partial s_{j}^{l}}\frac{1}{2}(y-\sigma(s_{j}^{L}))^{2}=(y-a_{j}^{L})\sigma'(s_{j}^{L})$
\end_inset

，然后
\begin_inset Formula $\sigma'(s_{j}^{L})=\sigma(s)(1-\sigma(s))$
\end_inset


\end_layout

\begin_layout Standard
For L-1,...,1，我们有
\begin_inset Formula $\delta_{j}^{l}=\frac{\partial J}{\partial s_{j}^{l}}=\sum_{k=1}^{n_{l+1}}\frac{\partial J}{\partial s_{j}^{l+1}}\frac{\partial s_{j}^{l+1}}{\partial s_{j}^{l}}=\sum_{k=1}^{n_{l+1}}\delta_{k}^{l+1}w_{jk}^{l+1}\sigma(s_{j}^{l})$
\end_inset

，这样就一直可以迭代反推至第一层。
\end_layout

\begin_layout Subsubsection
AE（自编码器，Auto-Encoders)
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename ../../auto-encoder.jpg

\end_inset


\end_layout

\begin_layout Standard
自编码器可以算是一个简化的神经网，大致只有三层：0，1，2。其中输入是x，输出也是x，但是中间进行了一个过滤。直观的讲，就像一个文件压缩了一下，又解压缩。中间压
缩包的体积要比源文件小，但是信息却基本没有损失。
\end_layout

\begin_layout Standard
AE基本上想达到两个目标：
\end_layout

\begin_layout Standard
1.
 
\begin_inset Formula $n_{1}<n_{0}$
\end_inset

，即中间那层的维数小于原始输入的维数p。
\end_layout

\begin_layout Standard
2.
 或者输出的均值非常小，即从第一层到最上面一层的输出较为稀疏，不是很强烈的关联。
\end_layout

\begin_layout Standard
下节课会讲到SVM。
\end_layout

\begin_layout Section
SVM（一）
\end_layout

\begin_layout Standard
支持向量机——最大边距方法
\end_layout

\begin_layout Standard
前言：这节课我人在北京，只能回来之后抄一下笔记，然后对着书和wiki理解一下....有什么错误还请大家及时指出。
\end_layout

\begin_layout Standard
------------------------------
\end_layout

\begin_layout Subsection
背景
\end_layout

\begin_layout Itemize
问题：两类分类问题
\end_layout

\begin_layout Itemize
数据：有标识、有监督
\begin_inset Formula $\mathcal{D}=\left\{ (\mathbf{x}_{i},y_{i})\mid\mathbf{x}_{i}\in\mathbb{R}^{p},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n}$
\end_inset


\end_layout

\begin_layout Itemize
模型：
\begin_inset Formula $f(x)=sign(wx+b)$
\end_inset

，线性模型
\end_layout

\begin_layout Itemize
准则：最大边距
\end_layout

\begin_layout Standard
先说一下个人理解的SVM的直觉。下图来自wiki。二次元中的SVM就是想找到一条直线（或者对应高维空间下的超平面）来尽可能的分割开两组数据。比如图中H3和H2这
两条直线虽然都可以分开这两组数据，但是显然H3离两组数据都远一些——这就是SVM遵循的最大边距准则。
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename C:/Users/liychen/Desktop/svm1.PNG

\end_inset


\end_layout

\begin_layout Standard
而在实践中，我们把二类分类分别作为正负1，所以两条距离该分割线平行距离1的直线就应景而生。在这两条直线上的点我们称之为支持向量（SV）。
\end_layout

\begin_layout Subsection
线性可分时的SVM 
\end_layout

\begin_layout Standard
1) 线性可分：存在
\begin_inset Formula $w,b$
\end_inset

使得
\begin_inset Formula $\begin{array}{cc}
y_{i}=1, & wx+b>0\\
y_{i}=-1, & wx+b<0
\end{array}\Rightarrow wx+b=0$
\end_inset

为分割超平面。
\end_layout

\begin_layout Standard
2) 一个点到超平面
\begin_inset Formula $wx+b=0$
\end_inset

的距离：
\end_layout

\begin_layout Standard
\begin_inset Formula $d(x|w,b)=\begin{cases}
\frac{wx+b}{\left\Vert w\right\Vert } & ,y=+1\\
-\frac{wx+b}{\left\Vert w\right\Vert } & ,y=-1
\end{cases}$
\end_inset

 
\begin_inset Formula $\Rightarrow=\frac{y(wx+b)}{\left\Vert w\right\Vert }$
\end_inset


\end_layout

\begin_layout Standard
3) 分割超平面的正则表示
\end_layout

\begin_layout Standard
数据集到某个超平面的距离
\begin_inset Formula $d(D|w,b)=\min d(i|w,b)=\min_{i}\frac{y_{i}(wx_{i}+b)}{\left\Vert w\right\Vert }$
\end_inset

。将
\begin_inset Formula $y(wx+b)\geq1$
\end_inset

标准化，则
\begin_inset Formula $\frac{y_{i}(wx_{i}+b)}{\left\Vert w\right\Vert }\geq\frac{1}{\left\Vert w\right\Vert }$
\end_inset

。
\end_layout

\begin_layout Standard
4) 最大边距准则 
\begin_inset Formula $\max_{w,b}d(D|w,b)$
\end_inset


\end_layout

\begin_layout Standard
5) 线性可分时的SVM
\end_layout

\begin_layout Standard
\begin_inset Formula $\max\frac{1}{\left\Vert w\right\Vert }$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y(wx_{i}+b)\geq1$
\end_inset


\end_layout

\begin_layout Standard
等同于
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y(wx_{i}+b)\geq1$
\end_inset


\end_layout

\begin_layout Standard
这样就有了一个sign分类器。
\end_layout

\begin_layout Standard
6) support vector：分离超平面落在隔离带的边缘，满足
\begin_inset Formula $y_{i}(wx_{i}+b)=1$
\end_inset

的
\begin_inset Formula $x_{i}$
\end_inset

被称为SV。
\end_layout

\begin_layout Standard
7) 优点：
\end_layout

\begin_layout Itemize
对测试误差错识小
\end_layout

\begin_layout Itemize
稀疏性
\end_layout

\begin_layout Itemize
自然直观
\end_layout

\begin_layout Itemize
有效
\end_layout

\begin_layout Itemize
有理论深度
\end_layout

\begin_layout Subsection
一般的（线性）SVM
\end_layout

\begin_layout Standard
不满足约束的时候，可以做一些放松——引入
\begin_inset Formula $\xi_{i}\geq0$
\end_inset

作为松弛变量。
\end_layout

\begin_layout Standard
这样原来的最优化问题就变成
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
最优的分类器则为
\begin_inset Formula $f*(x)=w*x+b*$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename C:/Users/liychen/Desktop/svm_graph.PNG

\end_inset


\end_layout

\begin_layout Standard
这里大概示意了
\begin_inset Formula $\xi$
\end_inset

的应用场景。左边是上述完全可分的情况，右边是没法分开，所以我们容忍一些误差，只要误差之和在一个可以接受的范围之内。
\end_layout

\begin_layout Subsection
非线性的SVM
\end_layout

\begin_layout Standard
这里的直觉大概是，在低维空间较为稠密的点，可以在高维空间下变得稀疏。从而可能可以找到一个高维空间的线性平面，把他们分开。
\end_layout

\begin_layout Standard
原来的数据集是：
\begin_inset Formula $\mathcal{D}=\left\{ (\mathbf{x}_{i},y_{i})\mid\mathbf{x}_{i}\in\mathbb{R}^{p},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n}$
\end_inset


\end_layout

\begin_layout Standard
然后定义一个从低维到高维的映射：
\begin_inset Formula $\Phi$
\end_inset

，使得
\begin_inset Formula $x\underrightarrow{\Phi}z$
\end_inset

。其中
\begin_inset Formula $x$
\end_inset

原本属于
\begin_inset Formula $\mathbb{R}^{p}$
\end_inset

，此时被映射到一个高维的
\begin_inset Formula $\mathbb{R}^{q}$
\end_inset

，可为无限维Hilbert空间（这里我只是照抄笔记...）。
\end_layout

\begin_layout Standard
映射之后的
\begin_inset Formula $\mathcal{D}'=\left\{ (\mathbf{z}_{i},y_{i})\mid\mathbf{z}_{i}\in\mathbb{R}^{q},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n}$
\end_inset

，之后就是传统的寻找一个线性平面。
\end_layout

\begin_layout Standard
\begin_inset Formula $\Phi$
\end_inset

的例子：
\end_layout

\begin_layout Standard
\begin_inset Formula $\Phi(x)=(\Phi_{1}(x),\Phi_{2}(x),\Phi_{3}(x))=(x_{1}^{2},2x_{1}x_{2},x_{2}^{2})$
\end_inset

，这样就大三到一个高维的空间（圆）。
\end_layout

\begin_layout Standard
下节课是线性SVM的计算。
\end_layout

\begin_layout Section
SVM（二）
\end_layout

\begin_layout Standard
这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍，现在又来了-_-||
\end_layout

\begin_layout Standard
还有个老的掉牙的段子...
\end_layout

\begin_layout Standard
有人问经济学家一个数学问题，经济学家表示不会解...
\end_layout

\begin_layout Standard
然后那个人把这个数学问题转成了一个等价的最优化问题，经济学家立马就解出来了...
\end_layout

\begin_layout Standard
好吧，我还是乖乖的赘述一遍对偶问题吧，表示被各种最优化问题折磨过的孩子这点儿真是不在话下。
\end_layout

\begin_layout Subsection
对偶问题的一般情况
\end_layout

\begin_layout Standard
1) 优化问题
\end_layout

\begin_layout Standard
一个典型的最优化问题形如：
\end_layout

\begin_layout Standard
\begin_inset Formula $\text{\min}f_{0}(x)$
\end_inset


\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $s.t.\, f_{i}(x)\leq0,\ i\in\left\{ 1,\dots,m\right\} $
\end_inset

(不等式约束)
\end_layout

\begin_layout Standard
\begin_inset Formula $h_{i}(x)=0,\ i\in\left\{ 1,\dots,p\right\} $
\end_inset

（等式约束）
\end_layout

\begin_layout Standard
2) 优化问题的Lagrange （拉格朗日）函数
\end_layout

\begin_layout Standard
\begin_inset Formula $\mathcal{L}(x,\lambda,\nu)=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}\nu_{i}h_{i}(x).$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{i},\nu_{i}>0,\forall i$
\end_inset


\end_layout

\begin_layout Standard
3) 对偶函数
\end_layout

\begin_layout Standard
\begin_inset Formula $g(\lambda,\nu)=\inf_{x\in\mathcal{D}}\mathcal{L}(x,\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}\nu_{i}h_{i}(x)\right)$
\end_inset

称为该优化问题的对偶函数。此时，
\end_layout

\begin_layout Standard
\begin_inset Formula $\nabla x\mathcal{L}(x,\lambda,\nu)=0$
\end_inset

，显然这个时候一阶偏导数为0。
\end_layout

\begin_layout Standard
4) 对偶问题
\end_layout

\begin_layout Standard
我们称
\begin_inset Formula $\max g(\lambda,\nu),s.t.\lambda\geq0$
\end_inset

为原优化问题的对偶问题，可化为最优化问题的标准形式
\begin_inset Formula $\min-g(\lambda,\nu),s.t.-\lambda\leq0$
\end_inset

。
\end_layout

\begin_layout Standard
如果原优化问题为凸优化，则
\begin_inset Formula $g(\cdot)$
\end_inset

必为凹函数，从而最终的标准形式依旧是一个凸优化问题。
\end_layout

\begin_layout Standard
5) 弱对偶性
\end_layout

\begin_layout Standard
令
\begin_inset Formula $x*$
\end_inset

为原问题的解，则
\begin_inset Formula $p*=f_{0}(x*)$
\end_inset

，且
\begin_inset Formula $f_{i}(x^{*})\leq0$
\end_inset

，
\begin_inset Formula $h_{i}(x*)=0$
\end_inset

.
\end_layout

\begin_layout Standard
令
\begin_inset Formula $(\lambda*,\nu*)$
\end_inset

为对偶问题的解，则
\begin_inset Formula $d*=g(\lambda*,\nu*)$
\end_inset

; 
\begin_inset Formula $\lambda*\geq0$
\end_inset

.
\end_layout

\begin_layout Standard
定理（弱对偶性）：
\begin_inset Formula $d*\leq p*$
\end_inset

，即对偶问题的优化值必然小于等于原问题优化值。
\end_layout

\begin_layout Standard
6) 强对偶性
\end_layout

\begin_layout Standard
当
\begin_inset Formula $d*=p*$
\end_inset

时，两者具有强对偶性；满足该条件的称之为constraint qualifications，如Sliter定理（http://en.wikipedia.org/wi
ki/Slater%27s_condition）。
\end_layout

\begin_layout Standard
强对偶性满足的时候，原优化问题就可以化为一个二步优化问题了。
\end_layout

\begin_layout Standard
7) KTT条件（库恩-塔克条件）
\end_layout

\begin_layout Standard
局部最优化成立的必要条件：
\end_layout

\begin_layout Standard
\begin_inset Formula $\nabla x\mathcal{L}(x,\lambda,\nu)=\nabla f(x^{*})+\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(x^{*})+\sum_{j=1}^{l}\nu{}_{j}\nabla h_{j}(x^{*})=0$
\end_inset

（一阶条件）
\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{i}f_{i}(x^{*})=0,\;\forall i=1,\ldots,m.$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{i}\geq0,\forall i$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $f_{i}(x^{*})\le0,\;\forall i=1,\ldots m$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $h_{j}(x^{*})=0,\;\forall j=1,\ldots,p\,\!$
\end_inset


\end_layout

\begin_layout Standard
注：SVM满足强对偶性，所以可以直接解对偶问题。
\end_layout

\begin_layout Subsection
对偶问题应用于SVM
\end_layout

\begin_layout Standard
1) SVM的最优化问题
\end_layout

\begin_layout Standard
上节课可知，SVM的最优化问题为：
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i$
\end_inset


\end_layout

\begin_layout Standard
写成标准形式就是
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\,1-\xi_{i}-y_{i}(w_{i}+b)\leq0,\forall i$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $-\xi_{i}\leq0,\forall i$
\end_inset


\end_layout

\begin_layout Standard
这样这里总计有2N个约束条件。
\end_layout

\begin_layout Standard
对应的Lagrange函数为：
\begin_inset Formula $\min_{\mathbf{w},\mathbf{\xi},b}\left\{ \frac{1}{2}\|\mathbf{w}\|^{2}+C\sum_{i=1}^{n}\xi_{i}+\sum_{i=1}^{n}\lambda_{i}[1-y_{i}(\mathbf{w'}\cdot\mathbf{x_{i}}-b)-\xi_{i}]-\sum_{i=1}^{n}\mu_{i}\xi_{i}\right\} $
\end_inset


\end_layout

\begin_layout Standard
这样一阶条件就是
\end_layout

\begin_layout Standard
\begin_inset Formula $\frac{\partial L}{\partial w_{k}}=w_{k}+\sum_{i=1}^{n}\lambda_{i}(-y_{i}x_{i}^{k})=0$
\end_inset

 
\begin_inset Formula $\Rightarrow\mathbf{w}=\sum_{i=1}^{n}\lambda_{i}(y_{i}x_{i})$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\frac{\partial L}{\partial b}=\begin{subarray}{c}
\sum_{i=1}^{n}\lambda_{i}(-y_{i})=0\end{subarray}$
\end_inset


\begin_inset Formula $\Rightarrow\sum_{i=1}^{n}\lambda_{i}y_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\frac{\partial L}{\partial\xi_{k}}=C-\lambda_{k}-\mu_{k}=0$
\end_inset


\begin_inset Formula $\Rightarrow C-\lambda_{k}-\mu_{k}=0,\forall k$
\end_inset


\end_layout

\begin_layout Standard
这样最后我们有
\begin_inset Formula $\mathcal{L}^{*}=-\frac{1}{2}\sum_{i}\lambda_{i}y_{i}(\mathbf{w'}x_{i})+\sum_{i}\lambda_{i}(1-b)$
\end_inset

.
\end_layout

\begin_layout Standard
3) 对偶函数
\end_layout

\begin_layout Standard
这里的对偶函数就是
\begin_inset Formula $g(\lambda,\mu)=-\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})+\sum_{i}\lambda_{i}$
\end_inset


\end_layout

\begin_layout Standard
4) 对偶问题
\end_layout

\begin_layout Standard
\begin_inset Formula $\min-g(\lambda,\mu)=\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})-\sum_{i}\lambda_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\sum_{i}\lambda_{i}y_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $0\leq\lambda_{i}\leq C$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\mu_{i}\geq0$
\end_inset


\end_layout

\begin_layout Standard
5) KKT条件
\end_layout

\begin_layout Standard
\begin_inset Formula $w=\sum\lambda_{i}y_{i}x_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{i}(1-y_{i}(w'x_{i}+b)-\xi_{i})=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\sum\lambda_{i}y_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $0\leq\lambda_{i}\leq C$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{i}[y_{i}(w'x_{i}+b)-\xi_{i}]=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\mu_{i}\xi_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\mu_{i}\geq0$
\end_inset


\end_layout

\begin_layout Standard
6) SVM分类器
\end_layout

\begin_layout Standard
ul...
\end_layout

\begin_layout Standard
解对偶问题，得到
\begin_inset Formula $\lambda*$
\end_inset

, 
\begin_inset Formula $\mu*$
\end_inset


\end_layout

\begin_layout Standard
计算
\begin_inset Formula $w^{*}=\sum_{i}\lambda_{i}y_{i}x_{i}$
\end_inset


\end_layout

\begin_layout Standard
计算
\begin_inset Formula $b^{*}$
\end_inset

：找到一个
\begin_inset Formula $<0\lambda_{i}<C$
\end_inset

（非边界上），从而满足
\begin_inset Formula $\begin{cases}
1-y_{i}(\mathbf{w'}\cdot\mathbf{x_{i}}-b)=0\\
\xi_{i}=0
\end{cases}$
\end_inset

。由
\begin_inset Formula $y_{i}=\pm1$
\end_inset

，我们可得
\begin_inset Formula $(\mathbf{w'}\cdot\mathbf{x_{i}}-b)=y_{i}$
\end_inset


\begin_inset Formula $\Rightarrow$
\end_inset


\begin_inset Formula $b=y_{i}-\mathbf{w'}\cdot\mathbf{x_{i}}=y_{i}-\sum_{j}\lambda_{j}y_{j}(x_{j}'x_{i})$
\end_inset


\end_layout

\begin_layout Standard
平面分类器
\end_layout

\begin_layout Standard
y=
\begin_inset Formula $w^{*}x+b$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\hat{y}=sign(w*x+b)=sign(\sum_{j}\lambda_{j}y_{j}(x_{j}'x_{i}))$
\end_inset

，故只与内积有关。
\end_layout

\begin_layout Standard
这样下节课就会讲到解对偶问题的方法，以及SVM和kernel methods的联系。
\end_layout

\begin_layout Section
SMO算法
\end_layout

\begin_layout Standard
SMO算法
\end_layout

\begin_layout Subsection
1.
 SVM优化问题
\end_layout

\begin_layout Standard
1) 原问题
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i$
\end_inset


\end_layout

\begin_layout Standard
2) 拉格朗日形式的表述
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\mathcal{L}(y_{i},w^{'}x_{i}+b)+\lambda\left\Vert w\right\Vert ^{2}$
\end_inset


\end_layout

\begin_layout Standard
其中，
\begin_inset Formula $\mathcal{L}(y_{i},w^{'}x_{i}+b)=l(y(w'x+b))$
\end_inset

。
\end_layout

\begin_layout Standard
3) 对偶问题
\end_layout

\begin_layout Standard
\begin_inset Formula $\min-g(\lambda,\mu)=\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})-\sum_{i}\lambda_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\sum_{i}\lambda_{i}y_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $0\leq\lambda_{i}\leq C$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\mu_{i}\geq0$
\end_inset


\end_layout

\begin_layout Standard
4) SVM分类器
\end_layout

\begin_layout Standard
(i) 
\begin_inset Formula $W=\sum_{i}\lambda_{i}y_{i}x_{i}$
\end_inset


\end_layout

\begin_layout Standard
(ii) 选
\begin_inset Formula $0<\lambda_{i}<C$
\end_inset

，
\begin_inset Formula $b=y_{i}-w'x_{i}=y_{i}-\sum_{j}\lambda_{j}y_{j}(x_{i}'x_{j})$
\end_inset

，然后
\begin_inset Formula $\tilde{b}=average(b_{i})$
\end_inset

。
\end_layout

\begin_layout Standard
(iii)SVM分类器 
\begin_inset Formula $sign(w'x+b)=sign(\sum_{i=1}^{N}\lambda_{i}y_{i}(x'x_{i})+b)$
\end_inset


\end_layout

\begin_layout Subsection
SMO算法
\end_layout

\begin_layout Standard
1) 基本思想：迭代下降、坐标下降
\end_layout

\begin_layout Standard
一次要选择两个变量（否则会破坏
\begin_inset Formula $\sum\lambda_{i}y_{i}=0$
\end_inset

的约束），之后就可以解这个双变量优化问题。
\end_layout

\begin_layout Standard
2) 两个变量的优化
\end_layout

\begin_layout Standard
任取
\begin_inset Formula $\lambda_{1}$
\end_inset

,
\begin_inset Formula $\lambda_{2}$
\end_inset

作为变量，其他
\begin_inset Formula $\lambda_{3},...$
\end_inset

作为常量。
\end_layout

\begin_layout Standard
展开的矩阵大致如下：
\end_layout

\begin_layout Standard
\begin_inset Formula $\begin{array}{cccccc}
 &  & \lambda_{1} & \lambda_{2} & \cdots & \lambda_{N}\\
 &  & y_{1}x_{1} & y_{2}x_{2} & \cdots & y_{N}x_{N}\\
\lambda_{1} & y_{1}x_{1} &  &  & \vdots\\
\lambda_{2} & y_{2}x_{2} &  &  & \vdots\\
\vdots & \vdots & \cdots & \cdots & y_{i}y_{j}(x_{i}x_{j})\lambda_{i}\lambda_{j}\\
\lambda_{N} & y_{N}x_{N}
\end{array}$
\end_inset


\end_layout

\begin_layout Standard
目标函数=
\begin_inset Formula $a_{11}\lambda_{1}\lambda_{1}+a_{12}\lambda_{1}\lambda_{2}+a_{21}\lambda_{2}\lambda_{1}+a_{22}\lambda_{2}\lambda_{2}+b_{1}\lambda_{1}+b_{2}\lambda_{2}+c$
\end_inset


\end_layout

\begin_layout Standard
这样
\begin_inset Formula $a_{11}=\left\Vert x_{1}\right\Vert ^{2}$
\end_inset

,
\begin_inset Formula $a_{22}=\left\Vert x_{2}\right\Vert ^{2}$
\end_inset

,
\begin_inset Formula $a_{12}=\left|x_{1}\cdot x_{2}\right|$
\end_inset

,
\begin_inset Formula $a_{21}=\left|x_{2}\cdot x_{1}\right|$
\end_inset

。
\end_layout

\begin_layout Standard
约束
\begin_inset Formula $0\leq\lambda_{1},\lambda_{2}\leq C$
\end_inset

(对应对偶问题)
\end_layout

\begin_layout Standard
\begin_inset Formula $\lambda_{1}y_{1}+\lambda_{2}y_{2}+d=0$
\end_inset

，这里d代表其余不改变的那些
\begin_inset Formula $\sum_{i=3}^{N}\lambda_{i}y_{i}$
\end_inset

。
\end_layout

\begin_layout Standard
化到单变量的话，
\begin_inset Formula $\lambda_{2}=(d-\lambda_{1}y_{1})/y_{2}$
\end_inset


\end_layout

\begin_layout Standard
所以，
\end_layout

\begin_layout Itemize
目标函数= 
\begin_inset Formula $e_{0}\lambda_{1}^{2}+e_{1}\lambda_{1}+e_{2}$
\end_inset

，最优条件
\begin_inset Formula $\bar{\lambda_{1}}=-\frac{e_{1}}{2e_{0}}$
\end_inset


\end_layout

\begin_layout Itemize
约束 
\begin_inset Formula $L\leq\lambda_{1}\leq H$
\end_inset

，其中
\begin_inset Formula $L$
\end_inset

和
\begin_inset Formula $H$
\end_inset

分别为lower/upper bound。故必有最优点在L、H之间或者L、H之一。
\end_layout

\begin_layout Itemize
\begin_inset Formula $\min e_{0}\lambda_{1}^{2}+e_{1}\lambda_{1}$
\end_inset

，
\begin_inset Formula $s.t.\,\, L\leq\lambda_{1}\leq H$
\end_inset

，可以解得
\begin_inset Formula $\lambda_{1}^{*}=\begin{cases}
L & \bar{\lambda_{1}}<L\\
\bar{\lambda_{1}} & L\leq\bar{\lambda_{1}}\leq H\\
H & \bar{\lambda_{1}}>H
\end{cases}$
\end_inset


\end_layout

\begin_layout Standard
这里虽然需要迭代很多次，但是迭代的每一步都比较快。
\end_layout

\begin_layout Standard
至于如何选择
\begin_inset Formula $\lambda_{1,2}$
\end_inset

，第一个变量
\begin_inset Formula $\lambda_{1}$
\end_inset

可以选择
\begin_inset Formula $0<\lambda<C$
\end_inset

，同时
\begin_inset Formula $b_{i}-\bar{b}$
\end_inset

最大。第二个变量选择
\begin_inset Formula $H-L$
\end_inset

最大的。
\end_layout

\begin_layout Section
核函数和核方法
\end_layout

\begin_layout Standard
补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...
\end_layout

\begin_layout Subsection
核函数（正定）
\end_layout

\begin_layout Standard
定义 
\begin_inset Formula $K(x,y)$
\end_inset

, 
\begin_inset Formula $x,y\in\mathbb{R}$
\end_inset

满足：
\end_layout

\begin_layout Standard
1) 对称： 
\begin_inset Formula $K(x,y)=K(y,x)$
\end_inset


\end_layout

\begin_layout Standard
2) 正定： n个观测
\begin_inset Formula $x_{1},x_{2},...,x_{n}\in\mathbb{R}^{p}$
\end_inset

，
\begin_inset Formula $K_{n}=\left[\begin{array}{ccc}
K(x_{1},x_{1}) & \cdots & K(x_{1},x_{n})\\
\vdots & \ddots & \vdots\\
K(x_{n},x_{1}) & \cdots & K(x_{n},x_{n})
\end{array}\right]$
\end_inset

 正定（或者非负定）。
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $K(x,y)$
\end_inset

举例：
\end_layout

\begin_layout Standard

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
常数——
\begin_inset Formula $K(x,y)=C\Rightarrow\sum_{j}\sum_{j}cu_{i}u_{j}=c\left\Vert u_{i}\right\Vert $
\end_inset


\end_layout

\begin_layout Standard
内积—— 
\begin_inset Formula $K(x,y)=\sum x_{i}y_{i}$
\end_inset

，或广义下
\begin_inset Formula $K(x,y)=(\Phi(x),\Phi(y))$
\end_inset

，其中
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\Phi(x):x\rightarrow X$
\end_inset

，从
\begin_inset Formula $\mathbb{R}^{p}\rightarrow\mathbb{R}^{q}$
\end_inset

。
\end_layout

\begin_layout Standard
性质：
\end_layout

\begin_layout Standard
1.
 封闭性 
\end_layout

\begin_layout Standard
1) 
\begin_inset Formula $K(x,y)$
\end_inset

正定，
\begin_inset Formula $\alpha>0$
\end_inset

，则
\begin_inset Formula $\alpha K(x,y)$
\end_inset

正定。
\end_layout

\begin_layout Standard
2) 
\begin_inset Formula $K_{1}(x,y)$
\end_inset

正定，
\begin_inset Formula $K_{2}(x,y)$
\end_inset

正定，则
\begin_inset Formula $K_{1}(x,y)+K_{2}(x,y)$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
正定，
\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit

\begin_inset Formula $K_{1}(x,y)\cdot K_{2}(x,y)$
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
正定。
\end_layout

\begin_layout Standard
3) 
\begin_inset Formula $\{K(x,y)\}$
\end_inset

正定，
\begin_inset Formula $K_{n}(x,y)\rightarrow K(x,y)$
\end_inset

，则
\begin_inset Formula $K(x,y)$
\end_inset

正定。
\end_layout

\begin_layout Standard
4) 
\begin_inset Formula $(1+(x,y))^{k}$
\end_inset

正定
\end_layout

\begin_layout Standard
5) 
\begin_inset Formula $\exp(-\frac{\left\Vert x-y\right\Vert }{2\sigma^{2}})$
\end_inset

正定。
\end_layout

\begin_layout Standard
2.
 归一性
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{K}(x,y)=\frac{K(x,y)}{\sqrt{k(x,x)}\sqrt{k(y,y)}}$
\end_inset

正定，
\begin_inset Formula $\Rightarrow\bar{K}(x,x)=1$
\end_inset

。
\end_layout

\begin_layout Subsection
再生核Hilbert空间（RKHS)
\end_layout

\begin_layout Standard
1.
 Hilbert空间：完备内积空间，可以视作欧氏空间的推广。
\begin_inset Formula $H=\{x,y,z,...\}$
\end_inset

。
\end_layout

\begin_layout Standard
在这个空间中，我们定义：
\end_layout

\begin_layout Itemize
加法：x+y
\end_layout

\begin_layout Itemize
数乘：
\begin_inset Formula $\alpha x$
\end_inset

, 
\begin_inset Formula $\alpha\in\mathbb{R}$
\end_inset

。
\end_layout

\begin_layout Itemize
内积
\begin_inset Formula $(x,y)$
\end_inset

：对称性
\begin_inset Formula $(x,y)=(y,x)$
\end_inset

;线性 
\begin_inset Formula $(x_{1}+x_{2},y)=(x_{1},y)+(x_{2},y)$
\end_inset

，
\begin_inset Formula $\alpha(x,y)=(\alpha x,y)$
\end_inset

.
\end_layout

\begin_layout Itemize
零元素：若
\begin_inset Formula $(x,x)=0$
\end_inset

，则
\begin_inset Formula $x=\phi$
\end_inset

定义为零元素。
\end_layout

\begin_layout Itemize
完备性：如果
\begin_inset Formula $x_{n}\rightarrow x$
\end_inset

且
\begin_inset Formula $x_{n}\in H$
\end_inset

，则
\begin_inset Formula $x\in H$
\end_inset

。（收敛到该空间内）。
\end_layout

\begin_layout Standard
2.
 再生核Hilbert空间
\end_layout

\begin_layout Standard
给定
\begin_inset Formula $K(x,y)$
\end_inset

正定，可以构造Hilbert空间H使得
\begin_inset Formula $K(\cdot,y)\in H$
\end_inset

，
\begin_inset Formula $(K(\cdot,y),K(\cdot,z))=K(y,z)$
\end_inset

；且构造一个
\begin_inset Formula $\Phi(x):\mathbb{R}^{p}\rightarrow H$
\end_inset

，使得
\begin_inset Formula $K(x,y)=(\Phi(x),\Phi(y))$
\end_inset

，即核函数可以写成内积形式。
\end_layout

\begin_layout Standard
这样对于
\begin_inset Formula $\forall f\in H$
\end_inset

，
\begin_inset Formula $(f,K(\cdot,x))=f(x)$
\end_inset

。
\end_layout

\begin_layout Subsection
核方法
\end_layout

\begin_layout Standard
1.
 基本思想
\end_layout

\begin_layout Standard
将线性模型推广到非线性模型的方法（其中较为简单的一种）
\end_layout

\begin_layout Standard
\begin_inset Formula $x\underrightarrow{\Phi(x)}\tilde{X}=\Phi(x)$
\end_inset

，从
\begin_inset Formula $\mathbb{R}^{p}$
\end_inset

到
\begin_inset Formula $\mathbb{R}^{q}(H)$
\end_inset

的一个映射。举例：
\begin_inset Formula $\Phi(x)=(x,x^{2})$
\end_inset

，这样就可以拓展为广义线性模型。
\end_layout

\begin_layout Standard
2.
 SVM
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i$
\end_inset


\end_layout

\begin_layout Standard
可以转化为：
\end_layout

\begin_layout Standard
\begin_inset Formula $\min-g(\lambda,\mu)=\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})-\sum_{i}\lambda_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\sum_{i}\lambda_{i}y_{i}=0$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $0\leq\lambda_{i}\leq C$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\mu_{i}\geq0$
\end_inset


\end_layout

\begin_layout Standard
令
\begin_inset Formula $w=\sum\lambda_{i}x_{i}y_{i}$
\end_inset

，
\begin_inset Formula $b=y_{i}-w'x_{i}$
\end_inset

，则
\begin_inset Formula $f(x)=sign(\sum\lambda_{i}y_{i}(x'x_{i})+b)$
\end_inset


\end_layout

\begin_layout Standard
非线性变换之后，
\end_layout

\begin_layout Standard
\begin_inset Formula $\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i$
\end_inset


\end_layout

\begin_layout Standard
注意此时
\begin_inset Formula $w$
\end_inset

的维数有变化（
\begin_inset Formula $p\rightarrow q$
\end_inset

）。
\end_layout

\begin_layout Section
原型方法和最近邻KNN
\end_layout

\begin_layout Subsection
原型方法
\end_layout

\begin_layout Standard
1) 1-NN 最近邻居方法
\end_layout

\begin_layout Standard
最极端的情况：只找到最近的一位邻居。
\end_layout

\begin_layout Standard
数据集
\begin_inset Formula $D=\{(x_{i},y_{i}),1\leq i\leq N\}$
\end_inset

，输入
\begin_inset Formula $x_{i}$
\end_inset

，在
\begin_inset Formula $\{x_{j},j\neq i\}$
\end_inset

中找到与
\begin_inset Formula $x_{i}$
\end_inset

最近的邻居
\begin_inset Formula $x_{k}$
\end_inset

，输出
\begin_inset Formula $x_{k}$
\end_inset

对应的类标记
\begin_inset Formula $y_{k}$
\end_inset

。
\end_layout

\begin_layout Standard
2) 类中心的方法
\end_layout

\begin_layout Standard
类中心： 
\begin_inset Formula $c_{k}=\frac{1}{N_{k}}\sum_{y_{i}=k}x_{i},1\leq k\leq K$
\end_inset

，相当于对于一群有着同样类标记的点，对x取平均。
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $x_{i}$
\end_inset

，而后在所有类中心中与其最近的类中心
\begin_inset Formula $c_{l}$
\end_inset

。
\end_layout

\begin_layout Standard
输出：
\begin_inset Formula $c_{l}$
\end_inset

对应的类标记。
\end_layout

\begin_layout Standard
3) 对每个类可计算若干个“中心”（称之为原型或者样板，比如在每类中做聚类）。
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $x_{i}$
\end_inset

，而后在所有类中心中与其最近的类中心
\begin_inset Formula $c_{l}$
\end_inset

。
\end_layout

\begin_layout Standard
输出：
\begin_inset Formula $c_{l}$
\end_inset

对应的类标记。
\end_layout

\begin_layout Standard
4) K-NN方法
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $x_{i}$
\end_inset

，在
\begin_inset Formula $\{x_{j},j\neq i\}$
\end_inset

中找到与
\begin_inset Formula $x_{i}$
\end_inset

最近的K个邻居。
\end_layout

\begin_layout Standard
输出：
\begin_inset Formula $\max y_{k}$
\end_inset

(最多的那一类，从众原则的感觉）。
\end_layout

\begin_layout Standard
由于这一类方法都比较懒，所以称之为lazy learning methods.
\end_layout

\begin_layout Subsection
K-NN方法的错误率（渐近性质）
\end_layout

\begin_layout Standard
1) 结果
\end_layout

\begin_layout Standard
设
\begin_inset Formula $P*(e)$
\end_inset

为Bayes分类器的错误概率（最优分类器）；
\begin_inset Formula $\bar{P}(e)$
\end_inset

为1-NN分类器的错误概率。
\end_layout

\begin_layout Standard
则有：当样本数
\begin_inset Formula $N\rightarrow\infty$
\end_inset

时，
\begin_inset Formula $P*(e)\leq\bar{P}(e)\leq2P*(e)$
\end_inset

。接下来会证明这个优良的性质。
\end_layout

\begin_layout Standard
2) 分类问题 
\end_layout

\begin_layout Standard
给定
\begin_inset Formula $(x,y)$
\end_inset

，则
\begin_inset Formula $P(x,y)=P(y)P(x|y)$
\end_inset

。
\end_layout

\begin_layout Standard
这里我们称 
\begin_inset Formula $P(y=k)=\pi_{k}$
\end_inset

为先验分布，
\begin_inset Formula $P(x|y=k)=f_{k}(x)$
\end_inset

为类分布。从而
\end_layout

\begin_layout Standard
\begin_inset Formula $P_{k}(x)=P(y=k|x)=\frac{P(y=k,x)}{P(x)}=\frac{P(y=k)P(x|y=k)}{\sum_{k}P(x,y)}=\frac{\pi_{k}f_{k}(x)}{\sum_{k}\pi_{k}f_{k}(x)}$
\end_inset

，称之为后验概率。
\end_layout

\begin_layout Standard
3) Bayes分类器
\end_layout

\begin_layout Standard
x对应的
\begin_inset Formula $k=\arg\max_{k}P_{k}(x)$
\end_inset

，即使得后验概率最大的k。
\end_layout

\begin_layout Standard
所以，
\begin_inset Formula $P*(e|x)=P*(y\neq k^{*}|x)=1-P(y=k^{*}|x)=1-P_{k*}(x)$
\end_inset

，从
\begin_inset Formula $P*(e)=E_{x}[P*(e|x)]$
\end_inset

。
\end_layout

\begin_layout Standard
4) 1-NN分类器
\end_layout

\begin_layout Standard
1-NN输出的是离x最近的
\begin_inset Formula $\bar{x}$
\end_inset

对应的
\begin_inset Formula $\bar{y}$
\end_inset

，则
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{P}(e|x)=P(y\neq\bar{y}|x)=1-P(y=\bar{y}|x)=\sum_{k=1}^{K}P(y=k,y\neq\bar{y}|x)=\sum_{k=1}^{K}P(y=k|x)P(k\neq\bar{y}|x,y=k)$
\end_inset

。
\end_layout

\begin_layout Standard
由于
\begin_inset Formula $k\neq\bar{y}$
\end_inset

只限训练集，而
\begin_inset Formula $y=k$
\end_inset

那部分只跟测试集有关，所以由独立性我们可以拆分为：
\end_layout

\begin_layout Standard
\begin_inset Formula $=\sum_{k=1}^{K}P_{k}(x)P(k\neq\bar{y}|x)$
\end_inset

，则当
\begin_inset Formula $N\rightarrow\infty$
\end_inset

时，
\begin_inset Formula $x\rightarrow\bar{x}$
\end_inset

,
\begin_inset Formula $y\rightarrow\bar{y}$
\end_inset

，上面一项可以收敛为
\begin_inset Formula $\sum_{k=1}^{K}P_{k}(x)(1-P_{k}(x))=1-\sum_{k=1}^{K}P_{k}^{2}(x)$
\end_inset

，为后验概率（条件误差）。
\end_layout

\begin_layout Standard
5)由于
\begin_inset Formula $P*(e|x)=1-P_{k*}(x)$
\end_inset

，设
\begin_inset Formula $P_{k*}$
\end_inset

为所有
\begin_inset Formula $P_{k}$
\end_inset

中最大的，则
\end_layout

\begin_layout Standard
\begin_inset Formula $\bar{P}(e|x)=1-P_{k*}^{2}-\sum_{k\neq k*}P_{k}^{2}\leq1-P_{k*}^{2}-\frac{1}{K-1}(1-P_{k*}^{2})=2P*(e|x)-P*(e|x)^{2}-\frac{1}{K-1}P*(e|x)^{2}$
\end_inset


\end_layout

\begin_layout Standard
6)
\begin_inset Formula $\bar{P}(e)=E_{x}[\bar{P}(e|x)]=E_{x}[2P*(e|x)-P*(e|x)^{2}-\frac{1}{K-1}P*(e|x)^{2}]\leq2P*(e)-\frac{K}{K-1}P*(e)^{2}\leq2P*(e)$
\end_inset

。得证。
\end_layout

\begin_layout Standard
下一章会讲到聚类，然后就是降维了。
\end_layout

\begin_layout Section
聚类
\end_layout

\begin_layout Subsection
聚类
\end_layout

\begin_layout Standard
1.
 一般概念
\end_layout

\begin_layout Standard
1)分类与聚类（分类标识）
\end_layout

\begin_layout Standard
评测纯度。我们有测试集
\begin_inset Formula $\{x_{i}\}$
\end_inset

，这样定义纯度为
\begin_inset Formula $p_{k}=\frac{m_{k}}{N_{k}}\leq1,\forall k$
\end_inset

.
\end_layout

\begin_layout Standard
2) 输入
\end_layout

\begin_layout Standard
特征向量的表示：
\begin_inset Formula $\{x_{i},1\leq i\leq N\},x_{i}\in\mathbb{R}^{p}$
\end_inset

。
\end_layout

\begin_layout Standard
相似矩阵的表示：
\begin_inset Formula $S=\{s_{ij},1\leq i,j\leq N\}$
\end_inset

，其中相似度的计算可以是
\begin_inset Formula $s_{ij}=(x_{i}-\bar{x},x_{j}-\bar{x})$
\end_inset

的内积。显然，向量表示很容易可以计算相似度表示。
\end_layout

\begin_layout Standard
距离矩阵的表示（不相似度）：
\begin_inset Formula $D=\{d(i,j),1\leq i,j\leq N\}$
\end_inset

，其中距离可以用二阶范数定义，比如
\begin_inset Formula $d(i,j)=\left\Vert x_{i}-x_{j}\right\Vert ^{2}$
\end_inset

。
\end_layout

\begin_layout Standard
3) 输出： 
\begin_inset Formula $\{c_{k}\}$
\end_inset

，对应K个聚类。这里还分为：
\end_layout

\begin_layout Standard
非层次的
\end_layout

\begin_layout Standard
层次的（类似于树结构）
\end_layout

\begin_layout Subsection
K-means方法（非层次聚类）
\end_layout

\begin_layout Standard
（注意不要和KNN搞混了，都是K开头的...）
\end_layout

\begin_layout Standard
1) K-means方法（特征表示）
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $\{x_{i},1\leq i\leq N\}$
\end_inset

，K——聚类的个数。
\end_layout

\begin_layout Standard
算法：
\end_layout

\begin_layout Standard
初始化，随机选定类中心
\begin_inset Formula $\{c_{k}\}$
\end_inset

.
\end_layout

\begin_layout Standard
(i)根据
\begin_inset Formula $\{c_{k}\}$
\end_inset

分配
\begin_inset Formula $x_{i}$
\end_inset

到距离最近的类。
\end_layout

\begin_layout Standard
(ii)修改
\begin_inset Formula $\{c_{k}\}$
\end_inset

，使得
\begin_inset Formula $c'(k)=mean(x_{i}|x_{i}\in C_{k})$
\end_inset

。重复上面两步。
\end_layout

\begin_layout Standard
2) K-medoids方法（相似度表示）
\end_layout

\begin_layout Standard
输入：s,k
\end_layout

\begin_layout Standard
初始化。然后根据
\begin_inset Formula $\arg\min_{c_{k}}s(x_{i},c_{k})$
\end_inset

分配
\begin_inset Formula $x_{i}$
\end_inset

，再按照
\begin_inset Formula $\arg\max_{c_{k}}\sum_{x\in C_{k}}s(x_{i},c_{k})$
\end_inset

确定新的中心。
\end_layout

\begin_layout Standard
3) 模糊的K-means方法
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $\{x_{i},1\leq i\leq N\}$
\end_inset

，K
\end_layout

\begin_layout Standard
初始化。
\end_layout

\begin_layout Standard
(i) 
\begin_inset Formula $\forall x_{i}$
\end_inset

,计算
\begin_inset Formula $\left\Vert x_{i}-c_{k}\right\Vert ,\forall k$
\end_inset

，然后根据这个距离的比重来“软”分配
\begin_inset Formula $x_{i}$
\end_inset

(需要归一化分配权重）。
\end_layout

\begin_layout Standard
(ii) 
\begin_inset Formula $\forall c_{k}$
\end_inset

，利用
\begin_inset Formula $c_{k}$
\end_inset

中的
\begin_inset Formula $x_{i}$
\end_inset

进行加权平均。
\end_layout

\begin_layout Standard
重复上述两步。
\end_layout

\begin_layout Standard
4) 谱聚类（向量表示）
\end_layout

\begin_layout Standard
输入：
\begin_inset Formula $\{x_{i},1\leq i\leq N\}$
\end_inset

，K
\end_layout

\begin_layout Standard
然后对原始数据做转换，形成新的数据集
\begin_inset Formula $\{z_{i},1\leq i\leq N\}$
\end_inset

，然后再做K-means聚类。
\end_layout

\begin_layout Standard
其中转换的步骤如下：
\end_layout

\begin_layout Standard
(i) 计算相似矩阵S
\end_layout

\begin_layout Standard
(ii) 计算L=D-S，其中
\begin_inset Formula $D=\left[\begin{array}{ccc}
D_{1}\\
 & \ddots\\
 &  & D_{N}
\end{array}\right]$
\end_inset

，
\begin_inset Formula $D_{i}=\sum_{j=1}^{N}D_{ij}$
\end_inset

。
\end_layout

\begin_layout Standard
(iii)计算L最小的K个特征值对应的特征向量
\end_layout

\begin_layout Standard
(iv)让U=
\begin_inset Formula $(u_{1},\cdots,u_{k})$
\end_inset

，则
\begin_inset Formula $z_{i}$
\end_inset

是U的第i行，这样就从p维降到了K维。
\end_layout

\begin_layout Standard
(v)对Z进行K-means聚类。
\end_layout

\begin_layout Subsection
层次聚类
\end_layout

\begin_layout Standard
1) 自底向上的方法（聚合）
\end_layout

\begin_layout Standard
初始：每个
\begin_inset Formula $x_{i}$
\end_inset

都为一类
\end_layout

\begin_layout Standard
而后对于最相似的两类，合并到一类。对于类的最相似，可以定义为距离最近的类。而对于距离，则可以定义为三者之一：
\end_layout

\begin_layout Standard
(i) 
\begin_inset Formula $d_{AB}=\min d(i,j),i\in A,j\in B$
\end_inset

，称之为单连。
\end_layout

\begin_layout Standard
(ii) 
\begin_inset Formula $d_{AB}=\max d(i,j),i\in A,j\in B$
\end_inset

，称之为全连。
\end_layout

\begin_layout Standard
(iii) 
\begin_inset Formula $d_{AB}=\frac{\sum d(i,j)}{\left\Vert A\right\Vert \left\Vert B\right\Vert }$
\end_inset

.
\end_layout

\begin_layout Standard
2) 自顶向下的方法（分裂）
\end_layout

\begin_layout Standard
初始：所有的x作为一类。选用一种非层次的方法进行聚类，递归使用。
\end_layout

\begin_layout Standard
例子：二分法。
\end_layout

\begin_layout Standard
初始：
\begin_inset Formula $G=\{x_{i}\}$
\end_inset

，
\begin_inset Formula $H=\emptyset$
\end_inset

。而后选择离G最远的一个点g。
\end_layout

\begin_layout Standard
修改
\begin_inset Formula $G'=G\backslash g$
\end_inset

，
\begin_inset Formula $H=H\bigcup g$
\end_inset

。重复步骤，选择离H近的离G远的逐渐加入H。
\end_layout

\begin_layout Standard
直到分不动了，彻底分为两类。
\end_layout

\begin_layout Section
降维和PCA
\end_layout

\begin_layout Standard
降维完全属于unsupervised learning了，即给定数据集
\begin_inset Formula $\{x_{1},...,x_{n}\},x_{i}\in\mathbb{R}^{p}$
\end_inset

，我们希望降到q维的
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\{z_{1},...,z_{n}\}$
\end_inset

。从这个角度来讲，降维和聚类还是有相通之处的，都是对于特征的提取。只是一个从行的角度出发，一个对列操作的感觉。
\end_layout

\begin_layout Subsection
PCA（主成分分析，Principle Component Analysis）
\end_layout

\begin_layout Standard
个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||
\end_layout

\begin_layout Standard
1.
 求
\begin_inset Formula $u_{1}$
\end_inset

,
\begin_inset Formula $\left\Vert u_{1}\right\Vert =1$
\end_inset

使得
\begin_inset Formula $z_{i}=u_{i}x_{i}$
\end_inset

，且
\begin_inset Formula $\sum z_{i}^{2}$
\end_inset

最大。
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename C:/Users/liychen/Desktop/PCA.jpg

\end_inset


\end_layout

\begin_layout Standard
直觉上来讲，就是想寻找一个主方向。
\end_layout

\begin_layout Standard
这样，求解问题为：
\end_layout

\begin_layout Standard
\begin_inset Formula $\max\sum z_{i}^{2}=\sum(u_{1}x_{i})^{2}=\sum u_{1}'x_{i}x_{i}'u_{1}=u_{1}'\left(\sum x_{i}x_{i}'\right)u_{1}$
\end_inset

。所以我们只需要求一阶导数
\begin_inset Formula $\frac{\partial\sum z_{i}^{2}}{\partial u_{1}}$
\end_inset

即可。
\end_layout

\begin_layout Standard
设A为对称矩阵，则存在正交阵
\begin_inset Formula $u'u=I$
\end_inset

使得
\begin_inset Formula $A=u\Lambda u'$
\end_inset

，其中
\begin_inset Formula $\Lambda=\left[\begin{array}{ccc}
\lambda_{1}\\
 & \ddots\\
 &  & \lambda_{n}
\end{array}\right]$
\end_inset

为A的特征值矩阵，故
\begin_inset Formula $Au_{i}=\lambda_{i}u_{i}$
\end_inset

(列向量为特征向量）。不失一般性，我们可以排序使得
\begin_inset Formula $\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{n}$
\end_inset

（从大到小排序）。
\end_layout

\begin_layout Standard
最大特征值: 
\begin_inset Formula $\max_{\left\Vert x\right\Vert =1}x'Ax=\lambda_{1}$
\end_inset


\end_layout

\begin_layout Standard
同时
\begin_inset Formula $C=\frac{1}{n}\sum x_{i}x_{i}'$
\end_inset

为x的相关矩阵，
\begin_inset Formula $\{u_{1},u_{2},...,u_{q}\}=U_{q}$
\end_inset

，从而
\begin_inset Formula $z_{i}=U_{q}U_{q}'x_{i},\forall i$
\end_inset


\end_layout

\begin_layout Standard
2.
 找到
\begin_inset Formula $\{u_{1},u_{2},...,u_{q}\}=U_{q}$
\end_inset

(q维的子空间）
\end_layout

\begin_layout Standard
将
\begin_inset Formula $x_{i}$
\end_inset

投影到该q维空间，这样
\begin_inset Formula $z_{i}=U_{q}U_{q}'x_{i}=U_{q}\left[\begin{array}{c}
u_{1}'\\
\vdots\\
u_{q}'
\end{array}\right]x_{i}=U_{q}\left[\begin{array}{c}
u_{1}'x_{i}\\
\vdots\\
u_{q}'x_{i}
\end{array}\right]=\left[u_{1},u_{2},...,u_{q}\right]\left[\begin{array}{c}
u_{1}'x_{i}\\
\vdots\\
u_{q}'x_{i}
\end{array}\right]=(u_{1}'x_{i})u_{1}+...+(u_{q}'x_{i})u_{q}$
\end_inset

，且
\begin_inset Formula $\left\Vert u_{q}u_{q}'x-x\right\Vert _{F}^{2}$
\end_inset

最小。
\end_layout

\begin_layout Standard
A矩阵的范数：
\begin_inset Formula $\left\Vert A\right\Vert _{F}=\sum_{i}\sum_{j}a_{ij}^{2}=tr(AA')$
\end_inset

 tr表示矩阵的迹（对角线元素和）。
\end_layout

\begin_layout Standard
则上述问题等价于，求
\begin_inset Formula $(u_{1},...,u_{q})=U_{q}$
\end_inset

使得
\begin_inset Formula $tr[(u_{q}u_{q}'x-x)'(u_{q}u_{q}'x-x)]$
\end_inset

最小。
\end_layout

\begin_layout Standard
\begin_inset Formula $=tr(x'U_{q}U_{q}'U_{q}U_{q}'x-x'U_{q}U_{q}'x-x'U_{q}U_{q}'x+x'x)=tr(-x'U_{q}U_{q}'x+x'x)$
\end_inset

最小。
\end_layout

\begin_layout Standard
即使得
\begin_inset Formula $tr(x'U_{q}U_{q}'x)$
\end_inset

最大（注意没有负号）。
\end_layout

\begin_layout Standard
\begin_inset Formula $S=x'x$
\end_inset

称为数据的相似矩阵
\begin_inset Formula $=(x_{i}'x_{j})$
\end_inset

。
\end_layout

\begin_layout Standard
\begin_inset Formula $AA'$
\end_inset

和
\begin_inset Formula $A'A$
\end_inset

均为对称阵，且两个阵有相同的特征值。记
\begin_inset Formula $r$
\end_inset

为A的秩，AA'的特征向量
\begin_inset Formula $u_{1},...,u_{m}\in\mathbb{R}^{m}$
\end_inset

，A'A的特征向量
\begin_inset Formula $v_{1},...,v_{m}\in\mathbb{R}^{n}$
\end_inset

，则
\begin_inset Formula $A'u_{i}=\lambda_{i}u_{i}$
\end_inset

，
\begin_inset Formula $A'v_{i}=\lambda_{i}v_{i}$
\end_inset

。做奇异值分解，则
\begin_inset Formula $A=U\Lambda V'$
\end_inset

.
\end_layout

\begin_layout Standard
由此，
\begin_inset Formula $tr(x'U_{q}U_{q}'x)$
\end_inset

求得的和前述结果等价。
\end_layout

\begin_layout Standard
回到PCA。如果降维后需要重构，则
\begin_inset Formula $u_{i}z_{i}=\hat{x_{i}}$
\end_inset

，解
\begin_inset Formula $\min\sum_{i}\left\Vert x_{i}-\hat{x_{i}}\right\Vert $
\end_inset

即可。
\end_layout

\begin_layout Standard
3.
 对偶PCA。如果
\begin_inset Formula $p\geq n$
\end_inset

即数据非常高的时候，可以转置后再做。
\end_layout

\begin_layout Standard
4.
 KPCA （kernel）PCA也可以先用核函数
\begin_inset Formula $\Phi(\cdot)$
\end_inset

，即实现非线性的降维。需要注意，降维的过程需要保持可逆。
\end_layout

\begin_layout Standard
---------------
\end_layout

\begin_layout Standard
PS.
 PCA不适合解决overfitting的问题。如果需要解决，加regularization项。
\end_layout

\end_body
\end_document