Tag: 降维

Categories
读书有感

统计学习精要(The Elements of Statistical Learning)课堂笔记（二十五）：降维和PCA

 降维

降维完全属于unsupervised learning了，即给定数据集，我们希望降到q维的。从这个角度来讲，降维和聚类还是有相通之处的，都是对于特征的提取。只是一个从行的角度出发，一个对列操作的感觉。

PCA（主成分分析，Principle Component Analysis）

个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||

1. 求,使得，且最大。

PCA

直觉上来讲，就是想寻找一个主方向。

这样，求解问题为：

。所以我们只需要求一阶导数即可。

设A为对称矩阵，则存在正交阵使得，其中为A的特征值矩阵，故(列向量为特征向量）。不失一般性，我们可以排序使得（从大到小排序）。

最大特征值:

同时为x的相关矩阵，，从而

2. 找到(q维的子空间）

将投影到该q维空间，这样，且最小。

A矩阵的范数：
tr表示矩阵的迹（对角线元素和）。

则上述问题等价于，求使得最小。

最小。

即使得最大（注意没有负号）。

称为数据的相似矩阵。

和均为对称阵，且两个阵有相同的特征值。记为A的秩，AA'的特征向量，A'A的特征向量，则，。做奇异值分解，则.

由此，求得的和前述结果等价。

回到PCA。如果降维后需要重构，则，解即可。

3. 对偶PCA。如果即数据非常高的时候，可以转置后再做。

4. KPCA （kernel）PCA也可以先用核函数，即实现非线性的降维。需要注意，降维的过程需要保持可逆。

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

PS. PCA不适合解决overfitting的问题。如果需要解决，加regularization项。

Categories
读书有感

降维模型若干感悟

前几天集中爆发了一些email，直到最后和Frank兄提起，他说我应该去看一下 Adaptive Lasso，我才终于痛下决心开始看这方面的东西。先说说为啥开始看Lasso。

需求。大数据时代，任务有很多：

  • 理论层面，要有适应大数据的模型。一方面是数据量的增加（表现为个体记录的增长），一方面是数据维度的增加（简单的说就是回归方程右边的变量），让大数据这个任务变得格外艰巨（p.s. 这个不是我总结的，照抄上次ShanghaiR沙龙时候Ming的原话...话说我别的没记住，就这句话深深的印在脑海了，哎~）。
    • 数据量的增加，对应的是大样本理论。这个好玩的有很多，暂且不表。
    • 数据维数的增加，则需要相应的降维模型。你总不能在回归方程右边放入几千个变量，“维数灾难”啊...所以变量选择是个很好玩的话题。
  • 应用层面，一个模型性质再漂亮，你也要能算得出来才行是不是？
    • 首先就是要有个好的算法，比如在「统计学习那些事」中提及的LAR对于Lasso的巨大贡献。
    • 其次，什么分布式计算啊，并行计算啊，都成为热呼呼的实践问题（当然我还是go against那些不管三七二十一、直接软件中调用模型的。任何一个模型的假设和局限性都是应该首先考虑的，要不真不知道预测到哪里去了呢~）。

好吧，好久没用这么多层级了。只是昨天稍稍理了理思路，顺便写在这里，算作「感悟一」。

然后，说到底统计学还是为其他学科服务的（好吧，我是想说数据不是无源之水，总归有自己的背景，总归有在这个背景领域的人希望借助数据来解决的问题）。那么作为一种empirical method，统计模型关心的是什么呢？在被计量经济学熏陶外加祸害了若干年后，发现它本质还是为了经济学研究的一些目的服务的，所以关注的更多是consistency，大家张口闭口就是“变量外生性”...而这多少有些直觉+经验判断的东西。显然，统计模型不仅仅是计量经济学，昨天看「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」，大致的关于统计模型关心的判断标准的「感悟二」总结在这里：

  • consistency：这个还是逃不掉的，一致性在大样本下虽然比小样本的无偏要求来的弱得多(plim毕竟比期望算子好“操作”一些)。其实有一段时间我一直很抵触把计量经济学里面的causality叫做因果关系，学习计量模型的过程基本就是保证估计一致性的推导过程...想说的只是，真正的因果关系不是统计学就可以定义的，还是要回到学科本身。consistency更多包含着“internal validity”的味道，即一个结果可以期望在样本本身内重复实现。个人感觉，从经济学理论与实证研究的角度，这大概是计量经济学能达到的最多的程度了吧。再苛刻的因果真的就是经济理论本身的问题了。
  • accuracy: 统计还有一大任务，做预测。我们都知道OLS有的时候可以很简单的给出一个consistent的估计量，但是仅仅是均值意义上的估计还是不够的，对你还得给出个方差。这个方差就刻画了你的估计值是不是飘来飘去。我们当然希望一个方差比较小的估计量，所以大多数时候OLS是不能满足这样的要求的（顺便复习一下BLUE的那些条件）。
  • implementable: 有的时候我们可以用现有的数据、花费大量的时间，来拟合一个漂亮的模型。但是，模型不是放在那里就可以的，在实际应用中大家更关心的是，模型建立之后对于日后决策的指导作用。可能1000个自变量拟合出来的模型比20个好10%到20%，但是在实际应用中，20个变量显然更实用...同理，有些非线性模型漂亮的一塌糊涂，但是计算复杂度可能远远不是多项式级别的。这个时候，退而求其次也不失为一记良策。说到底，有的时候并不要求最完美的模型，总要在性能和效率之间取得一个平衡。
  • 当然说到prediction，这里更多的就有statistical learning的味道了。回归多少还算是supervised learning，至少脑海里大致有个印象什么是回归方程那一边的y。更多的时候，连y是什么都没有概念，所以就有了基于similarity的模型，比如clustering，比如协同过滤...不过有句话确实说的好(摘抄自「统计学习那些事」)：

立新老师曾经有这么一句话：“If a method works well in practice, there must be some theoretical reasons for its success.” 如果一个模型在实践中表现的很好，那么一定有它好的原因。

所以基于上述三点（当然还有可能有更多的考虑），不同的模型对于不同的标准有着不同的达标水平。大家各有所长，用哪个还真得看实际任务的需求了。

「感悟三」，则是statistical learning (统计学习，有点机器学习的味道)的任务，这个是从「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」上照抄的：

  • 预测准确性要高：和上面的accuracy对应。
  • 发现有价值的预测变量：更有可能从归纳法回溯到演绎法，给出更多的insights。

最后的，稍稍偏数学一点。「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」里面第三章讲了很多Shrinkage Methods，关心的是varible selection(生物统计中feature selection)的问题。从大家最耳熟能详的stepwise（逐步回归），到ridge regression(岭回归)，再到Lasso(或者把LAR也算进来)。基本说来，ridge和Lasso是在OLS基础上一个很有意思的变化。

  • OLS求解的最优化问题是：
  • ridge regression则是加了一个L2惩罚项，即 ，其中t是一个给定常数参数。
  • Lasso则是把这个L2变成了L1，即

就这么一个简简单单的变化，就有了后面那么多神奇的性质。「感悟四」就是，原来Lasso思想并不是那么复杂啊。

Categories
事儿关经济 经济、IT观察与思考

社会实验的特殊性（三）

在上一篇[cref %e7%a4%be%e4%bc%9a%e5%ae%9e%e9%aa%8c%e7%9a%84%e7%89%b9%e6%ae%8a%e6%80%a7%ef%bc%88%e4%ba%8c%ef%bc%89]里面回顾了费歇尔的实验设计三原则之后，那么归根结底，我们为什么要做实验？

从一个纯经济学的角度来看，社会实验的目的之一就是在我们面对现有的数据受到各种局限、从而无法完美的回答我们关心的问题的时候（说到底还是各种内生性问题），采取的一种主动出击寻求答案的方式。故而，实验之前我们一般是有一个基本的思路和方向的，然后更多的想去看一下这个东西到底是不是在现实中就是这个样子。从这个角度而言，社会实验是在很明确的我们知道想得到什么信息的方向上去设计的。

说一下从我个人的感觉上的最大的在业界和在学术界的不同，可能就是data上。在学术界，难得会有非常好的data，所以很多的时候我们都是在有限的数据资源的基础上、去力求用最完美的方法估计我们感兴趣的值。数据源有限的原因有些是历史上的，比如我们研究几十年前的事情，自然当时没有电脑等东西可以完善的记录所有的事情；有些是数据本身的性质决定的，比如宏观里面常用的gdp等东西，中国的数据是1978年之后才有的，而且一般都是年度数据，更受限于国民统计汇总的层级汇报，自然会有一些测量偏差；有些是业界有数据，但是没法得到，这里就牵扯到一些隐私等法律权益、或者数据接口API等开放的幅度的问题；还有些是知道数据在哪里、也可以得到，但是成本太高，比如个人层面的数据，除了全民普查外很难有全覆盖的数据，一般只是小规模样本；最后的就是信息并不是直接以数字的方式记录的，比如twitter上面的用户微博记录，因此需要借助文本挖掘等手段进一步深究。

业界主要提供的就是第三类，大量的个人用户的数据，比如淘宝上各种买卖双方交易的数据。现在淘宝的交易量真的是非常大，而且每笔交易都是真实的现金往来的（我们不考虑非法的洗钱状况），其实背后对应的就是一个真实的微观交易的集合。但是这个交易数据怎么用？最简单的，我们可以看价格，对于同质品之间竞争已然白热化的，已然相差无几，那么价格几乎就等同于scanner price，可以用来衡量物价的波动。当然，网络交易有不同于实体交易的地方，比如受限于运输成本和采购的规模效应，肯定会和超市里的价格有所区别。另一方面，网络上的价格信息流动非常充分，越来越接近于理想中的完全竞争市场对于信息的要求，所以多少也让人兴奋。

另外一个有趣的数据可能就是微博，因为其实质上是一种“短平快”的信息传播渠道，会把信息通过简单的几个信息源极快的扩散到整个网络中去（所谓的influencer model）。所以现在很多人炒得很热的微博营销也是背后有着深刻的渊源的。但是同样的，信息传输成本降低的背后就是噪音的增加，因此对于微博的信息分析起来除了文本挖掘技术实现之外，就是怎么去在大量的噪音数据中寻找到有用的信息。从这个角度而言，就是在进行任何文本挖掘或者信息提取之前，是不是有一个主导的思路去明确的知道需要挖掘的信息。业界很多时候不是数据太少了，而是太多了，以至于大家根本不知道这些数据可以怎么用，所以data mining成为了救命稻草，一窝蜂的上去看看能不能挖到金矿。从我的角度看，每一个data mining算法背后必然是有一种主导的思想来支撑的，比如决策树，不过是分类统计最优化路径的感觉，这样的直觉还是蛮强的。所有数据分析的任务无外乎两个字：降维，怎么在一个多维的好烦的数据海中找到自己最感兴趣的数据，可能是几个变量之间的关系，可能是一个综合指标的创建。最简单的，GDP就是对于国民生产消费活动的降维衡量指标，所以他既然降维了自然有损失，能够多么真切的反应经济活动的现实就必然要打个折扣。

经济学里面常用的“降维”的方法就是回归，无论回归在统计学或者其他学科里面被批判的多么体无完肤，但是回归最大的好处在我看来就是最容易融入经济学直觉。在[cref %e5%b0%8f%e7%aa%a5%e2%80%9c%e9%ab%98%e7%bb%b4%e6%95%b0%e6%8d%ae%e9%99%8d%e7%bb%b4%e2%80%9d-2]里面我曾经提到一些最新的高维数据降维的算法，然而算法本身必然是有直觉甚至是（经济）理论来支撑的。当数据挖掘方法被应用在一个经济活动或者经济问题的时候，如果完全脱离了经济直觉和经济思维衍生的分析方法，我觉得未免有点太过于高傲了。有的时候，如果分析思路足够敏锐，那么基于这样思路的各种算法的出来的结果可能是殊途同归。正所谓“万变不离其宗”，这也是我觉得很多data mining的方法应该和经济学、商科的思维更好的融合在一起的缘故。就像挖矿，我们除了要有先进的挖掘机以外，事前的各种勘探和经验思路还是有非常大的价值的，至少可以降低找到金矿位置的成本、尤其是时间成本。这也是我觉得经济学在业界的应用天地断然不仅仅限于和金融相关的那些而已的缘故。

另外，如果“降维”说的广义一点，就是科学的目标。可能不同的人对科学有不同的定义，我除了喜欢一种“概率”角度的定义之外，刚看到一种定义也是蛮受启发的，

The object of science is the discovery of relations.., of which the complex may be deduced from the simple. John Pringle Nichol, 1840

然而，说到底，经济直觉总要来源于实践经验，只要经济学还是定位于“研究人类行为活动的科学”。实践中信息不足的时候，信息是制约的瓶颈，因此我们要借助更多的数学建模工具来力求完美精细的刻画现有的数据构成的轮廓。反之，如果数据是可选择的，那么更多的精力就应该放在如何去“选择”数据上。我认为，实验最大的好处就是数据完全是由实验设计阶段决定的，实验设计的好数据自然会更好的告诉我们所关心的答案。

忘了是哪位大牛在Handbook of Econometrics里面写的了，大意是“与其寻求更好的估计方法，不如寻找更高质量的数据”，言下之意就是在数据可以被“设计”而获得的情况下，我们可以把精力更多的放在实验设计而不是估计模型的选择上。我并不是一个纯粹的reduced form鼓吹者，相反，我是更欣赏structural model后面的经济学思维的。因此，在实验的方法被付诸实践之前，我更希望更多的按照一种经济学model的模式去考量这些问题，去更精巧的让实验告诉我们想知道的答案。除了社会实验的特殊性考量之外，必然的，我们没有任何理由抛弃现有的经济理论、尤其是微观经济理论去完全随意的“检查”几个变量之间的实验上的因果关系。且不论efficiency，社会实验的对象为参与经济活动的人、这一特质决定了我们在设计实验的时候便要充分利用现有对于人类行为的认识成果，更好的一步步设计实验的流程——可能不只是一次实验的流程，更多的是一环扣一环的一个个实验如何按部就班进行下去。一个动态的实验设计会更好的考量实验设计者对于经济学的理解，也是社会实验较之于费歇尔三原则下的自然科学实验、要求更高的方面之一。

Categories
事儿关经济

小窥“高维数据降维”

算了，还是“一心只读圣贤书”吧。我觉得保险公司应该开发一个新险种：高铁动车险。你看我们坐汽车坐飞机都可以有保险买的，怎么坐火车的时候从来都没有这个选项？飞机的旅行保险貌似是细致到各种可能出现的事端，比如“晚点”、“取消”，那么高铁保险也可以以“停电”“雷击”“脱轨”等等名义来帮助消费者分担风险。最近看新闻看多了，弄得我这个在欧洲这么一个航班延误算是家常便饭的地方都不买保险的人，回来之后能买就买。说了这么多，我只是在小小思量明天应该怎么回家啊，这个高铁还敢不敢坐啊？查了查明天的高铁剩余车票，基本上京沪高铁都没怎么卖出去嘛！看来大家已经开始“用脚投票”了。

刚才在例行的看订阅的东西，就瞟见木遥终于更新了一篇学术日志：J-L 定理，以及为什么一个立方体相当于一个球壳。开始的时候没注意是他的，还在想谁能用中文写关于纯数学的blog；定睛一看之后，果然是木遥。这篇日志中提到的J-L定理，大致是：

Johnson–Lindenstrauss 定理是我在今晚的一个学术报告里听说的一个非常令人惊讶的定理。简单说来，它的结论是这样的：一个一百万维空间里的随便一万个点，一定可以几乎被装进一个几十维的子空间里！

本能的出于对中文写作的文献的不信任（无关作者国籍，只是说写作语言，中文论文噪音实在是太大了，甄别起来太费事儿），我顺手搜了搜，找到了一篇1999年的证明，上曰：

The Johnson-Lindenstrauss lemma shows that a set of n points in high dimensional Euclidean space can be mapped down into an O(log n=ffl 2 ) dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 Sigma ffl).

到这里，基本和上面先引用的木遥深入浅出的解释一致了。Google scholar继续给力，一下子又看到了两篇应用这个定理的paper：

  1. Ella Bingham and Heikki Mannila. 2001. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '01). ACM, New York, NY, USA, 245-250.
  2. Nir Ailon and Bernard Chazelle. 2006. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC '06). ACM, New York, NY, USA, 557-563.

（还请大家暂时容忍我的引用不规范……不想开Zotero了）

第一篇文章便是应用了Random projections来进行降维处理，是一篇实证文章，比较了Random projections和其他经典方法的优劣，采用的是图像和文字数据；第二篇则是基于上面的J-L定理，发展出来的Fast-Johnson-Linden-strauss-Transform（FJLT）变换算法：The FJLT is faster than standard random projections and just as easy to implement. 看到这里，大致可以理解J-L定理的基本原理和相应的发展趋势了。当然，还有一些研究者在继续探究J-L定理的性质，比如这篇William B. Johnson , Assaf Naor, The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.885-891, January 04-06, 2009, New York, New York。我就没有细细看此文了，以一个标题党的眼光这篇文章大致指出了J-L定理（或者引理？）还不足以完美的勾勒Hilbert空间的性质吧。

关注高维数据降维，一者是最近貌似高频大规模数据处理很热，姑且认为这种需求大概是近十几年计算机大规模应用在各个行业的必然结果吧；另者巧的是最近google不是出了个新的图片搜索么，可以直接拖图到搜索框中。正好看到了一篇blog论及与此，好奇之下也就在关注google的算法：

When you upload an image to Search by Image, the algorithms analyze the content of the image and break it down into smaller pieces called “features”. These features try to capture specific, distinct characteristics of the image - like textures, colors, and shapes. Features and their geometric configuration represent the computer’s understanding of what the image looks like.

  • 对于每张图片，抽取其特征。这和文本搜索对于网页进行分词类似。
  • 对于两张图片，其相关性定义为其特征的相似度。这和文本搜索里的文本相关性也是差不多的。
  • 图片一样有image rank。文本搜索中的page rank依靠文本之间的超链接。图片之间并不存在这样的超链接，image rank主要依靠图片之间的相似性（两张图片相似，便认为它们之间存在超链接）。具有更多相似图片的图片，其image rank更高一些。

简而言之，Google不过是把图片的特征提取，从我的理解来看也是一种把高维数据进行降维处理的思路。

说来有趣，我本身不是一个学计算机出身的，虽然机缘巧合的在大学期间学了很多涉及编程的东西，但更多只是限于语法，还谈不上算法。总所周知，国内的算法和数据结构教材有够陈旧和不实用，所以当年算法就没学好……不过对于“时空复杂度”的基本概念还是有的。后来发现经济学里面居然也盛行编程，当然大多数是一种数值模拟的思路（计量除外）。只是这里大多情况下也用不到什么算法了，一个定理出来之后算法的思路基本就很明晰了，更多的只是在于如何更好地定义初始的数据结构，以及一些基本的小tricky的选择（比如是插值算法是牛顿插值还是其他）。另有一种感觉就是以现在计算机的高计算能力和大多数情况下经济学里面对于模拟的要求，根本不需要找个高效率的算法——大多情况下循环也循环不了多少次，计算机跑1秒和2秒的差别又何在？弄得我有时候就是偷懒，明知程序写出来很没效率，还是不愿把时间花费在思考一个更有效的算法上——只要找一台更好的计算机便是了嘛！于是在我的笔记本已然承载不了的情况下，开始折腾学校里面的计算机，哈哈。当然，已知的更好的收敛算法还是会考虑的，比如经典的"policy function iteration"和"value function iteration"……顿时想起当年严格证明前者的迭代结果和后者一样的痛苦经历……于是于我，心里便暗暗的有种感觉，算法不是学CS人的事儿，是学math的人的事儿……各种美妙的数学定理才是更好的算法的源泉啊。

另，木遥提到的另外的关于高维空间中大数定理的问题，也很有趣，值得稍稍琢磨一下。无奈我数学基础还不够，尚不能完全理解他说的那些东西，看来还是需要时日打磨啊。