Initially introduced by Peter Hammer, Logical Analysis of Data is a methodology that aims at computing a logical justification for dividing a group of data in two groups of observations, usually called the positive and negative groups. Consider this partition into positive and negative groups as the description of a partially defined Boolean function; the data is then processed to identify a subset of attributes, whose values may be used to characterize the observations of the positive groups against those of the negative group. LAD constitutes an interesting rule-based learning alternative to classic statistical learning techniques and has many practical applications. Nevertheless, the computation of group characterization may be costly, depending on the properties of the data instances. A major aim of our work is to provide effective tools for speeding up the computations, by computing some \emph{a priori} probability that a given set of attributes does characterize the positive and negative groups. To this effect, we propose several models for representing the data set of observations, according to the information we have on it. These models, and the probabilities they allow us to compute, are also helpful for quickly assessing some properties of the real data at hand; furthermore they may help us to better analyze and understand the computational difficulties encountered by solving methods. Once our models have been established, the mathematical tools for computing probabilities come from Analytic Combinatorics. They allow us to express the desired probabilities as ratios of generating functions coefficients, which then provide a quick computation of their numerical values. A further, long-range goal of this paper is to show that the methods of Analytic Combinatorics can help in analyzing the performance of various algorithms in LAD and related fields.
翻译:由Peter Hammer 最初推出的“ 数据逻辑分析” 方法旨在计算将一组数据分为两组观察的逻辑理由,通常称为正组和负组。 将这一分区视为正组和负组, 以描述部分定义的布林函数; 然后将数据处理, 以辨别一组属性, 其值可用于描述正组观察相对于负组的观察。 LAD 是一种有趣的基于规则的学习, 替代经典统计学习技术, 并有许多实用应用。 然而, 计算一组特性的计算可能成本很高, 取决于数据实例的特性。 我们工作的一个主要目的是提供有效工具, 加速计算计算结果, 将它分为正和负组函数; 由此, 我们提出了几种模型的模型, 以及它们能帮助我们进一步快速评估实际数据的一些特性。 此外, 我们的工作的一个主要目的是通过计算一些emph{areph{abreabreal} 来提供一个有效的工具, 从而让我们能通过快速计算其数值的计算方法, 从而让我们从快速地计算这些模型的计算成本。