The key is to notice that your problem is equivalent to machine learning with overlapping classes.
Given item $x_n$ and information that it does not belong to class $L_i$, notice that
$x_n \notin L_i \iff x_n \in (L \setminus L_i)$
and, for another class $L_j$,
$L_i \cap L_j = \emptyset \Rightarrow L_j \in (L \setminus L_i)$
$x_n \in L_j, x_n \notin L_i \Rightarrow x_n \in L_j \subseteq (L \setminus L_i)$
You can thus define $L'_i:= L \setminus L_i$. These new classes work just like regular classes, and can contain the regular classes defined earlier.
Unfortunately, this does not mean that the classification is hierarchical (which would simplify matters), since for two classes $L'_i$ and $L'_j$ these classes might have a non-zero intersection. Consider $x_1, x_2 \notin L_1$ and $x_2, x_3 \notin L_2$. Then, $L'_1$ and $L'_2$ overlap, but one is not contained in the other.
I don't know much about ML with overlapping classes; I know the problem is considered to be tough and that there are definitely publications on this. Search for multi-label classifications (e.g. the mldr package in R). Hope this helps.