Given a task of predicting $Y$ from $X$, a loss function $L$, and a set of
probability distributions $\Gamma$ on $(X,Y)$, what is the optimal decision
rule minimizing the worst-case expected loss over $\Gamma$? In this paper, we
address this question by introducing a generalization of the principle of
maximum entropy. Applying this principle to sets of distributions with marginal
on $X$ constrained to be the empirical marginal from the data, we develop a
general minimax approach for supervised learning problems. While for some loss
functions such as squared-error and log loss, the minimax approach rederives
well-knwon regression models, for the 0-1 loss it results in a new linear
classifier which we call the maximum entropy machine. The maximum entropy
machine minimizes the worst-case 0-1 loss over the structured set of
distribution, and by our numerical experiments can outperform other well-known
linear classifiers such as SVM. We also prove a bound on the generalization
worst-case error in the minimax approach.

引入最大熵原理的一般化方法，应用于带有从数据中得出的经验边缘条件的分布集合，提出一种针对监督学习问题的通用 minimax 方法，其中最大熵机是一种新的最小化结构化分布中最坏情况 0-1 损失的线性分类器，并且通过实验表明可以优于其他线性分类器，同时证明了 minimax 方法中的泛化最坏情况误差保证的界限。