MMD_3a_CommunitiesInSN

SN means social network。

The first 12 videos cover this topic.

The first four videos are part of the basic track, and cover machine-learning techniques for finding the best set of “overlapping communities,” following the intuition that people generally belong to more than one community, e.g., their high-school friends, their coworkers, etc.

Videos 5-12 are part of the advanced track. They use concepts from linear algebra to explain how to break graphs optimally (i.e., break the fewest edges) into disjoint “communities.”

概述

实例

想要将社交网络所属的不同组给划分开来。

需要解决的问题

从AGM到Network

如何从模型推出社交网络

所谓社交网络,就是两个人U,V是不是朋友,或者理解成图论中的两个node是否需要连接。

模型

Community-Affiliation Graph

特点

flexibility

从AGM到bigClam

AGM是一种计算P(u,v),即u,v两个点之间是否有edge的概率。 同样的,bigClam也是计算两点间是否有edge的概率。

区别是: 前者有:社区C中的任何两个人是朋友的概率 后者有:每个人对于特定组的归属度

bigClam的求解问题

这里讨论的是,已知一个网络,求解模型的问题。

已知: 网络中的任何两个人是否是好友,是否有edge相连。也就是前面讨论中求出的连接概率。 求: 网络的参数F矩阵。

转化成优化问题,可以使用梯度法求解。 并且根据一些trick,将问题的复杂性减小。

最大似然的优化问题

注意,这里对优化问题去了log值,理由是:

  1. 乘法问题变成了加法问题,方便计算分析
  2. 乘法问题的话错误会不断快速地累积,加法问题可以避免这个问题
  3. log不改变原来的单调性

梯度下降法

对每个点进行一次迭代,每经过一个点更新参数,直到达到稳定值。

注意,这里是求最大似然值

  1. 可以变下符号
  2. 更新参数的时候把减号变成加好,因为求导的方向也就是梯度的方向,是函数增长最快的方向。

但是,这种方法有个缺点,对于和u不适邻居的数据,都要进行迭代计算,所以每次更新的话会遍历所有的样本点,这样时间复杂度是O(N)O(N)的,不利于大数据的计算。

改进的梯度下降

改进后的方法,只需要预先计算一次全体值,然后cache方便之后计算。 接下来每次只需要计算与u相邻的节点值,这样的话在大数据的情况下极大地减少了时间,时间复杂度是关于邻居集合的线性的。

Scalability

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开心的学习之路

知识篇——聚类算法应用

时隔两月开始继续储备机器学习的知识,监督学习已经告一段落,非监督学习从聚类开始。 非监督学习与监督学习最大的区别在于目标变量事先不存在,也就是说 监督学习...

3075
来自专栏机器学习算法与理论

使用开源人脸特征提取器进行脸部颜值评分

本文仅为模型应用实战,而非颜值研究,所得结果仅供娱乐,仅供参考。 方法也仅供参考。 一般而言,数据量越大,结果越接近正常人审美。由于本次数据量较小,故仅为实验。...

5369
来自专栏大数据文摘

R: 学习Gradient Boosting算法,提高预测模型准确率

22011
来自专栏人人都是极客

1.训练模型之准备工作

经常关注我公众号的读者应该还记得之前写了5课关于嵌入式人工智能的文章,可以点击这里查看(文章末尾有前4节课时的推荐),前5节课时都在讲一个主题,即如何识别物体。...

3429
来自专栏大数据文摘

ResNet告诉我,我是不是世界上最美的人?

1236
来自专栏数据派THU

一文读懂FM算法优势,并用python实现!(附代码)

作者:ANKIT CHOUDHARY 翻译:张媛 术语校对:冯羽 文字校对:谭佳瑶 本文共3933字,建议阅读9分钟。 本文带大家了解因子分解机算法并解析其优势...

1K8
来自专栏PPV课数据科学社区

R语言之kmeans聚类理论篇!

前言 kmeans是最简单的聚类算法之一,但是运用十分广泛。最近在工作中也经常遇到这个算法。kmeans一般在数据分析前期使用,选取适当的k,将数据分类后,然后...

53011
来自专栏新智元

【何恺明最新论文】非局部神经网络,打造未来神经网络基本组件

【新智元导读】何恺明又出论文了,这次与CMU和FAIR的几位作者合作,提出了“非局部神经网络”。受计算机视觉中的经典非局部均值方法的启发而来,非局部网络可以作为...

36511
来自专栏机器之心

教程 | 从超参数到架构,一文简述模型优化策略

模型可以在训练过程中通过修正超参数而逐步建立。这在迁移学习中最为常见,在这种环境中,我们试图将现有模型的知识应用到新领域或新任务中。这是持续学习中更常见的问题,...

553
来自专栏腾讯大数据的专栏

递归的艺术 - 深度递归网络在序列式推荐的应用

在内容爆炸性增长的今天,个性化推荐发挥着越来越重要的作用,如何在海量的数据中帮助用户找到感兴趣的物品,成为大数据领域极具挑战性的一项工作;另一方面,深...

2599

扫码关注云+社区