| In this study, a linear programming model is formulated that finds an optimal strategy for many decision-making problems that typically arise in homeland security, banking, medicine, and engineering. We consider the problem of deploying a set of tests most effectively when the goal is to detect as many as possible "bad" objects among the vast majority of "good" ones, for example, in searching for contraband. The study assumes that functional dependency between test results and object type is unknown. The model finds an optimal testing strategy in the form of a decision tree that minimizes the expected cost given a detection rate or maximizes the detection rate given the budget. The mathematical basis for the model is a polyhedral description of all decision trees in higher dimensional space.;Decision trees are widely used in data mining and machine learning. A notion of VC-dimension is used to evaluate the bounds of the sample size required for the learning model. For some classes of Boolean functions VC-dimension is already known, for example, for monomials and threshold functions. In Chapter 10, the VC-dimension of Horn functions is derived, and also the VC-dimension of a more general class of k-quasi-Horn functions. In Chapter 11 we state and prove a criterion for k-quasi-Horn functions that generalizes McKinsey's theorem. Also, necessary and sufficient conditions for function to be bidual k-quasi-Horn are stated and proved. |
