Towards Structure Learning Of CP-nets

CP-nets are a kind of qualitative preference of graphical model,it can effectively represent and process user's preferences.In recent years,it has been widely concerned in artificial intelligence field.There has little work to study the CP-nets representation,CP-nets reasoning,and CP-nets learning.This dissertation mainly utilizes the reasoning method to investigate the CP-nets learning problems.The main work are as follows.(1)Based on the expressive power and the compactness of CP-nets,the expressive efficiency of CP-nets efficiency is proposed.In addition,qualitative conclusions of expressive efficiency of two special structure of CP-nets are gave,that is,the set structure CP-nets cannot express the total order relation,however,the equality difference structure CP-nets can express the total order relation.(2)We point out that the CP-nets structure learning is mainly focused on searching the feasible parent set of each attribute,that is,to obtain the directed super struc-ture of graphical model.We propose two kinds of predicate constraints,which consists of father set constraint and root vertex constraint.By performing the pruning constraint on the subset lattice efficiently,we can obtain all the minimal feasible parent sets.All feasible father sets form the approximation structure of acyclic CP-nets—directed super structure,which can be solved in O(m~2n~22~n),where m is the number of samples,n is the number of attributes.(3)Based on the directed super structure of CP-nets,and combining the score and search methods,we can transform the problem of searching an optimal acyclic CP-net into a solution of solving optimization problem in the linear order space.By integrating branch and bound technique into dynamic programming,or inte-grating super structure decomposition into dynamic programming,we can find the optimal acyclic CP-nets more efficiently.In summary,in this dissertation,based on the expressive efficiency of two kinds of special CP-nets,we establish the learning framework from preference database which is comprise of pair-wise comparisons,and give two key steps,that is,mining minimal fea-sible father sets and calculating the optimal acyclic CP-net.Finally,the corresponding algorithms are developed to fulfill these two learning steps.