浅析互信息与特征选择

转自: 业余机器学习与深度学习

基础知识


正文:

特征选择有很多方法,其中一种是基于互信息的。

那么什么是互信息呢?变量x与变量y之间的互信息,可以用来衡量已知变量x时变量y的不确定性减少的程度,同样的,也可以衡量已知变量y时变量x的不确定性减少的程度。

互信息是基于熵而得到的。什么是熵呢?一个随机变量的熵是用来衡量它的不确定性的。比如,对于变量y,熵的计算公式如下

当变量y是离散变量时,则累加即可,而当变量y是连续变量时,则需要通过积分方法来计算。其实,熵可以解释为表示变量y所需二进制位的平均值。

假设离散变量y的取值空间为Ω = {0,1},并且 P [y=1] = p, P [Y=0] = 1-p,则熵随p的变化曲线如下:

其中

容易看出,两件事发生的概率相等时,变量y的不确定性最大。

接下来看看条件熵。条件熵 H(y |x ) 用来衡量变量x给定时,变量y的不确定性。公式如下:

H(y | x) = H(y, x) − H(x)

如果变量y和变量x是相互独立的,即 H(y | x) = H(y)。 这种情况下,不论变量x是否已知,变量y的不确定性都一样。

既然已经了解了熵,下面来看下互信息。变量x和y之间的互信息即为:

I(y;x) = H(y) − H(y | x) = H(x) − H(x | y)

它是两个熵之间的差,即变量y的熵减去给定变量x时变量y的熵。互信息具有以下特性:

1. 如果x和y是相互独立的,则 I(y;x) = 0;

2. I(y;y) = H(y);

3. 互信息I(y;x)通常是非负的,并且小于 min(H(y), H(x))。

互信息可以识别出变量之间的非线性关系。比如变量x, y ,z满足以下条件时:

1 变量 x 服从均匀分布 [-1 1] 2 变量 y = x^2 + noise 3 变量 z 服从均匀分布 [-1 1]

4 变量 z 和 变量 x 相互独立。

互信息和相关系数的计算结果如下:

其中Correlation是相关系数。

注意到互信息公式是

I(x,y) = H(y) − H(y | x) = H(x) − H(x | y)

其中的x和y有可能是向量。针对这种情形如何计算互信息呢?首先来看几个概念。

关联度

上述定义给出了,给定x1时,x2相对y的关联度即为条件互信息。

冗余度

上述定义给出了两个变量互相冗余的定义。

上面定义给出了强相关的定义。强相关意味着这个变量在最优特征子集中通常是必须有的。

上面定义给出了弱相关的定义。弱相关性表明该特征不一定是必须的,但是在某些条件下可能是必须的。

如果某个特征既不是弱相关,又不是强相关,则该特征是没有必要的。

可以得到

进而可以得到

如果上面的交互项是正的,则这两个变量是互补的。如果变量是相互冗余的,则交互项是负值。

说了这么多,互信息跟特征选择到底什么关系呢?给定输出目标 y 和输入变量集合 X = {x1, . . . , xn} ,选择最佳的特征子集可以描述为下述优化问题:

上述问题可以用增量法来解决。即首先令 X = {xi}, i = 1, . . . , n,并且 XS 是当前已选变量构成的集合。添加变量 x∗ ∈ S − X 的过程可以有下面方法解决

这是一个最大依赖性(maximal dependency)问题,需要估计多变量的互信息。

最后介绍一种常用基于互信息的特征选择方法,即为mRMR(mimimum-Redundancy Maximum-Relevancy),最小冗余最大相关法,这种方法对应的特征选择策略利用

来近似下式

参考资料:

1. http://www.ulb.ac.be/di/map/gbonte/bioinfo/course4.pdf

2. http://www.cost-ic0702.org/summercourse/files/feature_selection.pdf

3. Peng, Hanchuan, Fuhui Long, and Chris Ding. "Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy." IEEE Transactions on pattern analysis and machine intelligence 27.8 (2005): 1226-1238.

4. Zaffalon, Marco, and Marcus Hutter. "Robust feature selection by mutual information distributions." Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., 2002.

5. Guo, Baofeng, and Mark S. Nixon. "Gait feature subset selection by mutual information." IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 39.1 (2009): 36-46.

本文由zdx3578推荐。

原文发布于微信公众号 - CreateAMind(createamind)

原文发表时间:2016-11-11

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

手把手教你用 Keras 实现 LSTM 预测英语单词发音

我近期在研究一个 NLP 项目,根据项目的要求,需要能够通过设计算法和模型处理单词的音节 (Syllables),并对那些没有在词典中出现的单词找到其在词典中对...

922
来自专栏机器学习算法工程师

机器翻译不可不知的Seq2Seq模型

Seq2Seq,全称Sequence to Sequence。它是一种通用的编码器——解码器框架,可用于机器翻译、文本摘要、会话建模、图...

2043
来自专栏人工智能头条

实战 | 手把手教你搭一个机器翻译模型

5377
来自专栏计算机视觉战队

简单易懂的讲解深度学习(入门系列之五)

我们知道,《三字经》里开篇第一句就是:“人之初,性本善”。那么对于神经网络来说,这句话就要改为:“网之初,感知机”。感知机( Perceptrons ),基本上...

971
来自专栏AI研习社

我们分析了最流行的歌词,教你用 RNN 写词编曲(附代码)

翻译 | 余若男 李振 吴章勇 整理 | 凡江 此文展示了基于 RNN 的生成模型在歌词和钢琴音乐上的应用。 介绍 在这篇博文中,我们将在歌词数据...

3364
来自专栏深度学习与数据挖掘实战

【今日热门&优质资源】深度学习经典论文&详解深度学习最热门的RNN网络

1122
来自专栏专知

【ACL2018】什么都能GAN,无监督神经网络翻译新方法

2562
来自专栏AI研习社

手把手教你用 PyTorch 辨别自然语言(附代码)

最近在学pyTorch的实际应用例子。这次说个简单的例子:给定一句话,判断是什么语言。这个例子是比如给定一句话: Give it to me 判断是 ENGLI...

3645
来自专栏机器之心

你可能不再需要Attention:这是一个贼简单的神经机器翻译架构

自从编码器解码器架构崛起以来,主流的神经机器翻译(NMT)模型都使用这种架构,因为它允许原文序列长度和译文序列长度不一样。而自 Bahdanau 等研究者在 1...

863
来自专栏AI科技评论

开发|简单有趣的 NLP 教程:手把手教你用 PyTorch 辨别自然语言(附代码)

最近在学pyTorch的实际应用例子。这次说个简单的例子:给定一句话,判断是什么语言。这个例子是比如给定一句话: Give it to me 判断是 ENGLI...

3127

扫码关注云+社区

领取腾讯云代金券