Learning from Partial Observations
Learning from Partial Observations
复制标题
从部分观察中学习
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Loizos Michael
中科院分区：
文献类型：
--
作者：
Loizos Michael
我们提出了一个通用的机器学习框架，用于对数据中缺失信息的现象进行建模。我们提出了一个掩蔽过程模型来捕捉信息丢失的随机性。在这种情况下，学习是作为一种手段，以恢复尽可能多的丢失的信息是可恢复的。我们扩展了可能近似正确的语义学习的情况下，从部分观察任意隐藏的属性。我们建立，简单地要求学习的假设与观测值相一致，足以保证隐藏的值可以恢复到一定的精度;我们还表明，在某种意义上，这是实现准确恢复的最佳策略。然后，我们建立了一些自然的概念类，包括所有类的单调公式，PAC学习的单调公式，和类的合取，析取，k-CNF，k-DNF，和线性阈值，是一致的学习部分观察。最后，我们证明了奇偶校验和单调项1-决策列表的概念类是不正确的一致从部分观察，如果RP <$NP。这意味着从部分观察中可以持续学习的内容与在完整或噪声环境中可以学习的内容的分离。
We present a general machine learning framework for modelling the phenomenon of missing information in data. We propose a masking process model to capture the stochastic nature of information loss. Learning in this context is employed as a means to recover as much of the missing information as is recoverable. We extend the Probably Approximately Correct semantics to the case of learning from partial observations with arbitrarily hidden attributes. We establish that simply requiring learned hypotheses to be consistent with observed values suffices to guarantee that hidden values are recoverable to a certain accuracy; we also show that, in some sense, this is an optimal strategy for achieving accurate recovery. We then establish that a number of natural concept classes, including all the classes of monotone formulas that are PAC learnable by monotone formulas, and the classes of conjunctions, disjunctions, k-CNF, k-DNF, and linear thresholds, are consistently learnable from partial observations. We finally show that the concept classes of parities and monotone term 1-decision lists are not properly consistently learnable from partial observations, if RP ≠ NP. This implies a separation of what is consistently learnable from partial observations versus what is learnable in the complete or noisy setting.