I will show how the notion of "output encoding" can be used to examine the effects of problem decomposition on learnability for specific tasks. These effects can be divided into two general classes: local effects and global effects. Local effects, which influence the difficulty of learning individual sub-problems, depend primarily on the coherence of the classes defined by individual output tags. Global effects, which determine the model's ability to learn long-distance dependancies, depend on the information content of the output tags. <br><br>I will also present some recent results showing that the choice of appropriate output encodings can help improve performance in tasks including NP chunking and semantic role labelling; and discuss the use of hill-climbing algorithms to automatically select an appropriate encoding for a given task. If time permits, I will also present an algorithm I have been developing for voting in structured output problems.