Explorations into Belief State Compression

Talk by Ali Elhalawaty

Location: APB 3027
Start: 28. May 2019 at 1:30 pm
End: 28. May 2019 at 2:30 pm
Research group: Knowledge-Based Systems
Event series: KBS Seminar
iCal

A knowledge base is an integral part of a logic-based artificial intelligence system. The size of the knowledge base has a great effect on the derivation time of a logic-based agent. In this thesis, I present a variety of algorithms for a particular variant of knowledge base size reduction referred to as “Belief State Compression”. Each proposed algorithm can be “lossy” or “lossless” depending on the (in)ability to recover the removed information; and “redundant” or “irredundant” with respect to the necessity of the remaining information in order to remain lossless. Belief state compression differs from previous approaches in at least three aspects. First, it takes its objects to be support-structured sets of unconstrained, rather than flat sets of syntactically constrained, logical formulas, which we refer to as belief states. Second, classical notions of minimality and redundancy are replaced by weaker, resource-bounded alternatives based on the support structure. Third, in “lossy” variants of compression, the compressed knowledge base logically implies only a practically-relevant subset of the original knowledge base. Six variants of belief state compression, falling into three major classes, are presented. Experimental results show that a combination of five of them results in mostly irredundant, lossless compressions, while maintaining reasonable run times.