江苏龙网

  1. 首页 > 资讯 > 科技 > >

【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论( 二 )


什么是计算约束呢？首先见下面我们对条件 V-熵（conditional V-entropy）的定义（其中我们省去了不重要的预测族（predictive family）的定义 ， 它本质上是加了些正则条件 ， 感兴趣的小伙伴可以看下原 paper）：
定义（条件 V-熵）：X, Y 是两个取值在 X, Y 的随机变量 ， V ? Ω 是一个预测族 ， 则条件 V-熵的定义为：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

计算约束体现在观测者被限制为 V ? Ω ， 即取全集 Ω 的一个子集合 V 。 由于 V ? Ω ， 因此定义中的 f[x] 是一个概率测度 ， f[x](y) 是该概率测度（如概率密度函数）在 y 处的取值 。
直观地来看 ， 条件 V-熵是在观测到额外信息 X 的情况下 ， 仅利用函数族 V 中的函数 ， 去预测 Y 可以取到的期望下最小的负对数似然（negative log-likelihood） 。 同理定义 V-熵 ， 也就是没有观测到额外信息（用 ? 表示）的情况下 ， 利用 V 中的函数去预测 Y 可以取到的期望下最小的负对数似然 。
下面我们展示 ， 通过取不同的函数族 V ， 许多对不确定性的度量（如方差、平均绝对离差、熵）是 V-熵的特例：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

接着类似于香农互信息的定义 ， 我们利用 V-熵来定义 V-信息：
定义（V-信息）：X, Y 是两个取值在 X, Y 的随机变量 ， V ? Ω 是一个预测族 ， 则 V-信息的定义为：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

即从 X 到 Y 的 V-信息是 Y 的 V-熵在有考虑额外信息 X 的情况下的减少量 。 我们也证明了决定系数、香农互信息均为 V-信息在取不同函数族 V 下的特例 。 我们还证明了 V-信息的一些性质 ， 比如单调性（取更大的函数族 V ， V-信息也随之增大） ， 非负性与独立性（X, Y 独立则 V-信息为 0） 。
此外我们展示 ， 通过显示地考虑计算约束 ， 在 V-信息的框架下 ， 计算可以增加 V-信息 ， 即增加对观测者而言的有用信息：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

同时 ， 注意到 V-信息是非对称的 ， 它可以很自然地用到一些因果发现或者密码学（如 one-way function）的场景中 。
对 V-信息的估计
不同于香农互信息 ， 在对函数族 V 的一些假设下 ， 本文证明了 V-信息在有限样本上的估计误差是有 PAC 界的：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

这个 PAC 界启发我们将 V-信息用于一些使用香农互信息的结构学习的算法中 。 我们发现这些之前在有限样本上没有保证的算法 ， 迁移到 V-信息下就有了保证 。 比如 Chow-Liu 算法就是一例：
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

本文通过实验验证了新的基于 V-信息的算法构建 Chow-Liu Tree 的效果 ， 优于利用现存最好的互信息估计量的 Chow-Liu 算法 。
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

更多的实验
我们也将 V-信息用到了其他结构学习的任务中 ， 如基因网络重建（下左图）和因果推断（下右图） 。
【机器之心】北大图灵班本科生满分论文：计算约束下有用信息的信息论
本文插图

注意到与一些非参数化的估计量（如 KSG, Partitioning 等）相比 ， 我们的方法在低维基因网络的重建中取得了更好的效果 。 同时我们的方法在因果推断的实验中正确地重建了时序序列 。 在确定性的时序轨迹（deterministic dynamics）下 ， 香农互信息是无法重建时序序列的 。


推荐阅读


上一篇：「新能源汽车」首家动力电池回收平台上线，新能源车残值有救了？

下一篇：#新能源汽车#2819个新能源汽车充电桩今年落地北京，覆盖这些地方