Partial multi-label learning (PML) is an emerging weakly supervised learning framework, where each training example is associated with multiple candidate labels which are only partially valid. To learn the multi-label predictive model from PML training examples, most existing approaches work by identifying valid labels within candidate label set via label confidence estimation. In this paper, a novel strategy towards partial multi-label learning is proposed by enabling binary decomposition for handling PML training examples. Specifically, the widely used error-correcting output codes (ECOC) techniques are adapted to transform the PML learning problem into a number of binary learning problems, which refrains from using the error-prone procedure of estimating labeling confidence of individual candidate label. In the encoding phase, a ternary encoding scheme is utilized to balance the definiteness and adequacy of the derived binary training set. In the decoding phase, a loss weighted scheme is applied to consider the empirical performance and predictive margin of derived binary classifiers. Extensive comparative studies against state-of-the-art PML learning approaches clearly show the performance advantage of the proposed binary decomposition strategy for partial multi-label learning.