如果让我选择一个对我来说最重要的技能，我一定会毫不犹豫选择"专注"。我认为这是一个人能否工作有效率的根本原因，而我认为对于大部分人每天的工作学习的时间都是差不多的，区别就是谁工作更有效率，谁更专注。

我不是一个专注的人，就像我妈妈说我从小就坐不住一样，我认为这和天生的基因有关系，但是这绝不是我不去努力改变的借口。同时我认为人性也如此，因为我发现我不是个案，只不过严重程度不同。我估计这来自于哺乳动物的本性，大自然中的鹿在吃草的时候，他永远不敢专注的吃，因为他要随时注意狮子的行动。

当我不需要分心关心狮子的行为时，手机、邮件、微博、人人等各种社交方式的出现导致我仍然需要随时关注这些东西，我以前认为这是一种休息，但是慢慢发现，这成为了一种习惯。

最近我一直在努力的锻炼自己的专注力，使用了一些方法比如番茄工作法、锁定qq等，但是不适合我自己。我发现我很难将自己的注意力集中到一件事情上超过一个小时，无法在半个小时内脑子不想别的东西，也很难将一篇很长的文章从头到尾仔细看一遍。有时候晚上睡觉前我想了想今天干了什么的时候，我发现工作量和工作时间非常不成比例，一天在电脑前呆10个小时甚至12个小时，有时工作量甚至不足6个小时，我对此一直担心甚至恐惧。

我认为社交网络是一个很重要的社交方式，通过它我可以知道我的朋友最近做了什么，这让我感觉我和大家在一起，所以我从来没有试图离开人人等，但是，我觉得，我必须对自己做出一些限制。

今天看到和菜头的碎片化生存，我突然觉得，是离开社交网络的时候了。信息出现的太快，我要下车。

所以我决定：

1. 每天只在打算离开实验室前打开社交网络，除非我要发布一些东西，包括人人、QQ空间和微博等。（最近的工作和社交网络有关系，所以工作除外）
2. 在QQ上，除非必须马上要回复的事情，都放在中间休息的时间统一回复。有急事的话对方自然会打我电话，我也没必要对此感到担心。

微软亚洲研究院基于GPS数据展开的研究工作，取得了另学术界瞩目的成就。从2008年开始每年都在顶级的计算机类会议上有文章发出，掀起了研究GPS数据智能化处理的热潮。

他们的工作由谢幸研究员和郑宇研究员主导。实验数据采集主要有两个工程：

1、Geolife工程使用的，170多个志愿者4年左右的GPS轨迹；

2、北京市2万多出租车约3个月的行驶轨迹。

参见：http://research.microsoft.com/en-us/projects/geolife/

个人将近年来该小组发表的论文做了下整理，归纳其研究脉络如下（个人愚见，仅供拍砖，前面序号按照文章发表时间倒序排列，时间排列文献全表见最后的“参考文献”部分）：

阶段一： GPS+webGIS：（GPS数据在GIS地图上的灵活展示和使用）

41、（生成用户日志，帮助用户回忆），Searching Your Life on Web Maps，SIGIR2008

42、（GeoLife1.0，在地图上管理自己的GPS日志）GeoLife:Managing and Understanding Your Past Life over Maps，MDM08

阶段二：GPS数据的简单挖掘（出行方式，用户轨迹的相似性，关联规则，异常行为，群组发现）

40、（理解用户行为），Understanding User Behavior Geospatially，计算机通信2008

36、（出行模式：步行，公交，驾驶）Learning Transportation Mode from Raw GPS Data for GeographicApplication on the Web，www2008

37、（理解移动特性），Understanding mobility based on GPS data，ubicom2008

38、（基于轨迹挖掘用户相似性）Mining user similarity based on location history，GIS2008

33、（挖掘有趣位置及旅行顺序）Mining Interesting Locations and Travel Sequences From GPSTrajectories，WWW 2009

34、（挖掘个人生活模式）Mining Individual Life Pattern Based on Location History，MDM 2009

35、（GeoLife生活模式），GeoLife2.0: A Location-Based Social Networking Service，MDM2009

30、（挖掘位置间的关联），Mining Correlation Between Locations Using Human Location History，GIS 2009

29、（基于GPS轨迹发现用户交通模式：行走、驾车、公交、地铁），Understanding transportation modes based on GPS data for Webapplications，ACMTransaction on the Web，2010

23、（学习位置间的关联）Learning Location Correlation from GPS trajectories，MDM2010

9、（交通异常，前一个版本）Discovering Spatio-Temporal Causal Interactions in Traffic DataStreams，sigkdd2011

1、群组发现（提出了一个群组发现加速的数据结构）：A Framework of Traveling Companion Discovery on Trajectory DataStreams，ICDE2012

阶段三：结合外部信息，提供基于云的LBS服务

27、（计算机学会刊文）Enabling smart location-based services by mining GPS traces，Communication of China ComputerFederation2010

28、（基于云的位置服务）Location-Based Services on the Cloud，Journal on Digital Mobile Era 2010

10、（基于云的，融合多种信息，探寻用户习惯的发现）Driving with Knowledge from the Physical World，SIGKDD 2011

阶段四：同协同过滤等算法结合实现位置、活动的推荐

24、（位置和活动推荐）Collaborative Location and Activity Recommendations With GPS HistoryData，WWW 2010

22、（基于用户的推荐，旅游景点和行程）Collaborative Filtering Meets Mobile Recommendation: A User-centeredApproach， AAAI2010

20、（前期版本，智能的行程推荐）Smart Itinerary Recommendation based on User-Generated GPSTrajectories，UIC2010

21、（GeoLife，智能生活，双层网络），GeoLife: A Collaborative Social Networking Service among User,location and trajectory，IEEE Data(base) Engineering Bulletin

14、（旅游推荐，较全面的工作），Learning travel recommendations from user-generated GPS traces， ACM Transaction onIntelligent Systems and Technology，2011

15、（根据单个轨迹推荐位置和朋友），Recommending friends and locations based on individual locationhistory，2011

12、（个人行程推荐，最初版本），Social Itinerary Recommendation from User-generated Digital Trails，Personal and Ubiquitous Computing

2、热点旅游位置推荐、周边活动发现（第二次发表：协同过滤）：Towards Mobile Intelligence: Learning from GPS History Data forCollaborative Recommendation， Artificial Intelligence Journal，2012-04-29

阶段五：引入语义轨迹，泛华推荐和相似性算法

19、（利用语义轨迹，发现相似用户），Finding Similar Users Using Category-Based Location History，GIS2010

3、（语义轨迹历史）基于GPS推到用户的社会关系：InferringSocial Ties between Users with Human Location History，Journal of Ambient Intelligence andHumanized Computing

阶段六：根据出租车数据，实现智能化驾驶

16、（根据出租车历史，指导行驶方向）T-Drive: Driving Directions Based on Taxi Trajectories，GIS，2010

17、（出租司机，灵活驾驶）Drive smartly as a taxi driver，UIC2010

13、（推到出租车行驶状况），Inferring Taxi Status Using GPS Trajectories，2011

6、出租车数据探测城市的异常交通：On Mining Anomalous Patterns in Road Traffic Streams:2011International Conference on Advanced Data Mining and Applications

7、（基于出租数据的城市规划，计算）Urban Computing with Taxicabs，

8、（寻找下一个旅客）Where to Find My Next Passenger?Ubicom2011

4、基于时间关系图发现出租车行驶路线：T-Drive: Enhancing Driving Directions with Taxi Drivers'Intelligence，IEEETransactions on Knowledge and Data Engineering (TKDE)

（贯穿）轨迹的预处理类工作：

39、（灵活的时空索引），A Flexible Spatio-temporal Indexing Scheme for Large-scale GPS TrackRetrieval，2008

32、（基于客观需求的，轨迹简化策略，方向变化的位置信息量越大）Trajectory Simplification Method for Location-Based SocialNetworking Services，SIGSPATIAL GIS workshop on location-based social networks，2009

31、（稀疏采样轨迹的地图匹配）Map-Matching for Low-Sampling-Rate GPS Trajectories，GIS2009

26、（Top-k区域查询）AnsweringTop-k Similar Region Queries，DASFAA 2010

25、（基于位置点，搜索轨迹）Searching Trajectories by Locations: An Efficiency Study，SIGMOD

18、（发现数据库中的相似记录），Detecting Nearly Duplicated Records in Location Datasets，GIS2010

11、（给定一组点，检索k个最近邻的点）Retrievingk-Nearest Neighboring Trajectories by a Set of Point Locations，SSTD2011

5、低采样轨迹的不确定性处理（比地图匹配性能更好）：Reducing Uncertainty of Low-Sampling-Rate Trajectories， ICDE 2012

参考文献：（按照时间降序，从新到旧排列）

2012

1、群组发现（提出了一个群组发现加速的数据结构）：A Framework of Traveling Companion Discovery on Trajectory DataStreams，ICDE2012

2、热点旅游位置推荐、周边活动发现（第二次发表：协同过滤）：Towards Mobile Intelligence: Learning from GPS History Data forCollaborative Recommendation， Artificial Intelligence Journal，2012-04-29

3、（语义轨迹历史）基于GPS推到用户的社会关系：InferringSocial Ties between Users with Human Location History，Journal of Ambient Intelligence andHumanized Computing

4、基于时间关系图发现出租车行驶路线：T-Drive: Enhancing Driving Directions with Taxi Drivers'Intelligence，IEEETransactions on Knowledge and Data Engineering (TKDE)

5、低采样轨迹的不确定性处理（比地图匹配性能更好）：Reducing Uncertainty of Low-Sampling-Rate Trajectories， ICDE 2012

2011：

6、出租车数据探测城市的异常交通：On Mining Anomalous Patterns in Road Traffic Streams:2011International Conference on Advanced Data Mining and Applications

7、（基于出租数据的城市规划，计算）Urban Computing with Taxicabs，

8、（寻找下一个旅客）Where to Find My Next Passenger?Ubicom2011

9、（交通异常，前一个版本）Discovering Spatio-Temporal Causal Interactions in Traffic DataStreams，sigkdd2011

10、（基于云的，融合多种信息，探寻用户习惯的发现）Driving with Knowledge from the Physical World，SIGKDD 2011

11、（给定一组点，检索k个最近邻的点）Retrievingk-Nearest Neighboring Trajectories by a Set of Point Locations，SSTD2011

12、（个人行程推荐，最初版本），Social Itinerary Recommendation from User-generated Digital Trails，Personal and Ubiquitous Computing

13、（推到出租车行驶状况），Inferring Taxi Status Using GPS Trajectories，2011

14、（旅游推荐，较全面的工作），Learning travel recommendations from user-generated GPS traces， ACM Transaction onIntelligent Systems and Technology，2011

15、（根据单个轨迹推荐位置和朋友），Recommending friends and locations based on individual locationhistory，2011

2010

16、（根据出租车历史，指导行驶方向）T-Drive: Driving Directions Based on Taxi Trajectories，GIS，2010

17、（出租司机，灵活驾驶）Drive smartly as a taxi driver，UIC2010

18、（发现数据库中的相似记录），Detecting Nearly Duplicated Records in Location Datasets，GIS2010

19、（利用语义轨迹，发现相似用户），Finding Similar Users Using Category-Based Location History，GIS2010

20、（前期版本，智能的形成推荐）Smart Itinerary Recommendation based on User-Generated GPSTrajectories，UIC2010

21、（GeoLife，智能生活，双层网络），GeoLife: A Collaborative Social Networking Service among User,location and trajectory，IEEE Data(base) Engineering Bulletin

22、（基于用户的推荐，旅游景点和形成）Collaborative Filtering Meets Mobile Recommendation: A User-centeredApproach， AAAI2010

23、（学习位置间的关联）Learning Location Correlation from GPS trajectories，MDM2010

24、（位置和活动推荐）Collaborative Location and Activity Recommendations With GPS HistoryData，WWW 2010

25、（基于位置点，搜索轨迹）Searching Trajectories by Locations: An Efficiency Study，SIGMOD 2010

26、（Top-k区域查询）AnsweringTop-k Similar Region Queries，DASFAA 2010

27、（计算机学会刊文）Enabling smart location-based services by mining GPS traces，Communication of China ComputerFederation2010

28、（基于云的位置服务）Location-Based Services on the Cloud，Journal on Digital Mobile Era 2010

29、（基于GPS轨迹发现用户交通模式：行走、驾车、公交、地铁），Understanding transportation modes based on GPS data for Webapplications，ACMTransaction on the Web，2010

2009

30、（挖掘位置间的关联），Mining Correlation Between Locations Using Human Location History，GIS 2009

31、（稀疏采样轨迹的地图匹配）Map-Matching for Low-Sampling-Rate GPS Trajectories，GIS2009

32、（基于客观需求的，轨迹简化策略，方向变化的位置信息量越大）Trajectory Simplification Method for Location-Based SocialNetworking Services，SIGSPATIAL GIS workshop on location-based social networks，2009

33、（挖掘有趣位置及旅行顺序）Mining Interesting Locations and Travel Sequences From GPSTrajectories，WWW 2009

34、（挖掘个人生活模式）Mining Individual Life Pattern Based on Location History，MDM 2009

35、（GeoLife生活模式），GeoLife2.0: A Location-Based Social Networking Service，MDM2009

2008

36、（出行模式：步行，公交，驾驶）Learning Transportation Mode from Raw GPS Data for GeographicApplication on the Web，www2008

37、（理解移动特性），Understanding mobility based on GPS data，ubicom2008

38、（基于轨迹挖掘用户相似性）Mining user similarity based on location history，GIS2008

39、（灵活的时空索引），A Flexible Spatio-temporal Indexing Scheme for Large-scale GPS TrackRetrieval，2008

40、（理解用户行为），Understanding User Behavior Geospatially，计算机通信2008

41、（生成用户日志，帮助用户回忆），Searching Your Life on Web Maps，SIGIR2008

42、（GeoLife1.0，在地图上管理自己的GPS日志）GeoLife:Managing and Understanding Your Past Life over Maps，MDM08

转自http://blog.csdn.net/yumengkk/article/details/7523223

上一篇文章介绍了LBSN的概要和从用户角度的研究内容，这篇文章我们将介绍从位置角度的研究内容。

从位置角度的LBSN研究主要分为两块：普通（General）推荐和个性化推荐。普通推荐主要遵循以下模式：trajectories->interesting locations -> popular travel sequences -> itinerary planning -> activities recommendation。个性化推荐分为user-based和location-based。

1 普通推荐

1.1 兴趣位置和旅游序列的挖掘

兴趣位置和旅游序列（travel sequence）随着时间和一些其他因素变化，因此可以从位置轨迹根据时间等因素挖掘兴趣位置和旅游序列。

在进行普通推荐时，我们要考虑两个问题：1 在确定一个位置的兴趣度时，不同用户的轨迹对兴趣度的权重不同，因为用户对这个位置的熟悉程度不同，即用户的经验不同。2 用户的经验和位置的兴趣度是相关的，并且和给定的区域有关。用户经验和位置的兴趣度对于不同的地区可能有不同的值。

1.1.2 兴趣位置的挖掘方法

首先，用户的历史轨迹通过使用基于树的层次图(tree-based hierarchical graph, TBHG)建模。分为以下两步

• 构建一个统一层次框架F，此步和上一篇文章中介绍的方法几乎相同：检测停留点，并以层次为基础将点聚类。
• 在每一层中构建位置图。在框架F的基础上，每一层中根据用户的历史轨迹，加入有向边。此步和上一篇中介绍的为用户轨迹建模的区别是此步同时考虑所有用户的历史轨迹，将所有用户的历史轨迹包含到这个基于树的层次图中。

  

然后，使用TBHG提出基于HITS的推断模型，该模型将用户曾访问过某个点看作用户到位置的有向边。此模型推断出两个值：位置的兴趣度和用户的旅行经验，此过程中模型考虑两个值的相互作用关系和给定的地理区域。

HITS（Hypertext Induced Topic Search）模型

此模型原先是用来进行主题下的超文本搜索的。对于一个搜索请求，HITS首先扩展搜索引擎的返回的一系列相关页面并为他们生成两种排名：authority排名和hub排名。如下图所示，authority是有很多inlink的网页而hub是有很多outlink的网页。HITS的原理是认为好的hub只想很多好的authority，同时，好的authority背很多好的hub指向。页面的authority得分就是指向他的所有的hub的总得分，而hub得分就是他指向的authority的总得分。通过一定数量的迭代，就可以获得最终的得分。HITS的主要作用是针对一个话题对页面进行排名。

相互作用关系

将用户作为Hub，用户访问过很多地方，而位置作为Authority，位置被很多用户访问过。此时的访问就是超文本中的指向关系。

区域相关

很明显，用户的经验和区域相关，比如我对南京很熟悉，但是我对北京就不熟悉。这个概念就和在HITS介绍的搜索引擎当中的搜索步骤对应，首先根据区域构建一个属于这个区域的location集合，在这个位置集合的基础上使用HITS推断模型。

位置集合选择策略

在TBHG模型中，节点（停留点聚类）可作为它的下层节点的区域。因此，可根据用户的选择的区域包括的节点，选择他们共同的唯一的上层节点（ascendant cluster）。举例如：

推断方法

给定一个区域，我们根据此区域(cluster)下面的所有位置构建邻接矩阵，xy坐标为用户和位置，内容为用户访问位置的次数。

比如，对于最顶层团C11，我们可基于所有的五个团构建邻接矩阵：

其中，表示团Cij基于层次l的authority得分，表示用户k给定区域Cij的hub得分。

1.2.2 旅行序列(travel sequence)的挖掘方法

对于给定区域的位置序列流行度的计算，考虑两个因素：1走过这个序列的用户的旅行经验；2 属于这个序列的位置的兴趣度。

对于一个长度为2的序列，A->C，序列的流行度包括以下三个方面：

• 属于这个序列的A的authority得分（即得分乘以离开A的所有的人数中属于这个序列的比例）
• 属于这个序列的C的authority得分（乘以从A中进入C的人数站所有进入C的比例）
• 走过这个序列的用户的hub得分。

如下图：

长度为3的序列的流行度为长度为2的流行度之和。

通常，计算长度为3的流行度比较有用，因为人们不会一次出行中去太多地方。

1.2 旅行线路推荐

通过获得了有趣的位置和旅行序列，可以在在不熟悉城市旅行中提供帮助，但仍有一些问题。第一，如果有很多可以去考虑的位置，用户会希望使他的旅行经验最大化。第二，旅行路线需要使用用户的当前位置、可支配时间和目的地。

以下介绍郑宇发表的相关论文中的路线推荐方法。

离线部分：此部分挖掘群体智慧，即痛过上一小节中介绍的方法计算位置的兴趣度和序列的流行度。

第一步：停留点的抽取和聚类，获得位置层次图。对于每个停留点在数据中有相应的进入时间和离开时间，以此可以计算出位置内的停留时间和位置间的移动时间，为预测路线花费的时间提供基础。

第二步：推断位置图中的每个位置的兴趣度，并计算长度为2的序列的流行度。

离线部分的输出为位置-兴趣度图，节点为附有兴趣度和停留时间的位置，边为人们的移动（我感觉还有序列的流行度）和移动时间。

在线部分：此部分获得用户的请求并找到最佳路线返回给用户。

第一步：请求验证。额，没啥好说的，过滤不规范输入。

第二步：此步在位置-兴趣图中找到满足用户请求的路线。

第三部：对满足请求的路线进行排名。考虑：利用时间率，停留时间率，位置的兴趣度之和，旅行序列的流行度之和。

1.3 位置-活动推荐

位置活动推荐主要是解决两个问题，如果想进行一个活动去哪里以及如果在一个地方有哪些活动。

此节由于文章写的太简陋看不懂，同时参考原参考文献《Collaborative Location and Activity Recommendations with GPS History Data》

推荐系统的架构如下：

由于仅使用轨迹数据，获得的位置-活动矩阵非常稀疏，因此在此系统中加入了其他两个矩阵对推荐进行辅助，分别为位置-特征矩阵和活动-活动矩阵。

位置-活动矩阵

该矩阵中的元素为在该位置进行过的某一活动的次数。

位置-特征矩阵

此特征中，列表示category，比如餐厅、电影院等。根据POI数据库，根据位置里面的所有POI计算location的特征即类别。根据TF-IDF算法计算。

活动-活动矩阵

此矩阵中保存的是活动和活动之间的关系，获得的方法是通过两个活动名称在google等搜索引擎中检索的结果个数来评价。

协同推荐方法

总的来说，推荐算法的目的是计算出位置-活动矩阵的未知元素，该矩阵填满就可以直接进行推荐。

没看懂…，大家仔细看吧。。

2 个性化推荐

为进行个性化推荐，构建用户-位置矩阵，元素为用户到达该位置的次数，以此反映用户对该位置的偏好。在此基础上，便可以使用协同过滤技术。如：

2.1 基于用户的协同过滤

1 根据用户的历史轨迹计算用户的相似度。可根据地理空间模型，也可以根据语义空间模型。

2 位置选择

3 打分。

其实这个基于用户的协同过滤推荐方法和传统的协同过滤的唯一区别就是第一步在计算用户的相似度时根据用户的历史轨迹，而不是用户对item(locationi)的打分，但是历史轨迹又体现了对location的偏好，其实还是一个东西。

2.2 基于item的协同过滤

基于用户的协同过滤在用户数量较大的情况下会需要非常多的计算资源，而location相对来说不会增加太多。

2.2.1 挖掘位置间的关联

位置间的关联不仅仅是类别、距离上的关联，还要从用户行为上体现。比如，人们吃完饭可能会想去看电影，则餐厅和电影院也有一定的关联性。

位置的关联可以用于广告牌投放地的选取、旅游推荐等。

计算位置间的关联主要考虑以下因素：

• 用户访问者两个位置的数量以及用户的经验。
• 包含这两个位置的访问序列。
  • Cor(A,B)不等于Cor(B,A)
  • 在一个序列中，AB的访问越接近，两个位置越相关。

可使用以下公式定义AB的关联度：

Ek表示用户k的旅行经验，a表示两个位置的间隔距离。

我：每个用户不可能只有一个轨迹，对于一个用户多个轨迹这里面好像没有体现，好像只考虑了每个用户的一个轨迹。

2.2.2 The Slope One Algorithm

Slope One算法是基于item评分的算法，此位置推荐算法就是在此算法上面的一个小小的改进。

对于一个评价矩阵，该算法首先计算不同item之间的差值(deviation)：

（计算所有对i和j都进行评价了的用户的i和j之间的差值的平均值）

若要预测j的打分，则将根据其他item预测到的打分求平均值。

（改进）为了更加准确，在根据i预测j的打分时，同时考虑同时评价了i和j的用户数，并作为权值，求加权平均：

2.2.3 位置推荐打分

位置推荐算法和Slope One算法的唯一区别是不用同时评价了i和j的用户数作为权值，而使用两位置之间的关联作为权值：

因为在我们的模型中，过滤矩阵的元素就是用户到达位置的个数，因此使用用户数作为权值就不准确了。

本文是根据郑宇大婶的文章做的总结。主要参考文献为书籍——Computing with Spatial Trajectories中的最后两章。

此篇文章介绍了LBSN介绍、轨迹建模以及从用户角度的一些研究内容。

下篇将介绍从位置角度的研究内容。

1 LBSN介绍

LBSN不仅仅是将位置信息嵌入到社交网络，而是根据位置信息推导出新的社会结构。这里的物理位置包括即时位置和某一段时间的位置历史。此外，依赖关系不仅仅包括梁用户同时出现在相同的位置或具有相同的位置历史(location history)，同时包括从用户的位置信息数据中挖掘到的知识(兴趣、行为和活动等)。

1.1 LBSN服务

位置服务可分为三种类型：

基于位置的标签媒体(Geo-tagged-media-based)：位置作为媒体的一个特征，组织和丰富传媒内容。媒体仍然是主体。

点位置(Point-location-driven)：分享用户当前位置，比如签到。位置（点）是主体，体现了多用户之间的依赖，同时用户生成的内容看作一种特征。

轨迹(Trajector-centric)：点和线。同时添加入tags、photo。tips等。

下图是三种服务类型的比较：

论文上说：第一二种形式可以转化为第三种形式，第三种形式的方法也可以用于第一二种形式。下面主要介绍第三种形式的算法。

作者：我对此感到怀疑，我觉得即使转化为3，也需要较大的修改，这些方法可能需要大幅度修改。文中说可以将1、2转化为3，但是是由于稀疏性，需要使用聚集和协同的方法，但没有说如何使用这些方法。

1.2 LBSN研究方法和研究方向

基于轨迹数据，可构造三种图：

location-location:点表示location，边表示一些用户连续访问这两个location。边的权重表示两位置的关联性。

user-location: 两种点；从用户到location的边表示用户访问过location（权）。

user-user ：表示用户之间的社会关系（1.直接的，2.通过位置数据推导出的）

通过以上三种图，我们可以分别从用户和位置的角度对用户和位置以及他们之间的关系进行理解。即以用户/位置为重点，另一个辅助。

从用户的角度：通过位置理解用户。

• 估计用户间的相似度。2.3节
• 找到一个区域的本地expert。2.4节
• 社区发现。2.4节

从位置的角度：通过用户信息理解位置。

• 普通(Generic)旅游推荐:
  • 挖掘最有趣的位置：找到最受欢迎的位置和行驶序列。
  • 路线计划：根据用户的要求为用户推荐旅游路线。
  • 位置-活动推荐：1在某一个location最火爆的活动。2针对某一活动最受欢迎的地点。

<li>

个性化旅行推荐
• 基于用户的协同过滤
• 基于位置（同基于item的系统推荐）

<li>事件发现</li>

2 位置历史建模

要对以上研究，首先要对用户的位置历史进行建模。郑宇自08年发表了一系列文章，提出了一个新的模型，模型考虑了不同用户间的位置历史间的比较，模式："传感器数据->地理位置"->语义"。此模型有两个优点：1 同时对个人和多人的历史位置建模，使其具有可比较性和可计算性。2 分别基于地理空间和语义空间建模，可以更好的理解用户的行为和兴趣。

直接通过原始的GPS数据对用户位置历史进行测量非常困难，因为原始的GPS数据有一定的误差，而且通过固定的阈值来确定用户是否在一个位置常常是武断的。因此，我们要将原始的历史数据转换成可计算的位置序列，比如：A->B->C。即使如此，根据用户地理空间上的移动轨迹对理解用户兴趣和行为也是不够的，将语义引入可获得更多的知识，即将"A->C"转化为"公园->商场"。

2.1 地理位置模型

此节提出了一个统一模型框架用来在地理空间上对用户的位置历史进行建模，叫层次图(hierarchical graph)。此框架包括一下三个步骤：

图1 地理空间上的用户位置历史建模框架

2.1.1 重要地点检测（Detecting Significant Places）

重要低点表示一个用户可进行有意义行为的位置，一般用户只会在这种位置上停留。检测重要地点的方法一般是根据时间和空间的一些规则，从GPS坐标序列中提取一些位置。

一般来说，我们希望从以下两种情况检测到一个重要地点，1用户进入一个建筑物而丢失掉了GPS信号；2 用户在一个地位空间区域停留的时间超过一个阈值。

停留点(重要地点)的检测方法：在一个轨迹中，如果两个点间的轨迹(Pi->…Pj)（不一定连续）之间的所有的点之间的距离小于一个阈值(对于所有的i<=k<j,dis(Pk,Pk+1)<阈值d)，而两点间时间大于一个阈值（Int(Pi,Pj)>阈值t） ，则这些点构成了一个停留点（Stay Point）。

下图说明了停留点的检测方法：对于一个轨迹（p1->p2->…->p7），在B)图中可以看出，P1构成一个单独的点。转移到P2，发现P2，P3和P4与P2之间的距离小于阈值，如果P2和P4之间的时间间隔大于阈值t，则这三个点构成一个停留点，转到P4，发现P5和P6也符合以上时空规则(P4/P5/P6间距离小于阈值d，P4、P6的时间间隔大于阈值t)，将P5和P6引入到这个停留点。最终，我们获得P2到P6都属于一个停留点。

文中还是用了一定的篇幅说明了选取距离阈值d为200m，时间阈值t为15min是一个比较合适的选择。

2.1.2 构造统一框架(Formulating a Shared Framework)

虽然通过处理单个用户的历史轨迹可以获得用户的停留点，但是不同的用户在同一个位置可能表现为不同的停留点，如两个用户从不同的入口进入同一个商场。

统一层次框架如图1所示，框架将不同用户的停留点统一聚类，不同的类别表示一个位置/区域，不同的层次表现了不同的位置大小粒度。

这样，统一层次框架为不同用户提供了重构它们的位置历史的统一的框架，用户的位置历史可以基于这个框架表示。

2.1.3 构建位置历史

根据构造的统一框架，将停留点在不同层次上映射至聚类点。用户的历史轨迹像一个层次图，有两个结构构成：层次结构和每一层次上面的图。

2.2 语义位置模型

此节的目的是将用户的历史轨迹从地理空间映射至语义空间，这样可以更好的理解用户兴趣，也可以比较在地理空间没有交集的用户（两个城市）。

此方法扩展了地理位置建模的方法，主要也包括三步，与地理位置建模方法对应，主要的不同在于第一步。

2.2.1停留点表示(Stay Point Representation)

这一步是试图描述停留点的语义。但是由于GPS定位的误差以及兴趣点(point of interest, POI)的密集，有些建筑物里面甚至有很多类型的POI（比如德基广场），这样就很难对一个停留点进行语义描述。

因此，文章首先将停留点扩展为停留区域(stay region)，然后根据此区域中的POI构建一个特征向量来表示这个停留区域。使用TF-IDF（term frequency-inverse document frequency）算法计算停留区域中的POI类别对此区域的表示能力，此区域中该类别的POI越多，其他区域中该类别的POI越少，则该类POI对该区域的表示越重要。

注：此处的停留点应该是首先使用2.1.1节计算的停留点，然后通过位置POI数据库，计算各停留点的POI特征向量。

特征向量的定义如下：

2.2.2 构建统一语义框架

这一步将停留区域根据特征向量使用聚类的方法将停留区域分为不同的团(Group)，在同一个团下面的停留区域认为是一个具有相同语义类型的位置。然而，由于在语义层面上位置仍然是具有层次结构的，因此我们将语义位置也建模为层次结构模型，就像2.1.2一样。如下图所示。

2.2.3 构建个人历史轨迹

2.3 用户相似度挖掘（从用户的角度）

在LBSN中，存在两种用户关系，一种是传统社会网络的连接关系，还有一种是通过位置数据获得的用户关系。第二种社会关系扩展了传统的社交网络，同时，这种社会关系一般基于用户的历史轨迹的相似性获得。通过历史轨迹挖掘到的用户间的相似性可以有很多用途，比如朋友推荐、社区发现和个性化位置推荐等。

在郑宇的一系列文章中，用户的相似度计算分为两个步骤：

1. 对于两个用户，在每一层次的图中找到一组相似的序列。相思序列指两人以相同的顺序和相同的时间间隔访问某组地点。
2. 基于相似序列，计算两人的相似度，主要考虑以下三个因素：

• 用户移动的位置序列，相似序列越长，两人越相关。
• 层次属性。相似序列的层次越高(由上向下)，即粒度越小，用户越相似。
• 位置的流行度：相似序列的位置越流行，用户相似度越低。

此框架以用户的位置历史（位置层次图）为输入，用户的相似度为输出。

2.3.1 相似序列检测

文中介绍了轨迹匹配(Travel Match)和最大轨迹匹配的概念，总的来说寻找轨迹匹配就是根据两个轨迹中同一位置以及位置的时间间隔判断，而最大轨迹匹配就只在轨迹中能找到的最大的轨迹匹配（额，有点废话），我们计算用户相似度用到的就是最大轨迹匹配。注意，轨迹匹配不要求位置是连续的，可以使地理空间上的或语义空间上的。

注：两条轨迹可能存在多个最大轨迹匹配。此最大轨迹匹配并不是要求最长的，而是要求前面没有，后面没有，中间没有即可。

由于要考虑时间因素，传统的最大序列匹配算法不能直接使用，文中也提出了一个最大轨迹匹配算法。（具体算法查看资料）

首先找到长度为1的匹配，然后将这些匹配作为图中的边构建前驱图，图中点表示同时出现在两个轨迹中的点。然后在前驱图中找到最长路径(并不要求长度最长，只要该路径前面和后面没有节点)，则前驱图中的路径就对应相应的最大轨迹匹配。

2.3.2 计算用户相似度

在检测到两用户最大轨迹匹配之后，可根据位置的流行度、顺序属性和层次结构计算两用户间的相似度。

附：N是所有用户的数量，n是访问过位置c的用户数量。

解释：给定历史轨迹LocH1和LocH2，两轨迹间的相似度定义为轨迹图的不同层次的相似度之和，fw(l)=2^(l-1)，l表示轨迹图层次，层次越高，权重越大。

某一层次的轨迹相似度表示为不同最大轨迹匹配的相似度之和，m为最大匹配的数量。同时，使用两轨迹的长度对其进行规格化。

最大轨迹匹配的相似度表示为包含在匹配中的地点的流行度。Gw(k)=2^(k-1)。匹配中的位置越不流行，匹配的位置数量越多，则相似度越大。

附：Gw(k)使用指数的原因是实验发现随着最大匹配序列数的增加，最大匹配成指数减少。

2.4 朋友推荐和社区发现

计算了用户之间的相似度以后，我们可以分层次的将用户聚类成团(cluster)，每个团表示一群兴趣相同的用户，不同的层次表示兴趣粒度不同。同时，我们可以在每一个团中找到一个代表，可以通过找在这个团中和其他用户的相似距离最近的点作为此团的代表。

使用层次结构有两种好处：1）可更快的查询相似用户（只需要查询同一团中的用户）。2）更快的插入新用户。只要迭代的计算不同层次的团中的代表用户和新用户的相似距离即可。

由于以下三种问题，朋友推荐和社区发现仍然是一个需要解决的问题。

• 公开的数据集
  • The reality mining dataset MIT
  • GeoLife Microsoft

<li>

Ground Truth(最理想的、用来和实验比较的值，实验如果和该值相同或相近，则最好)
• 调查问卷
• 从社会关系中抽取

<li>评价方法</li>

本文是视频的笔记，讲稿中并没有这个内容，所以记得有点乱。本文将的是在使用机器学习解决问题时需要注意的内容和建议。

1 调试学习算法

在使用机器学习时，如果发现学习后的效果并不好（误差较大），对算法进行改进的一些方向和方法。

例如：在垃圾分类的问题中，选取了50000个单词中的100个单词作为特征，使用贝叶斯逻辑回归（梯度下降），有20%的测试误差。

在这种情况下，可以想象的有一下八种优化方法：

1. 使用更多的训练样本
2. 100个单词作为特征太多，减少一些
3. 特征太少，增加一些
4. 更换一些特征（单词）
5. 梯度下降还没有收敛，再运行几次梯度下降算法
6. 使用牛顿方法
7. 更换算法参数
8. 使用SVM算法

如果盲目的使用以上优化方法，可能会浪费很多时间，比如可能已经有了足够的训练样本，但是使用者不知道而去获取更多的训练样本，可能结果并没有好转。所以要根据一些方法判断如何优化。

首先，可以判断误差过大是因为高偏差还是高方差造成的。判断的方法是比较训练误差和测试误差，对于高方差来说，测试误差远大于训练误差。而对于高偏差来说，测试误差很高，同时训练误差也很高。

高方差学习曲线：

高偏差学习曲线：

对于刚刚开始那八种优化方法的前四种，1、2是解决高方差问题，3、4是为了解决高偏差问题。所以，当我们知道我们现在的学习算法的不精确是因为高方差还是高偏差以后就可以一次选择一个合适的优化方法。

除了判断训练错误的原因是高偏差还是高方差之外，我们还有第二种调试方法：判断误差的原因是因为算法还没有收敛还是因为目标函数的选择有问题。判断此问题的方法video里面已经详细给出，我这里就不详细介绍。

总之，当学习算法不能很好的工作时，就和我们平时编程一样，我们需要去debug找到算法工作不正常的地方，找到一个目标才能对其进行修改。这里面有一些经验上的知识，也有指导性的知识。总之，在算法工作不正常的情况下，不要盲目的优化！

2误差分析

对于大部分系统（包括但也不仅仅包括学习系统）来说，一般包括多个组件，每个组件实现一个小功能，而通过整合实现一个总体功能满足最后的需求。比如人脸识别系统，可能包括图像预处理、背景识别、眼睛识别、鼻子识别等等。。。当这个系统的误差较大时，我们需要首先去判断哪个组件是误差的较大贡献者，而对其进行重点优化。

可以使用以下方法进行分析：依次将组件的输出精确率人工的提升为100%，而观察系统的最终结果。那一个组件的精确率的提升造成结果的提升最多，说明这个组件是瓶颈。

还有一种情况，目前获得的结果不错，我们想分析是因为那些特征/组件而获得了不错的结果，可以依次去掉这些特征/组件，观察精度下降的程度。

3 Getting start on a problem

在开始解决一个学习问题时，有两种解决思路：

1. 仔细设计系统，提取正确的特征，采集正确的数据，使用正确的算法。这种方法是将工作量放在前期，获得的结果可能比较好。
2. 创建一个草稿然后进行不断修改。先实现简陋的解决方案，利用误差分析/诊断方法进行不断的修改。优点：可以快速的建立系统，找到关键的部分并对其进行重点优化和修改。

?

?

?

在我们以前介绍的学习模型中，都是批量学习(batch learning)，而我们这一节将会介绍一种新的学习模型——在线学习。在线学习就是样本集成顺序出现，系统一边预测，一边学习。此节内容不属于任何模块，这里简单介绍一下。

正式说明如下：有顺序的样例：，首先算法根据x<1>预测y<1>，然后系统获得y<1>值，然后根据x<2>…以此类推。。在在线学习中，我们感兴趣的是总错误数量，即。

拿二值感知器分类举例y={-1,1}，感知器学习算法的假设函数为：

????

在某一步中，当给出训练样本（x,y）后，感知器学习算法根据规则更新参数。如果预测正确即，参数不变，如果预测错误，对参数进行以下更新：

????

以上在线学习更新算法非常简单，因为感知器学习只需要获知的正负号。

但是，有定理证明，在线学习的错误数存在上界，并且上界与样本数量m和特征空间维度n没有关系。

Video里面并没有对定理的证明进行讲解，本稿也不对其进行证明了，定理说明及证明可参考文稿。

目前我们已经学习了很多机器学习算法，比如线性模型、神经网络、多项式回归模型等。当我们要解决一个机器学习问题时，首先需要选择一个适合恰当的模型，有些模型还需要选择参数，比如局部加权回归中的bandwidth等。

问题：在有限的模型集合M=｛M1,M2,…Md｝中为问题选择一个最合适的模型Mi。

1 交叉验证

对于以上问题，如果选择使用经验风险最小化（ERM）方法， 在所有的模型中选择具有最小训练误差的模型，似乎是可以的，但是是不可以的。因为选择最小的训练误差往往具有较高的方差，即选择较高次数的多项式模型，出现过拟合现象往往具有较大的真实误差。

可以使用简单交叉验证方法（hold-out cross validation ,also called simple cross validation）：

• 随机分割样本集S为训练集(70%)和测试集(30%)。
• 使用训练集训练各个模型，分别获得假设函数。
• 对假设函数通过测试集进行验证，选择最小误差的模型。

通过使用测试集对假设函数进行验证，我们更好的评价了假设函数的真实误差。同时，也可以选择最小误差的模型以后再使用所有的样本对模型进行学习。简单交叉验证的缺点是数据集的浪费，即使我们在选择模型完成以后在使用所有的数据进行再学习，但我们在选择样本时使用的训练集只是所有的数据集的70%。

为了节省数据，以下是k-fold交叉验证：

• 将样本集分割成k份，每份有m/k个样本。样本子集为｛S1…..Sk｝
• 对于每个模型Mi，对其使用如下评价：
  • 对于每个样本子集Sj：使用除Sj的其他所有样本子集S1US2U…Sj-1USj+1U…USk对模型进行训练并获得假设函数hij。
  • 使用hij（over j）真实误差的的平均值评价模型Mi的真实误差。
• 选择具有最小真实误差的模型Mi，并通过所有的数据集S对模型进行训练获得最终的假设函数。

对于上述算法，常用k=10。但是在极端情况下，比如样本数据极少极为昂贵，可以将m个数据样本分为m份，每份只有一个样本，每次使用m-1个样本进行训练，使用1个样本进行测试。我们称之为leave-one-out交叉验证。

2 特征选择

特征选择是模型选择的一个特殊但重要的例子。比如当我们有一个监督学习问题，特征空间维度n很大，而且怀疑只有一些特征和学习任务，但是同时数据样本量还小有关。即使我们选择最简单的线性，假设空间的VC维也是O（n）。除非训练集很大，要不就可能出现过拟合的问题。

因此，我们需要通过特征选择算法减少特征的数量。假设当前有n个特征，如果使用遍历所有可能的特征组合并使用交叉验证选择特征的话，有2^n可能的组合，这样做不靠谱。比较靠谱的是使用启发式算法。

向前搜索算法：

除了向前搜索算法，还有向后搜索算法，即初始化F为全部特征，然后重复的删除一个影响最小的特征。这两种算法被称为wrapper model feature selection，因为它们是一个报过了学习算法的算法。这种算法一般可以获得比较好的结果，但是时间复杂度很高，因为它需要O(n^2)次调用学习算法。

过滤特征选择算法通过是计算每个特征的S(i)来评价特征i对区分y的重要性。只需要计算所有特征的S(i)并选择重要性（S(i)）最高的一些特征。

我们可以定义S(i)为Xi和y之间的关联度，并通过训练集进行计算。比如，我们可以计算xi和y之间的相互信息作为S(i)：

在以上公式中，我们假设xi和y都是二值的，比如垃圾分类情况，相关的计算都可以根据训练集预测。

同时，相互信息也可以用KL距离(kullback-beibler divergence)，也就是两概率分布之间的差异表示：

通过计算p(xi,y)和p(xi)p(y)之间的差异，可以获知xi和y之间的依赖程度。如果p(xi,y)等于或约等于p(xi)p(y)，则说明它们是独立的，表示无依赖，则S(i)很低。

3 贝叶斯统计和规格化

这一节中，我们介绍一个防止过拟合的新方法。此方法的本质就是在假设?是随机变量而给他一个先验概率如高斯分布N(0，xx)，这样参数就会接近于0从而防止出现了过拟合现象。

在前面，我们使用最大似然估计找到样本出现概率最大的参数：

这里是将参数?看成未知的常量，也就是我们想要求出的（频率学派）。

另一种方法去估计参数的方法是从贝叶斯学派的角度，认为参数?是位置的随机变量。使用p(?)表示参数?的先验概率，比如猜测?服从高斯分布；然后根据样本集获得参数的后验概率：

当对于一个新的样本X并希望预测y时，可以基于训练集S计算不同y的概率(计算出现?的概率并乘以在?情况下基于x出现y的概率，然后积分?，即求基于所有?求y概率的期望值)：

然后计算y的期望值（对于离散值使用累加代替积分）：

????

上面的过程我们可以看作完全贝叶斯预测过程，将参数?看作随机变量，对所有的?后验概率，然后根据?求y的期望值。但在以上过程中，所有的计算都非常困难。因此，在实际使用中，我们常常估计?的概率并找到基于训练集S参数?最可能的情况，也就是找到使后验概率p(?|S)最大的参数?：

计算出了参数?，在根据x预测y时就可以直接使用假设函数。

上式和最大似然性估计的公式几乎相同，只不过在最后加入了?的前验概率p(?)。在实际使用中，我们常常假设，这样的话，参数会大部分接近0，这和参数选择的思想是一样的，也就防止了出现过拟合的现象。

比如在文本/邮件分类的学习问题中，有5000个feature，可能里面的大部分feature都是没用的，所以我们给他先验概率（假设）认为他们大部分接近于0，这样就和特征选择获得了差不多的效果。（特征选择对于不重要的特征的权值置为0，而这个方法对于不重要的特征权值接近0）

1 偏差/方差权衡

对于我们前面介绍的欠拟合和过拟合的问题，代表着两种误差较大的建模方法。对于欠拟合来说，在模型结果和样本内结果误差较大，可以推论为在模型结果和实际结果误差较大，这种成为偏差（bias）。对于过拟合来说，虽然模型结果和样本内结果误差较小，但是由于样本的不确定性和随机性，样本的结果不能反映真实世界的结果，所以存在方差（variance）。真实误差（generalization error）主要有偏差和方差构成，一般来说，需要在偏差和方差之间进行权衡，如果模型太简单（或参数太少，欠拟合），容易出现比较大的误差和比较小的方差；如果太复杂，容易出现较小的误差和较大的偏差。

学习理论主要是通过一些直觉的经验或者推导出来的规则，使我们可以根据不同的情景最好的应用学习算法。主要是为了回答以下问题：

1 我们是否可以正式的权衡偏差和方差，也就是说自动选择一个合适的模型。

2 在学习算法中，真实误差是最重要的，但是大部分学习算法都根据训练样本进行学习。训练样本和真实误差之间的关系如何。

3 在哪些情况下学习算法可以较好的工作。

首先我们介绍两个定理：

联合界限定理：A1，A2….Ak分别代表k个不同的事件，则：P（A1UA2U….UAk）<=P(A1)+…..+P(Ak)

Heoffding不等式（中心极大值定律）：Z1,….Zm为m个独立同分布的随机变量，并且服从伯努利分布。即P(Zi=1)=φ,P(Zi=0)=1-φ。令表示这些随机变量的平均值，同时给定常量r，则：

为了方便表述，我们这里讨论的都是二值分类，也就是说y={0,1}。

对于一个训练集来说，我们定义训练误差（training error）为训练集中次数出现的概率/频率：

同时，我们定义真实误差(generalization error)，物理意义可以理解为当出现一个新的样本并且符合D分布时，h可能分类错误的概率：

现在考虑先行分类，，一个获得合适的参数?的方法是使训练错误最小，我们称之为经验经验风险最小（ERM）过程。

同时，在下面的学习理论的介绍中，我们不考虑具体的假设参数，也不考虑我们是否使用的是线性分类模型等。我们定义假设空间H，学习算法将在假设空间中找到一个合适的假设函数（包括了参数和模型）。

2 有限假设空间

首先我们考虑有限假设空间的学习问题，有限假设空间包含k个假设函数H=｛h1,h2,…hk｝。函数从特征空间X映射到｛0,1｝，而ERM试图寻找一个使训练错误最小的假设函数。下面我们根据训练集对于真实误差给出一些保证，1)我们发现训练误差和真实误差相近；2)对于假设函数，真实误差存在上界。

对于任一假设空间中的函数hi，令。

则训练错误可以表示为：

因此，可以理解为m个从独立同分布的伯努利分布的随机变量Zj的平均，而是这个伯努利分布的真实平均值。则由中心极大值定律可知：

由上式可知，对于某一假设函数hi，如果样本量m较大，训练误差有很大的概率约等于真实误差。现在将某一个假设函数推广为所有的假设函数。我们用Ai表示事件，则使用联合界限定理，有：

可以进一步推导出：

也就是说，（一致收敛uniform convergence）对于假设空间的所有假设函数h，训练错误约等于真实错误的概率（置信度）大于某个值。

在以上的讨论中，我们是给定一个样本量m和r，获得了一个误差的可能性，即的最大概率界限。同时，我们可以通过两个参数，获得任一个参数的界限。比如给定r和置信度σ，我们需要多少样本量m才能保证在概率1-σ下训练误差和真实误差之差小于r。我们获得了以下公式：

（样本复杂度）上式说明了样本数量m大于某个界限时，可以有1-σ的概率保证，对于所有假设空间里的假设函数，训练误差与真实误差之差小于r。同时上式也说明了需要的样本数量只与假设空间中的假设函数数量成log关系，即使k很大，m增长的也比较慢。

下面，我们定义即h*具有最小的真实误差，也就是物理意义上最好的假设函数。假设一致收敛成立，则：

上式1、3步试用了一致收敛，第二步根据。我们可以获得以下结论：如果一致收敛成立，则的真实误差最多比最好的假设函数h*差2r。将上式扩展，可得到以下定理：

定理 对于|H|=k，给定m和σ，则在置信度1-σ有：

同时，以上模型可以和我们以前介绍的偏差/方差相对应。当假设空间即k增大时，只能减小，因为可能找到一个使误差更小的函数（和偏差对应），但是第二项会增加（方差）。

注：第一项的真实物理意义其实是最好的函数的真实误差，也就是其实我们想知道的。但是我们没法获得最好的函数h，我们只能使用来评估。其实我们最后获得的是而不是h.

3 无限假设空间

在以上的论述中，我们仅考虑了有限的假设空间，而在现实应用中，大部分都是无限假设空间。比如线性分类，每个参数都是一个实数，则得到了一个无限假设函数空间。

在有限的假设空间中，我们使用的是假设空间中假设函数的个数来表示的假设空间复杂度（模型复杂度）。而在无限假设空间中，我们使用一个新的值度量假设空间的复杂度——VC维。

VC维的定义为：在实力空间X上的假设空间H，VC(H)表示可被H打散的X最大有限子集大小。如果X的任意有限大的子集可以被H打散，则VC（H）为无穷大。

如果我们要证明VC(H)大于d，我们仅仅需要证明存在至少一个大小为d的集合可以被H打散。

比如在二维空间上的线性分类函数集合，在二维空间上存在三个点的集合可以被一条直线随意划分（除非这三个点在一条直线上），而对于任意一个四个点的集合，直线都无法对其进行随意划分。所以线性分类函数的VC维为3。

在以上基础上，我们可以获得以下结论：（证明略）

由上面可知，如果假设空间存在有限的VC维，则一致收敛随着m的增加而出现。同时，可以获得关于样本复杂度的以下推论：

也就是说，为了获得较好的学习结果，样本数量和VC维成线性关系。同时，对于大部分合理的假设空间，VC维与模型的参数成线性关系。

附：以上所有的结论都是在ERM模型基础上得出的。视频中同时介绍了逻辑回归和SVM算法。SVM算法虽然具有无限的特征空间（kernel函数），但是由于它只考虑间隔较大的分类函数，所以VC维也比较低。