  In this paper, we propose a new framework to study the generalization
property of classifier chains trained over observations associated with
multiple and interdependent class labels. The results are based on large
deviation inequalities for Lipschitz functions of weakly dependent sequences
proposed by Rio in 2000. We believe that the resulting generalization error
bound brings many advantages and could be adapted to other frameworks that
consider interdependent outputs. First, it explicitly exhibits the dependencies
between class labels. Secondly, it provides insights of the effect of the order
of the chain on the algorithm generalization performances. Finally, the two
dependency coefficients that appear in the bound could also be used to design
new strategies to decide the order of the chain.
