A structured prediction model learning apparatus, method, program, and recording medium maintain prediction performance with a smaller amount of memory. An auxiliary model is introduced by defining the auxiliary model parameter set θ(k) with a log-linear model. A set Θ of auxiliary model parameter sets which minimizes the Bregman divergence between the auxiliary model and a reference function indicating the degree of pseudo accuracy is estimated by using unsupervised data. A base-model parameter set λ which minimizes an empirical risk function defined beforehand is estimated by using supervised data and the set Θ of auxiliary model parameter sets.