Tag: 广义线性模型

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十二）：核函数和核方法

补上笔记。这节课讲的就是大名鼎鼎的Kernel Method...

核函数（正定）

定义 , 满足：

1) 对称：

2) 正定： n个观测， 正定（或者非负定）。

举例：

  • 常数——
  • 内积—— ，或广义下，其中，从。

性质：

1. 封闭性

1) 正定，，则正定。

2) 正定，正定，则正定，正定。

3) 正定，，则正定。

4) 正定

5) 正定。

2. 归一性

正定，。

再生核Hilbert空间（RKHS)

（走神一下：关于这个命名的吐槽猛击 -> 翻译版、 英文原版Normal Deviate）

1. Hilbert空间：完备内积空间，可以视作欧氏空间的推广。。

在这个空间中，我们定义：

  • 加法：x+y
  • 数乘：, 。
  • 内积：对称性;线性 ，.
  • 零元素：若，则定义为零元素。
  • 完备性：如果且，则。（收敛到该空间内）。

2. 再生核Hilbert空间

给定正定，可以构造Hilbert空间H使得，；且构造一个，使得，即核函数可以写成内积形式。

这样对于，。

核方法

1. 基本思想

将线性模型推广到非线性模型的方法（其中较为简单的一种）

，从到的一个映射。举例：，这样就可以拓展为广义线性模型。

2. SVM

可以转化为：

令，，则

非线性变换之后，

注意此时的维数有变化（）。

---------------------

如果各位更关心SVM后面的直觉，还是去看看Andrew Ng的相关课程吧...这里推导太多，直觉反而丢了一些。

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十五）

梯度树提升算法(GTBA, gradient tree boosting algorithm)

继续boosting类算法哎。小小预告一下，下节课会直接跳到随机森林，老师貌似是想把各种分类器都一下子讲到，然后有点前后照应的比较～真有意思，若是以前扔给我这种问题我肯定run一个logit regression就不管了，现在倒是有各种线性的、广义线性的、非线性的模型可以试着玩了，爽哎～

------------------

1. 自适应基函数模型

小小的复习一下上节课那个框架。

1. 数据。

2. 模型。 为基函数模型，其中成为基函数集合。为参数。

3. 损失函数（准则）。 为损失函数，然后就转为一个优化问题：

4. 算法。 前向分步算法。

  • 初始化：
  • 迭代：For m=1 to M，
  • 令。
  • 输出。

在此框架之下，除了上节课的Adaboost之外，还可以套用多种其他的基函数，然后1）定义损失函数 2）给出迭代那一步的优化算法，就可以实现一种boost提升算法了。

2. 应用回归问题

先采用均方误差的损失函数，定义，这样就可以得到

然后定义：

，。这里之后用回归树来求的话，就是梯度回归树算法。

梯度回归树提升算法

  • 初始化：
  • 迭代：For m=1 to M，计算。由用回归树求得.
  • 令。
  • 输出。

3. GTBA，梯度树提升算法

先吹捧一下：这个算法就是此书作者本人开发的，然后已经搞出来了软件包，可以做回归也可以做分类，貌似效果还胜过随机森林（当然是作者自己给出的那些例子...）。

损失函数为可微的。

我们的优化目标是，也就是说实际上我们不是直接对进行优化，而是仅仅在所有观测的数据点上优化，所以仅跟在这些观测点上的值有关。感觉这里就是说，我们使用有限的观测到的信息来推断一个连续的函数，然后类推并用于其他未观测到的点。

定义：

，这样这个问题就从一个直接优化的泛函问题转化为一个优化多元函数的问题...而对于一个多元函数，我们可以直接用梯度下降法。定义梯度为：

，这样。类似的，我们可以定义，其中。累加起来，就是

，这里可以是常量也可以随着改变。

定义完梯度下降之后，就是GTBA算法了。

  • 初始化。
  • 迭代：For m=1 to M，计算，然后由用回归树求得。
  • 令。
  • 输出。

一些梳理

1. 参数。这里显然有如下参数需要设定：

  • M：迭代次数。这是这个算法最主要的参数，需要用Cross-validation来算。
  • J：树的大小。建议4-8，默认为6。
  • ：收缩系数。这里可以加上这个参数，决定收缩的速度，0-1之间。
  • ：次采样率，0-1直接，默认0.5。用于做subsampling。

2. 特征变量评价

这个算法的一大优势就是可以给出各个自变量的评价。比如的时候我们可能面临特征变量选择问题。

用t表示树中的节点，表示t节点所用的变量，表示t节点产生的均方误差的减小值。之后定义：

，可用这个值来刻画变量的重要性，从而进行特征评价。

3. 通用工具

该算法对于数据无特殊要求，有一批都可以扔进去试试，故可以作为其他算法的benchmark。

此外，从贝叶斯分类器的角度，我们要找的是，这样除了原有可以观测到的之上，还可以衍生出一个向量，即，第k个位置为1如果观测到的对应第k类。一下子就可以扩展整个数据集，也可以进一步对每类都赋一个概率，不单单是0-1这样。

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十四）

开春，复课。

一句无关的话...今天打开Google Reader看到7月份要关的提示，无限悲伤。看着落园若干RSS源里面累计800+的读者，只能说句bless...2008年开始使用，到现在，伴我度过了多少读书时光呀。不过确实也衰落了，高峰的时候一个RSS源就有600+读者，现在也只剩一半了。写博客，越来越像一件出力不讨好的事情了。

--------正文开始---------

提升与梯度树

1. Boost(AdaBoost)

这里讲的AdaBoost是仅针对二类分类器的提升。大致的思想就是，给我一个弱分类器，还你一个强分类器。听起来蛮神奇的对不对?

先说算法实现。

第一步：初始化。,权重初始值 。

第二步：迭代。

for m = 1 to M

  • 根据已有算法（即弱分类器）和{}得到一个分类器.
  • 计算误差：，这里我们把权重进行归一化。
  • 计算权重：
  • 修改样本权重：

也就是说，我们不断的生成新的权重，当分类器分错的时候更改权重。

第三步：输出。最终的分类器为前面的加权。

这样就实现了从一个弱分类器改善到一个强分类器。这里弱分类器是指误差比随机猜的1/2少一点。

另注：在修改权重那一步的时候，也可以定义，然后，这样在最后的时候也可以改成。总之这里的直觉是，如果分对了，那么权重下降；反之，分错的时候这些样本的权重上升。最后take average就可以了。

2. 自适应基函数模型、前向分布算法

之所以上面又引入，便是为了更好地理解这一类模型：自适应基函数模型。

1. 我们称 为基函数模型，其中成为基函数基。注意这里和GLM有很大的不同，广义线性模型后面的为确定的。

2. 前向分步算法。

数据集记作。定义一个损失函数，比如常见的均方误差,

，或者0-1准则。

然后步骤为：

  • 初始化：
  • 迭代：For m=1 to M，
  • 令。
  • 输出。

这样我们就把这个最优化问题转变成了M步，每步只做一个参数的最优化（近似方法）。

3. 指数损失函数与AdaBoost

有了这么一个一般性的框架，我们就可以套用具体的形式。

1. 定义指数损失函数： 。

2. 两类分类、指数损失函数的自适应基函数模型。

前向分布算法：

(i)

定义

这样上式就可以化作

(ii) 固定，优化.

然后最小化，则。假定已被优化，然后继续。

(iii)优化。

取一阶条件FOC，则有

这样最后

这样就看出来上面那个AdaBoost里面的是怎么来的了吧?

(iv) 回到AdaBoost

看出来最后的AdaBoost雏形了吧？

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十三）

本学期最后一堂课的笔记...就这样，每周上班的时候都没有惦念的了，我是有多么喜欢教室和课堂呀。或者说，真的是太习惯学校的生活方式了吧...

这一节主要是在上一节的基础上，介绍一些可加模型或者树模型的相关（改进）方法。

MARS

MARS全称为Multivarible Adaptive Regression Splines，看名字就能猜出来大致他是做啥的。MARS这家伙与CART一脉相承（话说CART的竞争对手就是大名鼎鼎的C4.5）。不过，还是先说一下MARS到底是怎么玩的吧。

数据集依旧记作，然后就是splines的思想：我们定义，其中和，画出图形来就是:

mars1

这样就可以定义I函数了：，以及，越来越有spines味道了是不是？

之后就是定义f函数：，然后有意思的就来了：是中函数或者几个函数的乘积，选定了之后我们就可以用最小二乘法来求解相应的了。然后在接下来的每一步，我们都添加这样，一步步的，就开始增长。当我们用完了之后，显然有

over-fit的嫌疑，所以开始逐步的减少一些——考虑移除那些对减少残差平方和贡献比较小的项目。沿着cross-validation的思路，就可以定义函数。

PRIM

PRIM的全称为Patient Rule Induction Method，呃看名字貌似是一种比较耐心的一步步递归的方法。果不其然，最开始就是我们要先定义“削皮”：选取区间内任意的，比如0.1，然后开始削皮～削皮的策略大概就是，选定一个维度，去掉这个维度比如最大10\%或者最小10\%的样本，然后看剩余部分的y均值有没有增长。总共有p个维度，所以我们有中削皮法。选择其中上升最高的方法，削皮。然后继续来一遍，直到不能再增长的时候，停止，最终得到一块“精华”（贪心的算法）。之后，我们又要开始粘贴，即再贴上去一块儿，看看是否能涨。这样我们得到一个区，区域均值为。

从总体中扔掉这区中的样本，然后继续做下去，比如一共J次，得到J个区域（这些区域的空间可能是有交集的），这样的策略称为Bump-Hunting（肿块寻找），最终得到若干个区域，各区域中的样本均值作为（以第一次出现的空间为准）。

HME

HME的全称为Hierarchical Mixture of Experts，听起来像是一个智囊团的感觉。画出来呢，就是一个树的形状。

hme

大致的思想就是，以概率分配到各个枝条（软分类器），这样有。对于最下面一层的expert

net，可以用分类树或者其他任何的分类器。对于HME，可用EM算法来解。两类的情形，就有，有点像logit的变形有没有？

一句话的总结呢，就是这些方法看上去合理，比较容易follow the intuition，但是树类的结构弄得很难用现有的方法证明原理和一些相关性质（完全非线性呀）。

模型的总结：广义线性模型和基函数模型

从第一章到第九章，我们探索了很多个模型。说到底，模型就是，然后我们有参数模型，其中，。

最简单的来说，就是线性模型，形式为，其中。显然，线性模型便是参数模型。

然后就是广义线性模型（GLM），我们可以先扩张x，就有。说到底，就是已知的把数据从空间映射到一个新的空间。然后还可以把y再广义化，用一个可逆的已知函数变成。这样，就有，最终说来和这两个空间实现了一种线性的映射关系。

接下来我们就会看到一种形状很类似的树模型，但不是GLM：。显然这里远非线性的，而且是变量。

接着参数化，我们就有，若未知，即可变，则非GLM。这类的模型更适合的名字是：自适应基函数模型，即我们试图构造一些可以自适应的基函数，然后通过其线性组合构造最终的模型。这类模型经典如：树模型、GMM（高斯混合模型）、神经网络等。

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（八）

平滑splines

有数据集，然后定义目标函数，记为(1)

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

证明如下。

记为函数族上的分段三次多项式（splines），且在首尾两段和上是一次多项式，那么他一定有的自由度。

若，则当时，有。

(2) 我们设也是(1)式的解，则下面证明一定能找到使得目标函数比小，则,

.

(3)记，则

(4) 下面我们证明，（两者内积为0），即。

且

所以得到。

(5)有了上述结论后，我们有，然后有，所以对于所有的g，我们都有其二阶导数的范数小于f的二阶导数的范数，故在(1)式中代入g总比代入f大（或者相等）。这样我们就把一个无限维的最优化问题变为了有限维。

子波分析

1. 函数的平移与缩放

平移：

缩放：

组合起来就是。由此，对于每个，我们可以定义一个函数族，写成矩阵形式就是

2. Hoar函数

(1)定义： 。

(2)Hoar函数的平滑与缩放。定义Hoar函数族为,

。这样我们每个为一组（胖瘦一样）。

定理1（正交）：是平方可积函数的一个正交基，即对于任意的，有。

定理2（增长）：随着d的增加，张成的闭子空间逐渐增大，且。这样，d比较小的函数一定能用d比较大的函数（正交基）来表示，比如。直观的理解就是，d越大，分辨率越高。

定理3（完备）：

(3)定义，使，或者。

(4)定义，然后。

定理4：函数族,，则亦为完备基，且，如果。也就是说，和之间的空间随着d的增加，彼此正交，且所有的叠起来之后亦为完备空间。

如此，我们称为子波（mother）而为father函数。注意，这里Hoar函数非连续。

在更一般的场合，我们寻找为father函数，然后定义，满足（正交），且（增长），（完备）。

再寻找mother函数满足（同层次内正交）、(相邻层次正交补）和完备。

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

spline和子波分析

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