【AIDL专栏】操龙兵：非独立同分布学习

Progress Review: Non-IID Learning

大数据分析（big data analytics）就像是“盲人摸象”，要解决的问题是如何让“盲人”识别“象”，不管“象”大还是小。我们分析很多数据时会面临这种“we don’t know what we don’t know”的问题，其中一个最基本的问题可能就是学习问题所基于的基本假设，其中之一就是独立同分布假设（independent and identically distributed - IID）。

实际的问题与数据一般可能都是非独立同分布的（Non-IID），数据具有非独立同分布性（Non-IIDness）。分析非独立同分布数据的学习理论与方法称之为非独立同分布学习（Non-IID Learning）【1, 2, 3】。

由于时间关系，这里只能简单介绍我们在非独立同分布学习方面的某些研究进展，特别侧重概念与思想方面。实际上，我们的研究包括非独立同分布性的基本概念，数据表达，数据离散化，对包括K-Means、Spectral Clustering、KNN、Decision Tree等基于IID假设的经典算法的改进，研究Non-IID集成学习、图像处理、计算机视觉、统计机器学习、模式发现、推荐系统、文本分析、关键词查询等【3】。非独立同分布学习涉及经典学习理论的各个方面，个人认为很多原有的基于独立同分布假设的学习理论与方法都可能需要重新思考，特别是在出来多源异构数据时，是不可回避的根本问题。面向实际问题与数据的分析与学习理论与方法需要更针对实际问题和实际数据的特点与复杂性。

IIDness / IID Learning

一般的学习问题或分析问题可以抽象成上图左侧的描述。外圈虚线是学习问题的边界，不同形状颜色的图形代表不同类型的对象或数据源，彼此的连线反映了它们之间的关系。一般的学习基于IID假设，转换为右侧图示，O1~O3三个对象被认为是同分布的，且相互独立。之后构建目标函数。以O3为例，参考O3和基准O （benchmark）之间的关系计算距离或相似度d，再通过目标函数检测其与O1或O2是不是同一类、群、模式，或是不是异常。

如图是一个股票交易数据的例子，对其进行K-Means或Fuzzy C-Means聚类。有时效果不好，可能的原因是这些方法基于IID假设，但实际对象间存在关系，此外数据分布的异构性、学习的目标、均值的设置等也有所影响。对于Decision Tree等一些分类算法，如果数据不满足IID假设，结果也会存在问题。

简言之，利用基于IID假设的独立同分布学习算法在Non-IID数据上学习，得到的结果可能不完整、有偏差，甚至是错误的。

Non-IIDness / Non-IID Learning Concepts

下面介绍非独立同分布性Non-IIDness的概念【2】。不论是大数据还是小数据都有两个问题：一个是异构性（Heterogeneity），体现在很多方面，比如数据的类型、属性、数据源、关注的数据的方面，还包括数据的模式、结构、分布、关系，甚至学习结果也可能是异构的；另一个问题是Coupling Relationships，它不一定就是dependence、association或correlation，而是涉及到很多方面，有比较复杂的关系、层次、类型等。这两方面结合起来，就是非独立同分布性（Non-IIDness）。

从一个例子来理解Coupling Relationships。如上图，一个人的不同行为behavior1、behavior2之间存在关系，关系可能有很多种，比如Temporal Relation、Inferential Relation、Party-based Relation。我们需要研究如何将这些复杂的显式或者隐式的关系表达出来。

Non-IID的基本思想是，对于一个学习问题，要尊重其原本特点与复杂性，原来的异构要保持，原来的关系也要充分学习、表达出来。比如判断图中O3是哪个模式、群、类或是不是异常时，要考虑O3是否受O1或O2的影响，因此计算d3要考虑r13和r23。寻找O点（benchmark）时，也要考虑它会受到d1、d2影响。这两方面结合起来，目标函数就非常复杂了。以上就是对Non-IID学习高度抽象的一种表达。

Coupling Learningand Non-IID Categorical Clustering

首先介绍非独立同分布学习中的Coupling Learning（耦合学习）【3】的概念与方法，我们结合K-Modes聚类法进行介绍【4】。

非独立同分布学习需要建立在一个比较合适的数据结构上。如果数据能够用信息表来表达，可以作为一种研究非独立同分布学习的基本数据结构。

信息表里有O1到ON多个对象，有很多属性来描述这些对象，后面的M1到MQ可能是多个方法，或者是multi-view、multi-task、multi-label等，构成一个扩展信息表，表示一个学习问题所涉及的数据、方法与结果。对扩展信息表进行分析，比如在A2列，假设A2属性是性别，把每个对象的属性值标出来（V12, V22,…,VN2），考虑这些属性值之间的关系（称为属性值耦合关系，intra-attribute couplings），同时也要考虑该属性受其他属性A1,…, AJ等的影响，比如年龄、工作性质、兴趣等，称之为属性间耦合关系（inter-attribute couplings）。进一步计算对象间（比如O1, O2等）相似性时就需要把属性内与属性间的耦合关系综合起来。有时候这些耦合关系会比较弱，有时候关系会比较强。对于多方法M1到MQ，也要考虑基于每个方法的结果之间的关系，以及它们与属性耦合的关系。

对每个对象进行学习的时候，要进行层次性的思考，从每个属性到不同属性的交互，再到多方法、多数据源等。这些方面考虑得比较周到，对对象进行分类、聚类或异常检测等学习与分析时才比较准。这是一个基本的框架，下面讨论这些层次化耦合学习的一个具体例子。

首先构建一个信息表，u是不同的人，有性别、年龄、工作性质等属性。为了学习层次化的耦合关系，这里提出两个概念，一个是属性内部关系，一个是属性间的关系。比如对属性a2，u1和u3的值分别为B1和B2，B1和B2之间的关系就是intra-attribute coupling关系，或者称为属性内耦合关系。研究B1和B2之间的关系时也要考虑a1和a3属性对它的影响，就是inter-attribute coupling即属性间耦合关系。

表达这些概念需要建立信息函数（information function），从表中将信息提取出来。f函数和f*函数用于提取给定对象在某属性上的值的信息，g函数和g*函数用于提取给定属性值的对象的信息。这样会形成很多集合，集合之间具有关系。

如图，根据信息函数f*可以知道u1、u2、u3三个对象在a2属性上的值是B1、B2，其中B1可能出现多次，所以不仅要确定这个值，还要考虑它多次出现的情况。通过函数g确定a2属性值为B1时有对象u1、u2。给定多个值时，g*函数将所有对象找出。

进一步考虑一个属性上的值之间的关系如何建模。参考公式4.1，考虑两方面，一方面是

，表达x、y两个值在j属性上的相似度。另一方面也要考虑j属性上x、y的相似度受到其他属性的影响，多个属性的影响叠加得到

。两方面结合才能反映属性值x、y在这个信息表中可能的相似性。考虑对象间的相似性，需要将所有属性的相似性叠加得到对象间的耦合属性的相似性度量CASO（Coupled Attribute Similarity for Objects），进一步也可以得到对象间的耦合属性的相异性度量CADO（Coupled Attribute Dissimilarity for Objects）。

上述相似性度量可以灌入像K-Modes的聚类算法中对这些算法进行改进与更好地捕获数据中存在的层次化的耦合关系。比如，在UCI数据集上用RD、DI、DBI、SD等聚类算法评价指标将我们的相似性度量CADO和常用的SMD、OFD、ADD等方法进行比较，可以看出在一些数据集上我们的方法有明显优势，而在比较简单的数据集上相差不大。

Data structureindex comparison

用CADO对K-Modes或谱聚类等聚类方法进行改造，在UCI数据集进行实验比较，可以看到效果有所提升。这里考虑的不是big data，而是考虑如何体现small data中的复杂性，即使数据很小，里面可能还存在复杂的关系，学习起来也可能比较复杂。

Clustering evaluation on six data sets

这一节的方法主要是基于”pairwise”这种简单与常见的关系学习模式进行举例，还可以参考近些年提出的许多其它的耦合学习方法。两个值在同一维里的相似性要算出来，受到其他各维的影响也要算出来，再进行整合；如果计算两个对象的相似性还要遍历叠加所有的属性内与属性间的耦合。这种思想近些年在学习与应用上有很多的进展，比如被应用到KNN、K-Means，在关键词检索、文本分析、图像分析、推荐系统、表示学习、深度学习中也有应用，有兴趣的可参考KDD2017的Non-IID Learning tutorial,以及在www.datasciences.org找到相关文章。

Non-IID Outlier Detection

● Learning Feature Couplings for Outlier Detection【5】

无监督情况下进行异常检测比较经典的方法是pattern-based，基本假设是正常对象是相似的，异常也比较相似，但正常和异常的行为实际上可能差别较大。Pattern-based方法的基本框架如下图。

判断异常时首先找到异常的pattern或subspace，也就是异常特征，一般认为发生频率极低的可能是异常。根据这些特征构建模型，来判断输入数据是否为异常。这个方法的缺点是当数据比较复杂时虚警率很高。

一个新的思路是，特征输入后先分析一个特征内的值之间的关系，针对异常检测设计或者学习信息函数，将一个特征内的值之间的关系（尤其是异常性）刻画出来。对不同特征的值之间与异常有关的关系也要建立信息函数。这两套信息函数构建后，可以对每一个值给出异常程度的度量，来判断值是否异常。进一步，得到多个维上的值的异常度后，经过叠加可以得到每个对象的异常度，来判断每个对象是否异常。

这种思想也可用于特征选择。分析每一个特征内的值的异常程度与最后异常标签的关系，如果比较敏感，就将这个特征放入建模与学习中；如果不太敏感，这个特征就可以丢掉。

对于有噪声的特征，通常认为与异常是有差异的，判别性不强，所以构建信息函数时要能够剔除噪声特征，找出真正对异常检测敏感的特征并刻画它们的关系。

理解数据特点和复杂性是数据分析的重要问题，一个思路是设计或者学习数据要素(Data Factor)，针对数据要素可以定义、计算、度量它的一些指标。上表是在一些数据中的实验结果，N是数据量，D是特征数，Knoise和Kmode就是两个数据要素，用来衡量数据的复杂性。Knoise衡量数据的噪声程度，Kmode反映mode的分布。

我们的方法是CBRW (Coupled Biased Random Walk)，FPOF是pattern-based方法，COMP是基于信息的方法，MarP是基于概率的，可以看到CBRW在一些复杂数据上的效果更好。

进一步做特征选择。从上图可以看到很多方法加上CBRW特征选择后，AUC明显提升。

CBRW的另一个好处是计算复杂度低，基本上是近线性，处理量大或维数高的数据有明显优势。

● Hierarchical Feature Couplings for Outlier Detection【6】

有时正常和异常对象非常不对称，并且因为噪声较多，异常对象会被误认为是带有噪声特征的正常对象，为应对这种情况我们提出基于HierarchicalFeature Couplings的异常检测方法。

输入数据后，通过学习value之间的关系，在无监督情况下计算每个value的异常性（outlierness），建立Value Graph。通过value还可以计算特征的异常性，构建Feature Graph。之后根据特征的贡献度筛选出特征子集，选出真正适合异常检测的特征。

这个方法是考虑单个value之间的关系。我们IJCAI2017发表的一个新工作是考虑value本身的耦合性，加一层Value Cluster。通过Value Cluster和异常性来判断哪些value和特征是需要的。这里面也涉及到另外一些信息函数【7】。

Non-IID Recommendation

现有的一些推荐系统会出现重复推荐、错误推荐等问题，下面从Non-IID角度来探讨非独立同分布的推荐系统（non-IID recommender systems）的概念与方法【8】。

通常推荐系统会用到三张表：(A)Ratings表，用户对产品打分，(B)表包含用户的属性，还包括朋友、同学等关系，(C) 表是关于产品信息。在此基础上有很多推荐方法，比如Content-Based推荐、Cross-Domain推荐、Group-Based推荐等。(D)表目前研究较少，主要反映(B)表中的用户信息与(C)表中的产品信息间的关系，可能是显示或者是隐式的关系，其中每一项都是复杂的数据结构或关系。此外，推荐算法还应当考虑环境因素的影响，即表(E)中的信息以及与其它表的交互。以上每一个表都具有非独立同分布性。

推荐系统一个当前的重点与难点是个性化推荐的研究，其难点或核心是要考虑如何将(D)表中复杂的内容和Ratings表结合，并充分捕获 (B)表和(C)表中的复杂性。

推荐系统方法中一个最经典的方法例子是矩阵分解（Matrix Factorization）。

如图，矩阵分解解决的问题就是如何估计Rating表R中空白项的分值。基本思路是将表R分解成两个矩阵的乘积，如图中右上方公式所示，然后构建目标函数，使估计出的R尽量逼近实际的R，将物理问题转化为数学问题。

矩阵分解中要考虑用户和产品的非独立同分布性。上图左侧是用户的各种属性，右侧是产品的各种属性。可以用”pairwise”方法，把一维上值之间的关系学出来，不同维之间的耦合交互关系学出来，再研究两个用户或产品之间的关系。将这些关系学出来后就可以改进矩阵分解，我们据此提出了耦合矩阵分解CMF（Coupled Matrix Factorization）方法。

在一些数据集上进行实验，可以看到CMF方法相比于其他经典方法改进非常大。

Conclusion

对于比较实际的或者复杂的数据与学习问题，要考虑到数据的属性、属性值、对象等可能存在多种类型、层次、粒度等异构性与耦合关系。即非独立同分布性。非独立同分布学习的过程比较复杂，需要不断优化，还需要分层次，比如先分析一个特征，然后多个特征叠加，再到各个对象。相比经典的独立同分布学习，非独立同分布学习问题可以用下图进行概括：

对学习问题，采用右侧上方的方法考虑问题与数据的复杂性就是独立同分布，按下方的方法考虑就是向非独立同分布Non-IID方向发展。非独立同分布性还有很多问题需要深入研究，非独立同分布学习需要研究的问题与空间就更大，在信号处理、图像处理、网络分析、非结构化数据、多源异构数据等几乎所有的学习问题与数据领域都有这样的问题。目前相关的研究刚刚起步，非独立同分布学习特别是结合大数据分析、企业数据分析等应用中可能是不可回避的数据科学基本问题之一，很多问题需要不断深入思考。

Non-IID Learning: A Significant Area

比如，关于非独立同分布性，还可以从很多角度不断深入，比如Non-IIDness可能体现在Entity、Property、Interaction、Learning、Context等多方面，每方面还可以再深入，需要在理论上做更多探讨。

Aspects of Non-IIDness

层次上，非独立同分布性Non-IIDness与非独立同分布学习的研究可以从属性值到属性，再到对象，一直到多个方法、多个度量以致学习结果等加以考虑。

HierarchicalNon-IIDness

参考资源

【1】关于非独立同分布学习Non-IID Learning的相关文章、代码、tutorial slides可以从

www.datasciences.org上找到。

【2】Cao, L.: Non-iidness learning in behavioral and social data. The Computer Journal 57(9), 1358–1370 (2014)

【3】Cao, L.: Coupling learning of complex interactions. J. Information Processing and Management, 51(2), 167–186 (2015)

【4】Wang, C., Dong, X., Zhou, F., Cao, L., Chi, C.H.: Coupled attribute similarity learning on categorical data. IEEE Trans. Neural Netw. Learning Syst. 26(4), 781–797 (2015)

【5】Pang, G., Cao, L., Chen, L.: Outlier detection incomplex categorical data by modelling the feature value couplings. In: IJCAI2016, pp. 1–7 (2016)

【6】Guansong Pang, Longbing Cao, Ling Cheny and Huan Liu. Learning Homophily Couplings from Non-IID Data for Joint Feature Selection and Noise-ResilientOutlier Detection. IJCAI2017.

【7】Songlei Jian,Longbing Cao, Guansong Pang, Kai Lu, Hang Gao. Embedding-based Representationof Categorical Data by Hierarchical Value Coupling Learning. IJCAI2017.

【8】Longbing Cao.Non-IID Recommender Systems: A Review and Framework of Recommendation Paradigm Shifting. Engineering, 2: 212-224, 2016.