Identification of Threshold, Regular and Submodular Monotone Systems: Theory and Algorithms

点击翻译按钮获取中文摘要

The focus of this research is the development of algorithms, theory, and applications for the identification of all minimal representatives, for implicitly given monotone systems. Such systems are a frequent target of knowledge discovery as they represent important information hidden in large databases, complex networks, etc. Problems involving the determination of monotone systems arise naturally in a multitude of areas including: data mining (finding all maximal frequent, minimal infrequent sets); text mining (finding the best linear query in vector space models); machine learning (finding the best rules or patterns); hypergraph dualization (generating all minimal transversals); reliability theory (generating all minimal working and/or maximal failing states); integer programming (generating all minimal feasible solutions); stochastic programming (constructing deterministic equivalents to certain stochastic models); etc. A coherent theory of identification problems for monotone systems based on several recent mathematical results will be developed. Tractable classes will be outlined, efficient algorithms for such classes created and realized by programs. The resulting new methods will be tested on a variety of applications, such as data mining, logical data analysis, machine learning and text mining.