We consider the problem of learning linear classifiers when both features and
labels are binary. In addition, the features are noisy, i.e., they could be
flipped with an unknown probability. In Sy-De attribute noise model, where all
features could be noisy together with same probability, we show that $0$-$1$
loss ($l_{0-1}$) need not be robust but a popular surrogate, squared loss
($l_{sq}$) is. In Asy-In attribute noise model, we prove that $l_{0-1}$ is
robust for any distribution over 2 dimensional feature space. However, due to
computational intractability of $l_{0-1}$, we resort to $l_{sq}$ and observe
that it need not be Asy-In noise robust. Our empirical results support Sy-De
robustness of squared loss for low to moderate noise rates.

研究学习线性分类器时，当特征和标签都是二元时，考虑噪声干扰问题。研究了两种不同的属性噪声模型，并发现当噪声率较低到中等时，平方误差损失是鲁棒的。

属性噪声鲁棒的二分类

Attribute noise robust binary classification

Potential heuristics for state-space search are defined as weighted sums over
simple state features. Atomic features consider the value of a single state
variable in a factored state representation, while binary features consider
joint assignments to two state variables. Previous work showed that the set of
all admissible and consistent potential heuristics using atomic features can be
characterized by a compact set of linear constraints. We generalize this result
to binary features and prove a hardness result for features of higher
dimension. Furthermore, we prove a tractability result based on the treewidth
of a new graphical structure we call the context-dependency graph. Finally, we
study the relationship of potential heuristics to transition cost partitioning.
Experimental results show that binary potential heuristics are significantly
more informative than the previously considered atomic ones.

本研究尝试寻找一种比先前方法更有效的状态空间搜索算法，并通过构造新的图形结构来实现可行性和可解性的结果。