David Cohen

ICML Conference 2023 Conference Paper

Few-Sample Feature Selection via Feature Manifold Learning

• David Cohen
• Tal Shnitzer
• Yuval Kluger
• Ronen Talmon

In this paper, we present a new method for few-sample supervised feature selection (FS). Our method first learns the manifold of the feature space of each class using kernels capturing multi-feature associations. Then, based on Riemannian geometry, a composite kernel is computed, extracting the differences between the learned feature associations. Finally, a FS score based on spectral analysis is proposed. Considering multi-feature associations makes our method multivariate by design. This in turn allows for the extraction of the hidden manifold underlying the features and avoids overfitting, facilitating few-sample FS. We showcase the efficacy of our method on illustrative examples and several benchmarks, where our method demonstrates higher accuracy in selecting the informative features compared to competing methods. In addition, we show that our FS leads to improved classification and better generalization when applied to test data.

JAIR Journal 2020 Journal Article

Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

• Artem Kaznatcheev
• David Cohen
• Peter Jeavons

Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness landscapes can be represented using valued constraints, and investigate what the structure of such representations reveals about the complexity of local search. First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute. We then develop several techniques to bound the length of any sequence of local search moves. We show that such a bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. In the binary Boolean case, we prove that a degree 2 or treestructured constraint graph gives a quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for any form of local search. Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.

AAAI Conference 2016 Conference Paper

An Oral Exam for Measuring a Dialog System’s Capabilities

• David Cohen
• Ian Lane

This paper suggests a model and methodology for measuring the breadth and flexibility of a dialog system’s capabilities. The approach relies on having human evaluators administer a targeted oral exam to a system and provide their subjective views of that system’s performance on each test problem. We present results from one instantiation of this test being performed on two publicly-accessible dialog systems and a human, and show that the suggested metrics do provide useful insights into the relative strengths and weaknesses of these systems. Results suggest that this approach can be performed with reasonable reliability and with reasonable amounts of effort. We hope that authors will augment their reporting with this approach to improve clarity and make more direct progress toward broadlycapable dialog systems.

AAAI Conference 2015 Conference Paper

Binarisation via Dualisation for Valued Constraints

• David Cohen
• Martin Cooper
• Peter Jeavons
• Stanislav Zivny

Constraint programming is a natural paradigm for many combinatorial optimisation problems. The complexity of constraint satisfaction for various forms of constraints has been widely-studied, both to inform the choice of appropriate algorithms, and to understand better the boundary between polynomial-time complexity and NP-hardness. In constraint programming it is well-known that any constraint satisfaction problem can be converted to an equivalent binary problem using the so-called dual encoding. Using this standard approach any fixed collection of constraints, of arbitrary arity, can be converted to an equivalent set of constraints of arity at most two. Here we show that this transformation, although it changes the domain of the constraints, preserves all the relevant algebraic properties that determine the complexity. Moreover, we show that the dual encoding preserves many of the key algorithmic properties of the original instance. We also show that this remains true for more general valued constraint languages, where constraints may assign different cost values to different assignments. Hence, we obtain a simple proof of the fact that to classify the computational complexity of all valued constraint languages it suffices to classify only binary valued constraint languages.

AAAI Conference 2006 Conference Paper

Constraint Symmetry and Solution Symmetry

• David Cohen
• Christopher Jefferson

Symmetry in constraint satisfaction problems (CSPs) has been considered in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or as an operation preserving the constraints. To reflect these two views, we define solution symmetry and constraint symmetry. We discuss how these concepts are related and show that some CSP instances have many more solution symmetries than constraint symmetries.

IJCAI Conference 2005 Conference Paper

A Unified Theory of Structural Tractability for Constraint Satisfaction and Spread Cut Decomposition

• David Cohen
• Peter Jeavons
• Marc

In this paper we introduce a generic form of structural decomposition for the constraint satisfaction problem, which we call a guarded decomposition. We show that many existing decomposition methods can be characterized in terms of finding guarded decompositions satisfying certain specified additional conditions. Using the guarded decomposition framework we are also able to define a new form of decomposition, which we call a spread cut. We show that discovery of width k spread-cut decompositions is tractable for each k, and that the spread cut decomposition strongly generalize all existing decompositions except hypertrees. Finally we exhibit a family of hypergraphs Hn, for n = 1, 2, 3. .. , where the width of the best hypertree decomposition of each Hn is at least 3n, but the width of the best spreadcut decomposition is at most 2n.

IJCAI Conference 2003 Conference Paper

A Maximal Tractable Class of Soft Constraints

• David Cohen
• Martin Cooper
• Peter Jeavons
• Andrei Krokhin

Many optimization problems can be expressed us­ ing some form of soft constraints, where different measures of desirability arc associated with differ­ ent combinations of domain values for specified subsets of variables. In this paper we identify a class of soft binary constraints for which the prob­ lem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time al­ gorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as "as near as possible" or "as soon as possible after", as well as crisp constraints such as "greater than'1.

AIJ Journal 1998 Journal Article

Constraints, consistency and closure

• Peter Jeavons
• David Cohen
• Martin C. Cooper