The Set Covering Machine

By Mario Marchand, John Shawe-Taylor. 2003

153 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Associative classification methods assemble decision lists or decision sets from a set of pre-mined rules, generally either by greedily adding rules to the model one by one, or simply including all “top-scoring” rules into a decision set, where each rule is scored separately according to a scoring f”
Interpretable Two-level Boolean Rule Learning for Classification (2015, methodology): “Second, Logical Analysis of Data (LAD) [2] learns patterns for both positive and negative samples by techniques such as set covering [11], and typically builds a classiﬁer by a weighted combination of the patterns, i.e. not a two-level rule.”
MLIC: A MaxSAT-Based Framework for Learning Interpretable Classification Rules (2018, methodology): “Greedy approaches are used with a principled objective function in ENDER [17] and Set covering machines [25].”
Boolean Decision Rules via Column Generation (2018, background): “Predominant practical approaches include a covering or separate-and-conquer strategy ([15, 14, 16, 26, 28, 40],”
Learning query-dependent prefilters for scalable image retrieval (2009, methodology): “Phrases were selected at query time using the greedy algorithm of [13].”
Screening for learning classification rules via Boolean compressed sensing (2014, background): “As an example in a management setting, a rule-based classifier for predicting the voluntary resignation of salespeople is [7]: • Job Role = Specialty Software Sales Rep; AND • Base Salary ≤ 75,168; AND • Months Since Promoted > 13; AND • Months Since Promoted ≤ 30; AND • Quota-Based Compensation =…”
The Decision List Machine (2002, methodology): “Hence, we need to add this constraint in BuildDLM for our bound to be valid but, in practice, we have not seen any significant performance variation introduced by this constraint.”
PAC-Bayes Risk Bounds for Stochastic Averages and Majority Votes of Sample-Compressed Classifiers (2007, methodology): “The algorithm proposed by Marchand and Shawe-Taylor (2002) greedily constructs conjunctions of balls and holes that respect these conditions.”
A systematic analysis of performance measures for classification tasks (2009, methodology): “Empirical evaluation remains the most used approach for the algorithm assessment, although ML algorithms can be evaluated through empirical assessment or theory or both, e.g., derived generalized bounds and empirical results ( Marchand & Shawe-Taylor, 2002 ).”
A statistical approach to rule learning (2006, methodology): “Similar to Rumble, the set covering and decision list machines (Marchand and Taylor, 2003; Marchand and Shawe-Taylor, 2001; Sokolova et al., 2003; Marchand et al., 2003) build sparse rule sets from a predefined rule repository.”
Learning with Decision Lists of Data-Dependent Features (2005, methodology): “The set covering machine (SCM) has recently been proposed by Marchand and Shawe-Taylor (2001, 2002) as an alternative to the support vector machine (SVM) when the objective is to obtain a sparse classifier with good generalization.”
The Linear Programming Set Covering Machine (2004, methodology): “Experiments were conducted on the same data sets used by Marchand and Shawe–Taylor in [6, 7] where all examples with contradictory labels were removed as well as features containing unknown values.”
Exact Rule Learning via Boolean Compressed Sensing (2013, methodology): “Set covering machines (SCM) formulate rule learning with an optimization objective similar to ours, but find solutions using a greedy heuristic (Marchand & Shawe-Taylor, 2002).”
Extracting Diagnoses and Investigation Results from Unstructured Text in Electronic Health Records by Semi-Supervised Machine Learning (2012, methodology): “We compared the performance of S 3 CM against three other algorithms: the original fully-supervised SCM [19], the Transduc-tive Support Vector Machine (TSVM) [20] which is a semi-supervised but non-sparse algorithm, and the Freetext Matching Algorithm (FMA), a natural language processing system we…”
ENDER: a statistical framework for boosting decision rules (2010, methodology): “For instance, the generalization bounds for the sequential covering approach can be given using the analysis of the set covering machine (Marchand and Shawe-Taylor 2002).”