Some Notes on Kernel CRFs Xiaojin Zhu
1 Import Vector Selection for Kernel CRFs In the basic kernel CRF model, each clique c is associated with |y| parameters αj(yc). Even if we only consider vertex cliques, there would be hundreds of thousands of parameters for a typical protein dataset. This seriously affects the training efficiency. To solve the problem, we adopt the notion of “import vector machines” [ZH01]. That is, we use a subset of the training examples instead of all of them. The subset is constructed by greedily selecting training examples one at a time to minimize the loss function: argminkO(fA∪{k}, λ) −O(fA, λ) (1) where fA(x,y) = ∑