"Learning classifiers automatically from examples is subject to themultidisciplinary field of machine learning.The structured output learning (SOL) is concerned with thelearning of classifiers for prediction of multipleinterdependent variables exhibiting some structure dependence.Recent progress in SOL focuses mainly on supervised methodsthat require labeled examples. A high cost of labeled examplessignificantly limits application of SOL to many domains.Our goal is threefold. First, to developed framework for semi-supervised SOL from cheap partially labeled examples. Second, to apply this new framework to two important SOL tasks: (i) Markov Networks learning and (ii) learning of 2-dimensional image grammars. Third, to use the new algorithms for solving computer vision problems including the image segmentation and the car license plate recognition.To achieve the first goal, we will examine two strategies. First, we willcombine powerful discriminative methods for SOL with generative models offering a principled way to deal with missing labels. Second, we will extend the existing semi-supervised methods in order to handle the partially labeled examples.To achieve the second goal, we will incorporate the existing methods forsupervised SOL of Markov Networks and 2D grammars to the frameworkdeveloped as the first goal.To achieve the third goal, we will build on the technology forimage segmentation and license plate recognition developed bythe host. The currently used classification methods will bereplaced by the developed semi-supervised SOL algorithms todemonstrate their effectiveness on real-life problems.Achieving the goals will be possible by joining the expertiseof the applicant and the host. This applies both to theoreticaland application oriented goals. The applicant is experienced inSOL and Markov Networks while the host will complement thiswith a large expertise in 2D grammars and computervision."