problem consists of finding a single logical conjunction that best fits a

weighted dataset of ``positive'' and ``negative'' binary vectors.

Computing classifiers using boosting methods involves a maximum

agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we

describe an exact branch and bound method for maximum agreement over

Boolean monomials, improving on the earlier work of Goldberg and

Shan. In particular, we develop a tighter upper

bounding function and an improved branching procedure that exploits

knowledge of the bound and the dataset, while having a lower branching

factor. Experimental results show that the new method is able to

solve larger problem instances and runs faster within a linear

programming boosting procedure applied to medium-sized datasets from

the UCI repository.

constraints. We are motivated by applications in which the derivatives of the objective

function are unavailable or expensive to compute. This can occur, for example, when

the function is not given analytically and is evaluated by running a simulation. The

DIRECT algorithm by Jones, Pertunnen, and Stuckman is a global derivative-free op-

timization algorithm. It is a deterministic algorithm that samples the space following

a scheme that is justiable theoretically in case of Lipschitz continuous functions. In

practice, DIRECT has proven to be ecient, with respect to the number of function

evaluations, in nding a global minimum for a wide variety of functions. We extend

the DIRECT algorithm to make use of additional free trial points that are made avail-

able when running DIRECT simultaneously with other optimization algorithms. We

compare several deterministic and randomized variants of the DIRECT algorithm that

use the external trial points (DUET). We present experimental results with external

trial points that are sampled at random to show an improvement of DUET over the

performance of the DIRECT algorithm.

sifier from noisy observations. We use smooth boost-

ing to linearly combine abstaining hypotheses, each of

which maps a subcube of the attribute space to one of

the two classes. We introduce a new branch-and-bound

weak learner to maximize the agreement rate of each

hypothesis. Dobkin et al. give an algorithm for maxi-

mizing agreement with real-valued attributes. Our

algorithm improves on the time complexity of Dobkin

et al.’s as long as the data can be binarized so that the

number of binary attributes is o(log of the number of

observations × number of real-valued attributes). Fur-

thermore, we have fine-tuned our branch-and-bound al-

gorithm with a queuing discipline and optimality gap to

make it fast in practice. Finally, since logical patterns in

Hammer et al.’s Logical Analysis of Data (LAD) frame-

work are equivalent to abstaining monomial hy-

potheses, any boosting algorithm can be combined with

our proposed weak learner to construct LAD models.

On various data sets, our method outperforms state-of-

the-art methods that use suboptimal or heuristic weak

learners, such as SLIPPER. It is competitive with other

optimizing classifiers that combine monomials, such as

LAD. Compared to LAD, our method eliminates many

free parameters that restrict the hypothesis space and

require extensive fine-tuning by cross-validation.