|
清华大学谷源涛教授2018年5月2日VALSE Webinar 成功举办。
谷源涛，清华大学电子工程系长聘副教授，博士生导师。1998年毕业于西安交通大学信息与通信工程系，获学士学位。2003年毕业于清华大学电子工程系并获得博士学位，清华大学优秀学位论文。毕业后留校任教至今。2005年12月至2006年2月在微软亚洲研究院做访问学者，2012年8月至2013年8月在美国麻省理工学院和斯坦福大学做访问学者，2015年9月至10月在美国密歇根大学做高级访问学者。研究领域包括信号处理基础理论与算法、多媒体通信和无线网络等，出版教材2本，发表论文100多篇。2017年起成为IEEE Signal Processing Theory and Method Technical Committee (SPTM TC) elected member，2015年起担任IEEE Transactions on Signal Processing的Associate Editor。曾获得2015年IEEE GlobalSIP最佳论文奖和2015年IEEE ChinaSIP的最佳期刊论文展示奖，并指导学生获得2017年CCDC Zhang Si-Ying杰出青年论文奖。
谷源涛教授Webinar的题目为：低维数据的压缩保距性质及其在子空间聚类中的应用。
在报告中，谷源涛教授首先介绍了在机器学习和计算机视觉等应用中，海量高维数据往往位于未知低维子空间中，因而研究低维数据的非自适应降维技术具有重要意义。谷源涛教授还介绍研究小组最新发现的随机投影矩阵对低维子空间的压缩保距性质，严格证明了R^N中由数据样点张成的任意两个子空间之间的距离，在这些样点被随机投影到R^n(n<<N)之后，以1-e^O(n)的概率近似保持不变。谷源涛教授还介绍了JL引理(Johnson-Lindenstrauss Lemma)和稀疏信号的限制等距性质(Restricted Isometry Property, RIP)，说明随机投影可以在减小数据维度的同时保持任意两个数据点或者稀疏信号的欧氏距离，进而引出了压缩感知模型和稀疏重建问题，促进了对稀疏性的深入研究。其研究发现将JL引理和限制等距性质由数据点集合推广到子空间集合，从理论上保障了可以用随机投影在降低数据背景维度的同时保持其低维子空间结构。该理论课帮助理解将子空间聚类算法应用于压缩数据上的性能表现。因为子空间距离在投影后近似保持不变，可以证明子空间聚类算法只要对原始数据有效，对压缩数据也将以大概率有效。由于很多模型都涉及低维子空间结构，本理论一定可以用于包括子空间检测和追踪在内的更多应用场景中。
问答部分：
问题1：怎么理解在高维空间中欧氏距离失效？ 回答：这个问题和我在线讲的两极和赤道的比方是类似的。假设有两个独立的高维单位向量x和y，则两者的欧氏距离平方|x-y|^2等于|x|^2+|y|^2-2x^Ty；由单位向量知|x|^2+|y|^2=2；再因为高维向量，x和y近似正交，即x^Ty约等于0；所以x和y的欧氏距离约等于sqrt(2)，独立于x和y。这说明在高维空间中不适合用欧氏距离评价两个随机向量的关系。
问题2：子空间聚类本质上而言就是一种构图方法，计算复杂度很高，其聚类结果真的比传统的基于高斯核的构图方法好吗？ 回答：在一些应用场景中，不同类别的数据会分布在若干个不同的线性子空间上，比如报告中给出的Extended Yale B等数据集。在这种情况下，用子空间聚类方法构图的效果要明显优于基于数据点间的距离的方法。这是由于子空间聚类中的构图方法本身就是针对具有子空间结构的数据设计的，而基于数据点间距离的方法没有充分利用这一结构化特征。
问题3：如果子空间间距离的定义改变，定理是否还有可能成立？ 回答：可能成立。我们可以从一个更基本的角度，即主角（在slides中有定义）的角度，来研究高斯随机投影后子空间相对位置的保持性质。我们已经证明，两个子空间之间的任意一个主角，都满足定理中所述的近似保持性质。而子空间之间的距离定义只要满足旋转不变性，就可以写成主角的函数。因而定义在子空间上的距离只要满足旋转不变性，就会满足定理中所述性质。这方面的论文请详见实验室网站： http://gu.ee.tsinghua.edu.cn。
问题4：空间分成子空间的时候是以直和的方式分解嘛？ 回答：我不太明白这个问题。如果是在问原始数据所处的L个低维子空间之间是否正交的话，那回答是否定的。即我们并未假设这些低维子空间是独立或正交的，这些子空间之间可以有交(intersection)。
问题5：怎样从N维空间中划分n维子空间？ 回答：在随机降维模型中，子空间是随机选定的。例如，在MATLAB中运行Phi = randn(n,N)函数，会生成一个nxN的矩阵Phi，它的每个元素都独立地服从单位高斯分布。Phi的各行以概率1线性独立，这样Phi转置就可看做是一个n维子空间的基矩阵。这样我们就从N维背景空间得到了一个n维的子空间，需要强调的是这个过程独立于待降维的数据。
问题6：稀疏表示里面的字典，那也就可以理解为投影矩阵了？ 回答：假设从输入信号Y学到了稀疏的系数X和字典D，一般来说D的各行线性独立，所以D从数值上确实可以看做一个投影矩阵。但我感觉这么看的意义不大。首先，投影矩阵的意义是左乘某个数据（向量或者矩阵）对其进行降维。其次，D和X都是因为Y而存在的——给定Y求D和X；D比X更多一层意义是D作为字典，除了表示训练集Y之外，还可能表示测试集Y1；但X没有太多的主动的含义，它只是表示系数，换句话说，不可能人为的构造出一个系数矩阵X1，然后用D对它做降维，这样做（在一般的字典学习模型上）没有明显的意义。所以逻辑上我不认为字典可以理解为投影矩阵。
问题7：子空间的距离度量能推广成其他方式定义的距离嘛？ 回答：能。其实与距离相比，主角可以对子空间之间的相对位置关系进行更精细的描述。（参考问题3的回答）我们已经证明，两个子空间之间的任意一个主角，都满足定理中所述的近似保持性质。因而基于主角定义的距离，都会满足定理中所述性质。
问题8：非高斯分布数据降维，报告人的方法怎么样？ 回答：依旧有效。 需要将其中关于高斯分布的概率不等式转换成其它分布的概率不等式，保留几何性质证明步骤即可。事实上，我们已经证明并验证了subGaussian分布的降维矩阵的有效性。稿件即将完成，请关注实验室网站。
问题9：证明技术是怎么利用Gaussian的呢？对常见的sketch方法比如countsketch能推广吗？ 回答：证明过程中主要是使用了关于高斯随机矩阵的一些概率不等式，并借助子空间距离和几何性质完成推导，感兴趣的读者请阅读实验室网站的论文。对常见的sketch方法理论上一般是可以推广的，只需要将其中关于高斯分布的不等式转换成其它分布的概率不等式，保留几何性质证明步骤即可。
问题10：如果数据不带噪声，报告人的方法就不适用，是吧？ 回答：我们的方法未对原始数据是否有噪声做任何假设。在分析随机压缩对数据的影响时，我们将随机压缩的作用分解成两部分，其中一部分是对数据点的分布产生一定的扰动，我们将这个扰动视作噪声进行处理。因此原始数据中有或没有噪声并不会对我们的方法产生影响。此外，如果原始数据中有一定的噪声的话，如果噪声强度不太大，则经过高斯投影之后其强度仍然有很大概率是受限的，并不会对我们的分析产生本质的影响。
问题11：如果是仿射子空间，报告人的理论分析可以推广吗？ 回答：可以。具体分析和仿射子空间之间的距离描述相关，仿射子空间可以由一个子空间加一个平移向量(translation vector)生成，因此理论证明时只需将降维对平移向量的影响量化出来，并和我们的关于子空间的降维理论结合起来就可以得到关于仿射子空间的结论。
问题12：我想问问随机投影是否每次结果不一样，若是这样如何提高聚类效果？ 回答：随机投影确实每次结果都不一样。为了在这种随机化方法的基础上提高聚类效果，可以采用随机森林的思想，即让多次运行的不同结果进行投票，以最终投票结果作为分类依据。
录像视频在线观看地址： http://www.iqiyi.com/u/2289191062
特别鸣谢本次Webinar主要组织者： VOOC责任委员：庄连生（中国科学技术大学） VODB协调理事：张利军（南京大学）
活动参与方式： 1、VALSE Webinar活动依托在线直播平台进行，活动时讲者会上传PPT或共享屏幕，听众可以看到Slides，听到讲者的语音，并通过聊天功能与讲者交互； 2、为参加活动，请关注VALSE微信公众号：valse_wechat 或加入VALSE QQ群（目前A、B、C、D、E、F、G群已满，除讲者等嘉宾外，只能申请加入VALSE H群，群号：701662399），直播链接会在报告当天（每周三）在VALSE微信公众号和VALSE QQ群发布； *注：申请加入VALSE QQ群时需验证姓名、单位和身份，缺一不可。入群后，请实名，姓名身份单位。身份：学校及科研单位人员T；企业研发I；博士D；硕士M。 3、在活动开始前10分钟左右，讲者会开启直播，听众点击直播链接即可参加活动，支持安装Windows系统的电脑、MAC电脑、手机等设备； 4、活动过程中，请勿送花、打赏等，也不要说无关话语，以免影响活动正常进行； 5、活动过程中，如出现听不到或看不到视频等问题，建议退出再重新进入，一般都能解决问题； 6、建议务必在速度较快的网络上参加活动，优先采用有线网络连接； 7、VALSE微信公众号会在每周一推送上一周Webinar报告的总结及视频（经讲者允许后），每周四发布下一周Webinar报告的通知。
| 
发表于 2018-5-10 18:58:42