A polychotomizer which assigns the input to one of $K, K \ge 3$, is constructed using a set of dichotomizers which assign the input to one of two classes. We propose techniques to construct a set of linear dichotomizers whose combined decision forms a nonlinear polychotomizer, to extract structure from data. One way is using error-correcting output codes (ECOC). We propose to incorporate soft weight sharing in training a multilayer perceptron (MLP) to force the second layer weights to a bimodal distribution to be able to interpret them as the decomposition matrix of classes in terms of dichotomizers. This technique can also be used to finetune a set of dichotomizers already generated, for example using ECOC; in such a case, ECOC defines the target values for hidden units in an MLP, facilitating training. Simulation results on eight datasets indicate that compared with a linear one-per-class polychotomizer, pairwise linear dichotomizers and ECOC-based linear dichotomizers, this method generates more accurate classifiers. We also propose and test a method of incremental construction whereby the required number of dichotomizers is determined automatically as opposed to assumed a priori.