On Weak Union and Discernibility - A little bit of simple mathematics

In supervised learning, the task of feature reduction can be understood as a sub-category of feature selection, whereby some of attributes can be eliminated if it does not affect information provided by the remaining attributes with respect to the target variable (dependent variable, decision attribute).

Several methodologies can be followed to formulate the constraints for this kind of elimination. One of them refers to the notion of conditional independence developed in the theory of semi-graphoids, including its most popular example of probabilistic independence. Another approach has been developed within the theory of rough sets – we will refer to this one as to the rule of discernibility.

In both above cases, information about the decision attribute is expressed by means of conditional valuations, whereby each combination of values over a set of attributes (which corresponds to a set of rows in a data table, which support the given combination) is assigned with representation of the decision domain (e.g.: a conditional probability distribution, a set of possible decision values, etc.).

The rule of discernibility means that a given attribute can be reduced, if its removal does not cause a merge of combinations (and their supporting sets of rows) having different decision representations. However, such an approach to feature reduction does not need to be equivalent to the constraint of providing the same information about decisions before and after elimination of a given attribute. It is true only for some of valuation functions – functions which satisfy so-called discernibility property.

It is easy to show that if the given type of valuation function satisfies the discernibility property, then it is monotonic in the sense of attribute set inclusion, that is, if an attribute subset B of A provides the same information about decisions (according to the considered valuation function) as A , then it is true also for any other subset of A, which is a superset of B. In other words, using the terminology of the theory of semi-graphoids, one can show that if the notion of conditional independence is defined using a valuation function holding the discernibility property, then it also holds so-called weak union.

In this talk, we show that these two properties – i.e. the discernibility property and the weak union property – are not equivalent to each other. As noted above, implication is true in one of directions (“discernibility property implies weak union”). However, it is possible to specify a relatively simple valuation function which holds weak union (as the conditional independence model) but does not satisfy the discernibility property (that is: “weak union does not imply discernibility property”).