Enumerating Maximal Postive Sets using Irredundant Dualization

Prof. Ken Satoh (NII, Japan)

CSL SEMINAR SERIES

DATE: 2003-09-26
TIME: 14:00:00 - 15:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
This is joint work with Takeaki Uno (NII)

We give a new algorithm for enumerating all maximal positive sets w.r.t. a monotone property of sets using dualization, or in other words, minimal hitting sets. A property over sets is monotone if a set satisfies the property, every subset satisfies the property. This kind of enumeration actually related with enumerating maximal frequent sets in data-mining, learning monotone DNF, and enumerating maximal consistent sets. The task here is to enumerate all maximal sets in terms of set inclusion which satisfies the property (maximal positive sets) using a query whether a set satisfies the property or not. The lower bound for query complexity is: |Bd-|+|Bd+|. And the previous best known result for query complexity is: |Bd+|*|Bd-|+|Bd+|*|P|^2, where |Bd+| is the number of maximal positive sets and |Bd-| is the number of minimal negative sets and |P| is the number of possible elements. We give an improvement for this kind of algorithms in terms of the number of queries and the space complexity. Our algorithm checks each minimal negative set just once, while the existing algorithms check more than once, possibly so many times. Our algorithm does not store the minimal negative sets in memory, while the existing algorithms have to store them. The main idea of the improvement is that minimal negative sets computed from maximal positive sets by dualization is still minimally negative even if we add a set to the current maximal positive sets. We analyze the query complexity and the space complexity of our algorithm theoretically, and show that the query complexity is |Bd-|+|Bd+|*|P| and experimentally evaluate the algorithm to show that the computation time on average is in the order of |Bd-|*|Bd+|.
BIO:
Ken Satoh is a professor of NII (National Institute of Informatics), Japan. His research topics include logical foundations of various forms of human reasoning such as nonmonotonic reasoning, belief revision and case-based reasoning. His publications are found at http://research.nii.ac.jp/~ksatoh