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 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

Attribute-Enhanced F R with Neural Tensor Fusion Networks 阅读笔记

因为标题长度有限,所以把Face Recognition简写成F R,论文题目应为《Attribute-Enhanced Face Recognition wi...

3037
来自专栏AI科技大本营的专栏

干货 | 转型人工智能,你需要掌握的八大神经网络

翻译 | AI科技大本营 参与 | 林椿眄 编辑 | Donna 为什么我们需要机器学习? 机器学习可以解决人类不能直接用编程来应对的复杂难题,因此,我们喂给机...

3517
来自专栏统计学习方法

《统计学习方法》第八章-提升方法

在《统计学习方法》中第八章提升方法,包括四节,第一节介绍AdaBoost、第二节介绍AdaBoost的误差、第三节介绍从前向分布算法来实现AdaBoost、第四...

1936
来自专栏人工智能LeadAI

深度学习的三大生成模型:VAE、GAN、GAN

本章将为读者介绍基于深度学习的生成模型。这种模型的形式主要是根据原始图像推测图像具备的一些性质,例如根据数字图像推测数字的名称,根据自然场景图像推测物体的边界;...

4378
来自专栏数据派THU

VAE、GAN、Info-GAN:全解深度学习三大生成模型

来源:1024深度学习 作者:冯超 本文长度为2600字,建议阅读6分钟 本章介绍基于深度学习思想的生成模型——VAE和GAN,以及GAN的变种模型。 在深度学...

3868
来自专栏媒矿工厂

基于双流编码-解码深度网络的视频对象分割算法简介

背景介绍 视频对象分割(Video Object Segmentation),目的是将视频段中的物体连续地“抠”出来以得到视频每一帧的前景、背景分割结果。分割得...

4123
来自专栏新智元

【致敬ImageNet】ResNet 6大变体:何恺明,孙剑,颜水成引领计算机视觉这两年

【新智元导读】2015 年,152 层深的 ResNet 横空出世,不仅取得当年ImageNet竞赛冠军,相关论文在CVPR 2016斩获最佳论文奖。ResNe...

4568
来自专栏ATYUN订阅号

机器学习模型的特征选择第一部分:启发式搜索

特征选择能够改善你的机器学习模型。在这个系列中,我简单介绍你需要了解的特征选择的全部内容。本文为第一部分,我将讨论为什么特征选择很重要,以及为什么它实际上是一个...

38310
来自专栏大数据挖掘DT机器学习

进阶:用初等数学解读逻辑回归

作者:龙心尘 && 寒小阳 (感谢投稿) 原文:http://blog.csdn.net/longxinchen_ml/article/details/4928...

27911
来自专栏决胜机器学习

​ 机器学习(九) ——构建决策树(离散特征值)

机器学习(九) ——构建决策树(离散特征值) (原创内容,转载请注明来源,谢谢) 一、概述 1、概念 决策树,这个概念是一个很常见的概念,应该是机器学习中最...

3655

扫码关注云+社区