We investigate a family of update methods for online machine learning algorithms for cost-sensitive multiclass and structured classification problems. The update rules are based on multinomial logistic models. The most interesting question for such an approach is how to integrate the cost function into the learning paradigm. We propose a number of solutions to this problem. To demonstrate the applicability of the algorithms, we evaluated them on a number of classification tasks related to incremental dependency parsing. .