大数据时代的机器学习

大数据时代的机器学习何晓飞浙江大学大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引大数据时代的机器学习到2015年，全球互联网用户将达到近30亿，全世界的数据量将达到8ZB。每分钟产生数据量729,000多条新浪微博695,000条状态更新1,100万条即时消息698,445次谷歌搜索1.68亿封电子邮件人脸识别†如果在视频中我们看到感兴趣却不认识的人，就需要用人脸识别技术进行识别但是在大数据时代，我们能得到的信息远远不止这些但是在大数据时代，我们能得到的信息远远不止这些范冰冰性别：女年龄：32检测对齐识别人脸识别信息提取†现在检索到的相关网页的信息往往是杂乱无章的，我们需要对其进行信息提取非结构化数据信息提取†现在检索到的相关网页的信息往往是杂乱无章的，我们需要对其进行信息提取非结构化数据结构化数据图像检索†如果对其服装感兴趣，我们可以用图像检索查找相似的服装范冰冰图像搜索社交网络†然后，我们可以使用社交网络挖掘其社交关系内容页范冰冰推荐系统†利用挖掘到的信息，我们做多种形式的推荐，†比如服装推荐，好友推荐，电影推荐内容页范冰冰电影、服装推荐大数据时代的机器学习知识图谱图像检索推荐系统人脸识别社交网络大数据时代的机器学习特点：各种技术的融合大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引机器学习发展历程†1960s-1980s:神经网络、模式识别、决策树…†1990s:数据挖掘、强化学习、贝叶斯网络、Boosting…†2000s:SVM、核方法、概率图模型、迁移学习…………传统机器学习‡缺陷：‡特征多为人工设计，耗时耗力且需要领域知识‡数据量小，可以一次性全部处理‡注重算法的精度，对于算法效率关注不够设计算法SIFT:LBP:HOG:…神经网络:流形学习SVMLogisticRegression…输出TFIDF:提取特征数据大数据时代的机器学习‡大数据时代机器学习的特点‡数据理解是难点‡分类会逐渐弱化，检索会更加重要1.海量数据具有高度非结构化的特点，数据的快速准确理解成为信息挖掘的关键。2.深度学习和在线学习在大数据理解领域显得尤为重要。1.快速检索是有效利用海量数据的前提。2.在大数据时代，分类问题会逐渐弱化，而检索则会变得更加重要。三大核心问题存储理解检索大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引深度学习†从2006年开始重新兴起的一种学习方法，旨在建立类似人脑的神经网络，在学术界和工业界都产生了重大影响。4%11%2%201389%201285%201174%201072%RaceonImageNet(Top5HitRate)!2012年之后使用了深度学习技术深度学习‡深度学习在大数据时代的重要性：‡相比于以往的机器学习方法，深度学习能更有效利用海量数据。训练数据越大可以构建的模型越复杂，且越不容易overfitting‡但是深度学习也存在一些问题：‡算法上：训练耗时，调参复杂‡计算上：分布式优化困难‡硬件上：有些硬件还不能满足现在算法的需求，如GPU稳定性差，显存小（运行时经常会出现GPU温度过高而导致程序崩溃的情形)大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引在线学习‡在大数据时代，新数据不断涌现，使得在线学习变得更加重要‡训练数据太大，离线学习方法训练时计算复杂度过高。‡需要不断更新模型，以适合新的数据，如果使用离线学习方法更新模型，计算代价将无法忍受。在线学习‡在线学习是什么?userMakepredictionTrueresponseUpdateamodel在线学习‡当前在线学习方法的缺陷：‡线性方法：对非线性数据效果很差‡非线性方法（核方法）：需要保存历史数据，训练和测试复杂度高（随样本数线性增加），原因如下基于核方法的在线学习框架在线学习‡为解决上述非线性在线学习方法的缺陷，我们提出了具有上界的稀疏在线学习方法。基于核方法的在线学习框架在线学习我们的算法在线学习Auxilary:我们的算法NC:传统在线学习算法PCD\DCD:批量学习算法大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引哈希索引†近似最近邻检索的重要性：‡在大数据时代精确最近邻检索复杂度太高，所以常常采用近似最近邻检索，常用的方法有哈希索引和树结构检索。‡近似近邻搜索的重要性：例如，数据规模：1亿，960维图片Gist特征，用普通台式机（i7,3.4GHz）检索1次,1-NN。检索方法线性检索树结构检索(kd-tree)传统哈希检索(LSH)训练时间06小时3小时检索时间2分钟20毫秒2秒存储空间360GB+0GB360+8GB360+6GB精度100%80%80%哈希索引用分割面将数据点分割到一个个区域（哈希桶）中，用0-1向量代表原向量，提高检索效率。110111111101110111110101†什么是哈希索引：哈希索引哈希索引哈希索引†密度敏感哈希索引(DensitySensitiveHashing)‡该方法主要针对问题1：相邻的数据点被分到不同的哈希桶中‡传统LSH会出现如下情形会返回许多的伪正例(falsenegative)，伪正例越多，之后计算原空间中实际距离所需要的时间就会越多哈希索引哈希索引哈希索引†互补投影哈希算法(ComplementaryProjectionHashing)‡该方法主要针对问题2：哈希桶中的数据点数量不均衡。‡主要思想：在前一工作中，我们解决了分类面通过数据密集区域的问题。但是我们发现哈希桶中的数据点数量不均衡。‡这会导致哈希检索时多次访问到空的哈希桶，从而不得不扩大搜索范围，最终降低检索效率‡所以我们希望不出现空桶，各个哈希桶间的数据量尽量均衡(LSH)哈希索引†互补投影哈希算法(ComplementaryProjectionHashing)‡我们希望最终的哈希桶间的数据量尽量均衡，应用数学定理，将此要求转化为惩罚函数‡数据被均匀分隔的条件等价于哈希索引†互补投影哈希算法(ComplementaryProjectionHashing)‡实验结果对比：我们在100万大小的数据集上，在不同的哈希长度下，分别测试各种哈希算法和我们的上述CPH方法，将和测试点最相近的1000个点作为近邻。用平均精度MAP（MeanAveragePrecision）作为评价指标，结果如下：哈希长度1624324864LSH0.020.0350.0450.0850.135CPH0.050.0850.120.180.22哈希索引哈希索引哈希索引†压缩哈希（CompressedHashing）‡主要思想及解决方法‡充分考虑数据几何结构‡用稀疏编码和压缩传感理论对数据进行更好的表达数据点稀疏局部表示哈希索引†压缩哈希（CompressedHashing）‡方法步骤‡对数据进行稀疏表示（用m个代表点的组合系数来表示每个数据点）：把数据从维转为维‡用压缩传感理论(RestrictedIsometryProperty)对数据进行低维表述(投影)，去除原始坐标中大量的0值，加速后续计算‡对最终的向量进行二值表示（大于平均值为1，否则为0）列为原始维度（每一行为一个数据点）列为基向量个数（每一行为数据的稀疏表示）哈希索引†压缩哈希（CompressedHashing）‡实验结果对比‡我们在100万大小的数据集上，在不同的哈希长度下，分别测试各种哈希算法和我们的CH方法，并将与测试点最近的2%的点作为近邻点，用平均精度MAP（MeanAveragePrecision）作为评价指标，结果如下：哈希长度163248648096LSH0.150.240.290.330.370.41CH0.230.330.380.410.420.45大数据时代的机器学习‡大数据时代机器学习的特点‡传统机器学习‡几个核心问题‡深度学习‡在线学习‡哈希索引‡基于树的索引基于树的索引统一的近似最近邻检索查询点基于树的索引统一的近似最近邻检索‡计算查询点和每个节点的Hashing码之间的Hamming距离，对节点做近似筛选查询点[0,1,1,0]基于树的索引统一的近似最近邻检索查询点[1.2,0.8,1.3,1.5][1.4,1.2,0.9,1.1][1.2,0.9,1.4,1.4][1.1,0.8,1.2,1.5][1.2,1.4,1.1,1.7]‡在近似检索的基础上，使用欧式距离作精确检索基于树的索引查询点统一的近似最近邻检索‡选出最近的两个节点，进入下一层基于树的索引†统一的近似最近邻检索：‡实验效果‡数据集：SIFT-1M，GIST-1M‡比较对象：kd-树，分层k-means树（HKM）1NN的情形50NN的情形谢谢！