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.