The problem of learning conditional preference networks (CP-nets) from a set of examples has received great attention recently. However, because of the randomicity of the users' behaviors and the observation errors, there is always some noise making the examples inconsistent, namely, there exists at least one outcome preferred over itself (by transferring) in examples. Existing CP-nets learning methods cannot handle inconsistent examples. In this work, we introduce the model of learning consistent CP-nets from inconsistent examples and present a method to solve this model. We do not learn the CP-nets directly. Instead, we first learn a preference graph from the inconsistent examples, because dominance testing and consistency testing in preference graphs are easier than those in CP-nets. The problem of learning preference graphs is translated into a 0-1 programming and is solved by the branch-and-bound search. Then, the obtained preference graph is transformed into a CP-net equivalently, which can entail a subset of examples with maximal sum of weight. Examples are given to show that our method can obtain consistent CP-nets over both binary and multivalued variables from inconsistent examples. The proposed method is verified on both simulated data and real data, and it is also compared with existing methods.

In this paper, we proposed a framework to address the problem of binary object (2D or 3D) recognition. In our method, a binary object is represented as a Skeleton Tree (ST), transformed from its skeleton (or centerline). Both topological and geometrical features are embedded in the ST and this allows comparisons between different objects by tree matching algorithms. Tree descriptor is used to represent the topological features of the ST, and the maximal isomorphic subtrees (MIST) are obtained by searching for the longest matching substrings in the tree descriptors. A novel method of ST matching based on tree descriptor is also presented. The problems with cyclic skeleton and noise on the skeleton are discussed too. Experiments on a variety of objects get satisfying results, which show the potential of our method in the presence of rotation, scaling, translation and reflection. The time complexity of the algorithm is o(n3), where n is the number of the skeleton branches in ST.