首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
【24h】

Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions

机译:鲍姆算法学习对数凹面分布的半空间相交

获取原文
获取原文并翻译 | 示例

摘要

In 1990, E. Baum gave an elegant polynomial-time algorithm for learning the intersection of two origin-centered halfspaces with respect to any symmetric distribution (i.e., any D such that D(E) = D(-E)) [3]. Here we prove that his algorithm also succeeds with respect to any mean zero distribution D with a log-concave density (a broad class of distributions that need not be symmetric). As far as we are aware, prior to this work, it was not known how to efficiently learn any class of intersections of halfspaces with respect to log-concave distributions.rnThe key to our proof is a "Brunn-Minkowski" inequality for log-concave densities that may be of independent interest.
机译:1990年,E。Baum提出了一种优雅的多项式时间算法,用于学习两个以原点为中心的半空间相对于任何对称分布(即,任何D使得D(E)= D(-E))的交集[3]。 。在这里,我们证明了他的算法对于具有对数凹面密度(不需要对称的各种分布)的平均零分布D也是成功的。据我们所知,在进行这项工作之前,还不知道如何有效地学习关于对数凹面分布的任何类的半空间交集。rn我们证明的关键是对数凹面的“ Brunn-Minkowski”不等式可能具有独立利益的凹密度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号