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

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