Abstract: When online algorithm predicts large number of examples, its time and space complexity is very low and prediction accuracy is very high, it has obvious advantage over batch learning. Since the online learning framework that makes a compromise of the correctness and conservativeness is proposed by Jivinen and M.Warmuth, the framework have been referenced widely, but in exponentiated gradient algorithms proposed by Jivinen and M.Warmuth, the approximation steps in the derivation of loss function of objection function lead to bad results. In this paper, by means of duality theory of optimization, the novel non-approximation multiplicative update classifier algorithms based on the different distance functions and loss functions are proposed. A series of experiments show that the algorithm improves the prediction accuracy.

Key words: optimization duality theory, non-approximation update, online learning, multiplicative weight update

摘要： 大样本集上在线预测算法时间空间复杂度小、预测准确性高，与批处理学习算法相比，有明显的优势。自从Jivinen和M.Warmuth提出权衡正确性与保守性的在线学习框架后，在线学习框架已被广泛引用。但是在Jivinen和M.Warmuth提出的梯度下降和指数梯度下降算法中，对目标函数中的损失函数求导过程中使用近似步骤会引起在线学习结果恶化。运用对偶最优化理论，提出了非近似的基于不同距离和损失函数的乘更新分类算法，一系列的实验显示算法提高了预测准确率。

关键词: 最优化对偶理论, 非近似更新, 在线学习, 乘权更新