Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selecti

本文主要是介绍Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selecti,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1、文章信息
  • 2、主要思想
    • 2.1信息熵:
    • 2.2 基于互信息的滤波算法

1、文章信息

Title: Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection

Author: Gavin Brown, Adam Pocock, Ming-Jie Zhao, Mike Lujan

Affiliation: School of Computer Science, University of Mancheste

Abstract: 首先提出一个通用的基于信息论的特征选择算法框架。将近20年的启发式Filter算法统一起来。这种方式回答了:基于互信息的特征选择算法的隐含统计学假设是什么。为了回答这些问题,不同于以前特征选择的文献,我们采用了不同的策略。传统的特征选择方法一般都是定义评价标准,但是我们从训练标签的条件可能性推导出评价标准。然而许多手工设计的启发式评价标准以优化特征的相关性和冗余性为宗旨,我们的方法采用概率的框架,很自然的与上述的思想保持一致。结果我们将多种近20年已经发表的评价标准进行统一,并且以低阶近似的方式来显示他们。主要贡献是定义了一个通用的基于信息论的启发式特征选择方法(将马尔可夫毯作为一个特殊的例子)。通过大量的实证研究提供了充分的证据。总之,我们可以得出结论JMI算法在准确度、稳定性及小数据量的灵活度方面提供了最好的折衷。

2、主要思想

首先对信息熵相关概念进行介绍:

2.1信息熵:

信息熵
H ( X ) = − ∑ x ∈ X p ( x ) log ⁡ p ( x ) H(X)=-\sum_{x\in X}p(x)\log p(x) H(X)=xXp(x)logp(x)
可以将信息熵看成是 log ⁡ ( 1 p ( x ) ) \log(\frac{1}{p(x)}) log(p(x)1)的期望值。
E ( log ⁡ 1 p ( X ) ) = ∑ x ∈ X p ( x ) log ⁡ ( 1 p ( x ) ) E(\log\frac{1}{p(X)})=\sum_{x\in X}p(x)\log(\frac{1}{p(x)}) E(logp(X)1)=xXp(x)log(p(x)1)
对于离散变量X,我们可以通过变量x出现的次数除以总数量来估计p(x). p ^ = # n N \hat p= \frac{\#n}{N} p^=N#n
联合熵
( X , Y ) = − ∑ x ∈ X ∑ y ∈ Y p ( x , y ) log ⁡ ( p ( x , y ) (X,Y)=-\sum_{x\in X}\sum_{y\in Y}p(x,y)\log(p(x,y) (X,Y)=xXyYp(x,y)log(p(x,y)
上式亦可表达为联合随机变量-log(p(X,Y))的期望值:
H ( X , Y ) = − E log ⁡ p ( X , Y ) = − ∑ x ∈ X ∑ y ∈ Y p ( x , y ) log ⁡ ( p ( x , y ) H(X,Y)=-E\log p(X,Y)=-\sum_{x\in X}\sum_{y\in Y}p(x,y)\log(p(x,y) H(X,Y)=Elogp(X,Y)=xXyYp(x,y)log(p(x,y)
用文氏图表达联合如图所示,由图可看出联合熵为 H ( X ) H(X) H(X) H ( Y ) H(Y) H(Y)的并。
联合熵文氏图
条件熵
H ( X ∣ Y ) = − ∑ y ∈ Y p ( y ) ∑ x ∈ X p ( x ∣ y ) log ⁡ p ( x ∣ y ) H(X|Y)=-\sum_{y\in Y}p(y)\sum_{x\in X}p(x|y)\log p(x|y) H(XY)=yYp(y)xXp(xy)logp(xy)
同理上式可以表示为期望的形式:
H ( X ∣ Y ) = − ∑ y ∈ Y p ( y ) ∑ x ∈ X p ( x ∣ y ) log ⁡ p ( x ∣ y ) = − ∑ x ∈ X ∑ y ∈ Y p ( x , y ) log ⁡ p ( y ∣ x ) = − E log ⁡ p ( X ∣ Y ) H(X|Y)=-\sum_{y\in Y}p(y)\sum_{x\in X}p(x|y)\log p(x|y)=-\sum_{x\in X}\sum_{y\in Y}p(x,y)\log p(y|x)=-E\log p(X|Y) H(XY)=yYp(y)xXp(xy)logp(xy)=xXyYp(x,y)logp(yx)=Elogp(XY)
用文氏图表示条件互信息如下,条件互信息可以理解为在Y已知的情况下X仍旧存在的不确定性。
在这里插入图片描述
互信息
互信息的定义:考虑两个随机变量X和Y,他们的联合概率密度函数为 p ( x , y ) p(x,y) p(x,y),其编辑概率密度函数分别为 p ( x ) p(x) p(x) p ( y ) p(y) p(y)。互信息 I ( X ; Y ) I(X;Y) I(X;Y)为联合分布 p ( x , y ) p(x,y) p(x,y) p ( x ) p ( y ) p(x)p(y) p(x)p(y)之间的相对熵。
I ( X ; Y ) = D ( p ( x , y ) ∣ ∣ p ( x ) p ( y ) ) = ∑ x ∈ X ∑ y ∈ Y p ( x , y ) log ⁡ p ( x , y ) p ( x ) p ( y ) I(X;Y)=D(p(x,y)||p(x)p(y))=\sum_{x\in X}\sum_{y\in Y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)} I(X;Y)=D(p(x,y)p(x)p(y))=xXyYp(x,y)logp(x)p(y)p(x,y)
其物理意义可以理解为度量X和Y的共享信息:它度量指导其中一个变量Y时,对X的不确定性的减少程度。如果X和Y完全独立,则知道Y对X的不确定性不产生任何影响,所以他们的互信息为0.( p ( x , y p ( x ) p ( y ) = 1 \frac{p(x,y}{p(x)p(y)}=1 p(x)p(y)p(x,y=1
另外一种极端情况为X 是 Y 的一个确定性函数,且 Y 也是 X 的一个确定性函数,那么传递的所有信息被 X 和 Y 共享:知道 X 决定 Y 的值,反之亦然。因此,在此情形互信息与 Y(或 X)单独包含的不确定度相同,称作 Y(或 X)的熵。而且,这个互信息与 X 的熵和 Y 的熵相同。即: I ( X ; Y ) = I ( X ; X ) = H ( X ) I(X;Y)=I(X;X)=H(X) I(X;Y)=I(X;X)=H(X)

采用文氏图对互信息进行标识:
在这里插入图片描述
由图可以得到相关的公式:
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ I(X;Y)=H(X)-H(…

条件互信息
I ( X ; Y ∣ Z ) = H ( X ∣ Z ) − H ( X ∣ Y Z ) = ∑ z ∈ Z p ( z ) ∑ x ∈ X ∑ y ∈ Υ p ( x y ∣ z ) l o g p ( x y ∣ z ) p ( x ∣ z ) p ( y ∣ z ) I(X;Y|Z)=H(X|Z)-H(X|YZ) =\sum_{z\in\Zeta}p(z)\sum_{x\in\Chi}\sum_{y\in\Upsilon}p(xy|z)log\frac{p(xy|z)}{p(x|z)p(y|z)} I(X;YZ)=H(XZ)H(XYZ)=zZp(z)xXyΥp(xyz)logp(xz)p(yz)p(xyz)
条件互信息的文氏图如图所示:
在这里插入图片描述
I(X;Y|Z)可以理解为集合H(X)和集合H(Y)的共同部分然后删除掉与集合Z的重合部分。
H ( X ) ⋂ H ( Y ) − H ( Z ) H(X)\bigcap H(Y)-H(Z) H(X)H(Y)H(Z)

:在信息熵中注意逗号“,”分号“;”与"|“的作用。逗号代表 ⋃ \bigcup ,分号代表 ⋂ \bigcap ,而”|"代表减的关系。
例如:
H(X,Y)代表 H ( X ) ⋃ H ( Y ) H(X)\bigcup H(Y) H(X)H(Y),H(X|Y)代表在H(X)中去除掉H(X)与H(Y)重合的部分I(X;Y)。
I(X;Y)代表集合H(X)与集合H(Y)的重合部分,I(X;Y|Z)代表H(X)与H(Y)的重合部分减去与H(Z)重合的部分,I(X;Y,Z)代表H(X)与H(Y)的重合部分加上与H(Z)重合的部分。

2.2 基于互信息的滤波算法

滤波算法一般定义一个评价标准J,用来衡量一个特征或者特征子集对于分类的有用程度。从直觉上来看,J应该是衡量特征与分类标签的的相关性,特征与分类之间的相关性越强,表示特征的预测能力更佳。对于标签Y, X k X_k Xk的互信息评价标准为
J m i m ( X k ) = I ( X k ; Y ) J_{mim}(X_k)=I(X_k;Y) Jmim(Xk)=I(Xk;Y)
分别考虑每个特征与标签之间的互信息的方式称为MIM(Mutual Information Maximisation)。
这种方式简单的将每个特征的互信息值进行排序,然后选取前K个作为选取的特征,其中K是事先定义好的选取特征的数量或者其他的停止标准。这种方式的局限之处在于其假设每个特征与其他所有的特征都是独立的。但是有些时候特征之间是相互依赖的,这样就导致不能得到最优结果。通常一个最优的特征子集不仅要求相关性,而且要求特征之间不相互冗余(特征之间不相关)。这种方式看起来很直观但是从严格意义上讲并不正确,这在后文当中会有介绍。基于此,相关但不冗余的方式被提了出来。例如Battiti(1994)提出了MIFS(Mutual Information Feature Selection)的评价标准为:
J m i f s ( X k ) = I ( X k ; Y ) − β ∑ X j ∈ S I ( X k ; X j ) J_{mifs}(X_k)=I(X_k;Y)-\beta \sum_{X_j\in S}I(X_k;X_j) Jmifs(Xk)=I(Xk;Y)βXjSI(Xk;Xj)
这里 S S S是目前选择的特征。其中 I ( X k ; Y ) I(X_k;Y) I(Xk;Y)项确保特征的相关性,并且增加了一个与S中相关的一个惩罚项。注意,该方法假设我们顺序的选择特征,通过迭代的方式得到最终的特征子集。如果需要调研其他顺序的特征选择算法,读者可以参考Duch(2006)的文章。MIFS中的 β \beta β是一个可配置的参数,一般通过实验来获得。当 β = 0 \beta=0 β=0时,此方法等价于MIM方法,独立的选择特征,然而当 β \beta β增加时,则更强调特征之间的相关性。在实验中Battiti发现当 β = 1 \beta=1 β=1时时最优的,但是却没有理论依据。Yang and Moody(1999)和后来的Meyer et al.(2008)采用JMI(Joint Mutual Information),将注意力放在特征之间的逐渐增加的互补信息。其公式如下:
J j m i ( X k ) = ∑ X j ∈ S I ( X k X j ; Y ) J_{jmi}(X_k)=\sum_{X_j\in S}I(X_kX_j;Y) Jjmi(Xk)=XjSI(XkXj;Y)
定义了目标Y与 X k X j X_kX_j XkXj之间的互信息,将待评价特征 X k X_k Xk与之前选择的特征分别进行联合。其主要思想是待选择特征是否与已经选择的特征具有互补性,如果有则选择。
MIFS和JMI方法是众多评价标准中最早进行相关性与冗余性进行折衷的方式,然后很明显他们有不同的出发点。下标总结了1992-2011年的特征选择方法。特征选择问题之前一直是手工设计的标准,然后用信息论的方法来修补评价标准,总体的目标就是做好相关性与冗余性的折衷,每一种评价标准都有不同的方向。但是下面有几个问题:我们该相信哪种方式?他们对数据有哪些假设?还有没有没有被发现的有效的方法?下面的章节我们将会针对以上问题提供一个全新的视角。

CriterionFull NameAuthors
MIMMutual Information MaximisationLewis(1992)
MIFSMutual Information Feature SelectionBattiti(1994)
KSKoller-Sahami metricKoller and Sahami(1996)
JMIJoint Mutual InformationYang and Moody(1999)
MIFS-UMIFS-UniformKwak and Choi(2002)
IFInformative FragmentsVidal-Naquet and Ullman (2003)
FCBFFast Correlation Based FilterYu and Liu(2004)
AMIFSAdaptive MIFSTesmer and Estevez (2004)
CMIMConditional Mutual Info MaxFleuret (2004)
MRMRMax-Relevance Min-RedundancyPeng et al. (2005)
ICAPInteraction CappingJakulin (2005)
CIFEConditional Infomax Feature ExtractionLin and Tang (2006)
DISRDouble Input Symmetrical RelevanceMeyer and Bontempi (2006)
MINREDMinimum RedundancyDuch (2006)
IGFSInteraction Gain Feature SelectionEl Akadi et al. (2008)
SOASecond Order ApproximationGuo and Nixon (2009)
CMIFSConditional MIFSCheng et al. (2011)

这篇关于Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selecti的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/808958

相关文章

Spring Framework系统框架

序号表示的是学习顺序 IoC(控制反转)/DI(依赖注入): ioc:思想上是控制反转,spring提供了一个容器,称为IOC容器,用它来充当IOC思想中的外部。 我的理解就是spring把这些对象集中管理,放在容器中,这个容器就叫Ioc这些对象统称为Bean 用对象的时候不用new,直接外部提供(bean) 当外部的对象有关系的时候,IOC给它俩绑好(DI) DI和IO

计算机视觉中,什么是上下文信息(contextual information)?

在计算机视觉中,上下文信息(contextual information)是指一个像素或一个小区域周围的环境或背景信息,它帮助模型理解图像中对象的相对位置、大小、形状,以及与其他对象的关系。上下文信息在图像中提供了全局的语义和结构线索,使模型不仅依赖局部细节,而且能够考虑整个场景或图像的大局。 上下文信息的具体含义 局部与全局信息的结合: 局部信息:这是指某个小区域或某个像素点的特征。通过小

【机器学习 sklearn】特征筛选feature_selection

特征筛选更加侧重于寻找那些对模型的性能提升较大的少量特征。 继续沿用Titannic数据集,这次试图通过特征刷选来寻找最佳的特征组合,并且达到提高预测准确性的目标。 #coding:utf-8from __future__ import divisionimport sysreload(sys)sys.setdefaultencoding('utf-8')import timest

Maximum likelihood function maximizes what thing?

最大似然函数(Maximum Likelihood Function)最大化的是数据在给定参数下出现的概率。具体来说,它最大化的是似然函数(Likelihood Function),即给定参数 ( \theta ) 下观测数据的概率。在统计学中,似然函数 ( L(\theta) ) 通常定义为所有独立观测数据点概率的乘积,对于参数 ( \theta ) 的函数。 对于一组独立同分布的观测数据

feature_column相关接口

在TensorFlow中,特征列(Feature column)是原始数据和 Estimator 之间的接口,它告诉Estimator如何使用数据。 原始数据集包含各种各样的特征,有的特征是数值,比如年龄,长度、速度;有的特征是文字,比如,地址、Email内容、数据库查询语句等 神经网络接受的输入,只能是数值,而且是整理好的数值 所以,原始数据 和 神经网络输入需求之间需要一个桥梁,这个

安卓aosp14上自由窗口划线边框Freeform Caption实战开发-千里马framework实战

背景: 上一篇文章也分享过aosp14版本上自由窗口的Caption栏的显示原理,今天来讲解一下aosp14版本上如何实现对自由窗口的划线边框功能,相关功能已经在aosp13上面进行实现,具体可以看我的分屏自由窗口专题哈。 就是想要在aosp14上面实现如下功能: 即自由窗口在被触摸放大缩小时候,边框要被画成红色的线条,表示选中。 尝试aosp13老方案: 因为aosp13是在acti

Detection简记2-DAFE-FD: Density Aware Feature Enrichment for Face Detection

创新点 1.使用密度估计模型增强检测中的特征图 总结 整个流程还是很清晰的。 conv1-3的特征图经过密度估计模块由检测器D1进行检测。 D2-4分别是四个检测器。 FFM是特征融合模块,将不同层不同大小的特征融合。 FFM网络结构如下: 首先使用1X1的卷积减少两组特征的厚度到128,然后使用双线性插值统一两组特征图的尺寸,然后相加。类似于cvpr2017的SSH。 多尺度检测器的网

Android Framework中的PolicyManager简介

PolicyManager类位于framework\base\core\java\com\android\internal\policy目录中的PolicyManager.java文件中。PolicyManager主要用于创建Window类、LayoutInflater类和WindowManagerPolicy类,它扮演着简单工厂模式中的工厂类角色,而抽象产品角色由IPolicy接口实现,具体产

rust feature 简介

Rust 的 feature 是一种机制,用于在编译时选择性地启用或禁用代码的某些部分。通过 feature,你可以在 Cargo.toml 中定义哪些功能需要启用,并在代码中通过条件编译来控制代码的编译与否。下面是 feature 机制的详解: 1. 基本概念 Feature: 是一个编译时的标志,允许你有选择性地启用某些代码路径、依赖项或编译选项。Default Feature: 默认启用

知识图谱(knowledge graph)——RDF(Resource Description Framework)

RDF的基本单元是三元组(triple) 每个三元组是(主语 谓语 宾语) 这样的元组tuple。主谓宾的取值称为"资源"(Resource, 也就是RDF里的R) 资源可以是一个网址(URI),一个字符串或数 字(严格来讲都是带类型的字符串,称为 literal),或者一个“空节点”(blank node)。 有两种特殊类型的资源。rdfs:Class代表类。 rdf:Property代