Bibtex entries of Prof. Shaul Markovitch

@article{Gabrilovich:2009:WBS,
  journal = {Accepted for Publication in Journal of Artificial Intelligence Research},
  year = {2009},
  title = {Wikipedia-based Semantic Interpretation},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  volume = {},
  number = {},
  month = {},
  pages = {},
  url = {},
  keywords = {Feature Generation, ESA, Text Categorization, Semantic Relatedness, Wikipedia},
  secondary-keywords = {},
  abstract = {Adequate representation of natural language semantics requires access to vast amounts of common sense and domain-specific world knowledge. Prior work in the field was based on purely statistical techniques that did not make use of background knowledge, on limited lexicographic knowledge bases such as Wordnet, or on huge manual efforts such as the CYC project. Here we propose a novel method, called Explicit Semantic Analysis (ESA), for fine-grained semantic interpretation of unrestricted natural language texts. Our method represents meaning in a high-dimensional space of concepts derived from Wikipedia, the largest encyclopedia in existence. We explicitly represent the meaning of any text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our method on text categorization and on computing the degree of semantic relatedness between fragments of natural language text. Using ESA results in significant improvements over the previous state of the art in both tasks. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users.},
}

@inproceedings{Radinsky:2008:PNT,
  year = {2008},
  title = {Predicting the News of Tomorrow Using Patterns inWeb Search Queries},
  address = {Sydney, Australia},
  pages = {},
  booktitle = {Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence (WI'08)},
  author = {Kira Radinsky and Sagie Davidovich and Shaul Markovitch},
  keywords = {Information Retrieval},
  secondary-keywords = {Common-Sense Knowledge},
  url = {},
  abstract = {The novel task we aim at in this work is to predict top terms that will prominently appear in the future news. This is a difficult task that nobody attempted before, as far as we know. We present a novel methodology for using patterns of user queries to predict future events. Query history is obtained from web resources such as Google Trends. In order to predict whether a term will appear in tomorrow's news, we examine if the terms in today's queries indicated this term in the past. We provide empirical support for the effectiveness of our method by showing its prediction power on news archives.},
}

@article{Esmeir:2008:AIL,
  journal = {Journal of Artificial Intelligence Research},
  year = {2008},
  title = {Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach},
  author = {Saher Esmeir and Shaul Markovitch},
  volume = {33},
  number = {},
  month = {},
  pages = {1--31},
  url = {http://www.jair.org/papers/paper2602.html},
  keywords = {Anytime Algorithms, Anytime Learning, Decision Tree Induction, Cost-Sensitive Learning},
  secondary-keywords = {Hard Concepts, Lookahead},
  abstract = {Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns.},
}

@inproceedings{Egozi:2008:CBF,
  year = {2008},
  title = {Concept-Based Feature Generation and Selection for Information Retrieval},
  address = {Chicago, IL},
  pages = {},
  booktitle = {Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence},
  author = {Ofer Egozi and Evgeniy Gabrilovich and Shaul Markovitch},
  keywords = {Feature Generation, Feature Selection, ESA, Information Retrieval},
  secondary-keywords = {Common-Sense Knowledge, Feature Construction},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Egozi-Gabrilovich-Markovitch-aaai2008.pdf},
  abstract = {Traditional information retrieval systems use query words to identify relevant documents. In difficult retrieval tasks, however, one needs access to a wealth of background knowledge. We present a method that uses Wikipedia-based feature generation to improve retrieval performance. Intuitively, we expect that using extensive world knowledge is likely to improve recall but may adversely affect precision. High quality feature selection is necessary to maintain high precision, but here we do not have the labeled training data for evaluating features, that we have in supervised learning. We present a new feature selection method that is inspired by pseudo-relevance feedback. We use the top-ranked and bottom-ranked documents retrieved by the bag-of-words method as representative sets of relevant and non-relevant documents. The generated features are then evaluated and filtered on the basis of these sets. Experiments on TREC data confirm the superior performance of our method compared to the previous state of the art.},
}

@inproceedings{Esmeir:2007:AIC,
  year = {2007},
  title = {Anytime Induction of Cost-sensitive Trees},
  address = {},
  booktitle = {Proceedings of The 21st Conference on Neural Information Processing Systems (NIPS-2007)},
  author = {Saher Esmeir and Shaul Markovitch},
  pages = {},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-NIPS2007.pdf},
  keywords = {Decision Tree Induction, Anytime Algorithms, Anytime Learning, Cost-Sensitive Learning},
  secondary-keywords = {Lookahead},
  abstract = {Machine learning techniques are increasingly being used to produce a wide-range of classifiers for complex real-world applications that involve nonuniform testing costs and misclassification costs. As the complexity of these applications grows, the management of resources during the learning and classification processes becomes a challenging task. In this work we introduce ACT (Anytime Cost-sensitive Trees), a novel framework for operating in such environments. ACT is an anytime algorithm that allows trading computation time for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques ACT approximates for each candidate split the cost of the subtree under it and favors the one with a minimal cost. Due to its stochastic nature ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare the performance of ACT to that of the state of the art cost-sensitive tree learners. The results show that for most domains ACT produces trees of significantly lower costs. ACT is also shown to exhibit good anytime behavior with diminishing returns.},
}

@article{Gabrilovich:2007:HEH,
  journal = {Journal of Machine Learning Research},
  year = {2007},
  title = {Harnessing the Expertise of 70,000 Human Editors: Knowledge-Based Feature Generation for Text Categorization},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  volume = {8},
  number = {},
  month = {Oct},
  pages = {2297--2345},
  url = {http://jmlr.csail.mit.edu/papers/v8/gabrilovich07a.html},
  keywords = {Feature Generation, Text Categorization, Information Retrieval},
  secondary-keywords = {Common-Sense Knowledge, Feature Constrcution},
  abstract = {Most existing methods for text categorization use induction algorithms in conjunction with the bag of words document representation. While they perform well in many categorization tasks, these methods are inherently limited when faced with more complicated tasks where external knowledge is essential. Recently, there have been a number of attempts to augment the bag of words approach with external knowledge, including semi-supervised learning and transfer learning. In this work, we present a new framework for automatic acquisition of world knowledge and methods for incorporating it into the text categorization process. Our approach enhances machine learning algorithms with features generated from domain-specific and common-sense knowledge. This knowledge is represented by ontologies that contain hundreds of thousands of concepts, further enriched by several orders of magnitude through controlled Web crawling. Prior to text categorization, a feature generator analyzes the documents and maps them onto appropriate ontology concepts that augment the bag of words. Feature generation is accomplished through contextual analysis of document text, thus implicitly performing word sense disambiguation. Coupled with the ability to generalize concepts using the ontology, this approach addresses the two main problems of natural language processing---synonymy and polysemy. Categorizing documents with the aid of knowledge-based features leverages information that cannot be deduced from the training documents alone. We applied our methodology using the Open Directory Project---the largest existing Web directory, built by over 70,000 human editors. Experimental results over a range of datasets confirm improved performance compared to the bag of words document representation.},
}

@article{Esmeir:2007:ALD,
  journal = {Journal of Machine Learning Research},
  year = {2007},
  title = {Anytime Learning of Decision Trees},
  author = {Saher Esmeir and Shaul Markovitch},
  volume = {8},
  number = {},
  month = {May},
  pages = {891--933},
  url = {http://jmlr.csail.mit.edu/papers/v8/esmeir07a.html},
  keywords = {Anytime Algorithms, Anytime Learning, Decision Tree Induction},
  secondary-keywords = {Hard Concepts, Lookahead},
  abstract = {The majority of the existing algorithms for learning decision trees are greedy�a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Furthermore, the greedy algorithms require a fixed amount of time and are not able to generate a better tree if additional time is available. We introduce a framework for anytime induction of decision trees that overcomes these problems by trading computation speed for better tree quality. Our proposed family of algorithms employs a novel strategy for evaluating candidate splits. A biased sampling of the space of consistent trees rooted at an attribute is used to estimate the size of the minimal tree under that attribute, and an attribute with the smallest expected tree is selected. We present two types of anytime induction algorithms: a contract algorithm that determines the sample size on the basis of a pre-given allocation of time, and an interruptible algorithm that starts with a greedy tree and continuously improves subtrees by additional sampling. Experimental results indicate that, for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.},
}

@inproceedings{Esmeir:2007:ORJ,
  year = {2007},
  title = {Occam's Razor Just Got Sharper},
  address = {Hyderabad, India},
  booktitle = {Proceedings of The Twentieth International Joint Conference for Artificial Intelligence},
  author = {Saher Esmeir and Shaul Markovitch},
  pages = {768--773},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-ijcai2007.pdf},
  keywords = {Decision Trees},
  secondary-keywords = {},
  abstract = {Occam's razor is the principle that, given two hypotheses consistent with the observed data, the simpler one should be preferred. Many machine learning algorithms follow this principle and search for a small hypothesis within the version space. The principle has been the subject of a heated debate with theoretical and empirical arguments both for and against it. Earlier empirical studies lacked sufficient coverage to resolve the debate. In this work we provide convincing empirical evidence for Occam's razor in the context of decision tree induction. By applying a variety of sophisticated sampling techniques, our methodology samples the version space for many real-world domains and tests the correlation between the size of a tree and its accuracy. We show that indeed a smaller tree is likely to be more accurate, and that this correlation is statistically significant across most domains.},
}

@inproceedings{Gabrilovich:2007:CSR,
  year = {2007},
  title = {Computing Semantic Relatedness using Wikipedia-based Explicit Semantic Analysis},
  address = {Hyderabad, India},
  booktitle = {Proceedings of The Twentieth International Joint Conference for Artificial Intelligence},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  pages = {1606--1611},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Gabrilovich-Markovitch-ijcai2007.pdf},
  keywords = {Wikipedia, Feature Generation, Information Retrieval, ESA, Semantic Relatedness},
  secondary-keywords = {Word Similarity, Common-Sense Knowledge, Semantics},
  abstract = {Computing semantic relatedness of natural language texts requires access to vast amounts of common-sense and domain-specific world knowledge. We propose Explicit Semantic Analysis (ESA), a novel method that represents the meaning of texts in a high-dimensional space of concepts derived from Wikipedia. We use machine learning techniques to explicitly represent the meaning of any text as a weighted vector of Wikipedia-based concepts. Assessing the relatedness of texts in this space amounts to comparing the corresponding vectors using conventional metrics (e.g., cosine). Compared with the previous state of the art, using ESA results in substantial improvements in correlation of computed relatedness scores with human judgments: from $r=0.56$ to $0.75$ for individual words and from $r=0.60$ to $0.72$ for texts. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users.},
}

@inproceedings{Esmeir:2006:WDT,
  year = {2006},
  title = {When a Decision Tree Learner Has Plenty of Time},
  address = {Boston, MA},
  pages = {1597--1600},
  booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence},
  author = {Saher Esmeir and Shaul Markovitch},
  keywords = {Resource-Bounded Reasoning, Anytime Learning},
  secondary-keywords = {Decision Trees},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-aaai2006-WDT.pdf},
  abstract = {The majority of the existing algorithms for learning decision trees are greedy---a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Furthermore, the greedy algorithms require a fixed amount of time and are not able to generate a better tree if additional time is available. To overcome this problem, we present a lookahead-based algorithm for anytime induction of decision trees which allows trading computational speed for tree quality. The algorithm uses a novel strategy for evaluating candidate splits; a stochastic version of ID3 is repeatedly invoked to estimate the size of the tree in which each split results, and the one that minimizes the expected size is preferred. Experimental results indicate that for several hard concepts, our proposed approach exhibits good anytime behavior and yields significantly better decision trees when more time is available.},
}

@inproceedings{Esmeir:2006:AID,
  year = {2006},
  title = {Anytime Induction of Decision Trees: an Iterative Improvement Approach},
  address = {Boston, MA},
  pages = {348--355},
  booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence},
  author = {Saher Esmeir and Shaul Markovitch},
  keywords = {Resource-Bounded Reasoning, Anytime Learning},
  secondary-keywords = {Decision Trees},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-aaai2006-AID.pdf},
  abstract = {Most existing decision tree inducers are very fast due to their greedy approach. In many real-life applications, however, we are willing to allocate more time to get better decision trees. Our recently introduced LSID3 contract anytime algorithm allows computation speed to be traded for better tree quality. As a contract algorithm, LSID3 must be allocated its resources a priori, which is not always possible. In this work, we present IIDT, a general framework for interruptible induction of decision trees that need not be allocated resources a priori. The core of our proposed framework is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is expected to yield the highest marginal utility. The algorithm then rebuilds the subtree with a higher allocation of resources. IIDT can also be configured to receive training examples as they become available, and is thus appropriate for incremental learning tasks. Empirical evaluation with several hard concepts shows that IIDT exhibits good anytime behavior and significantly outperforms greedy inducers when more time is available. A comparison of IIDT to several modern decision tree learners showed it to be superior.},
}

@inproceedings{Gurevich:2006:ALN,
  year = {2006},
  title = {Active Learning with Near Misses},
  address = {Boston, MA},
  pages = {362--367},
  booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence},
  author = {Nela Gurevich and Shaul Markovitch and Ehud Rivlin},
  keywords = {Active Learning},
  secondary-keywords = {Vision},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Gurevich-Markovitch-Rivlin-aaai2006.pdf},
  abstract = {Assume that we are trying to build a visual recognizer for a particular class of objects---chairs, for example---using existing induction methods. Assume the assistance of a human teacher who can label an image of an object as a positive or a negative example. As positive examples, we can obviously use images of real chairs. It is not clear, however, what types of objects we should use as negative examples. This is an example of a common problem where the concept we are trying to learn represents a small fraction of a large universe of instances. In this work we suggest learning with the help of \emph{near misses}---negative examples that differ from the learned concept in only a small number of significant points, and we propose a framework for automatic generation of such examples. We show that generating near misses in the feature space is problematic in some domains, and propose a methodology for generating examples directly in the instance space using \emph{modification operators}---functions over the instance space that produce new instances by slightly modifying existing ones. The generated instances are evaluated by mapping them into the feature space and measuring their utility using known active learning techniques. We apply the proposed framework to the task of learning visual concepts from range images. We examine the problem of defining modification operators over the instance space of range images and solve it by using an intermediate instance space---the \emph{functional representation space}. The efficiency of the proposed framework for object recognition is demonstrated by testing it on real-world recognition tasks.},
}

@inproceedings{Gabrilovich:2006:OBB,
  year = {2006},
  title = {Overcoming the Brittleness Bottleneck using Wikipedia: Enhancing Text Categorization with Encyclopedic Knowledge},
  address = {Boston, MA},
  pages = {1301--1306},
  booktitle = {Proceedings of the Twenty-First National Conference on Artificial Intelligence},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  keywords = {Wikipedia, Feature Generation, Text Categorization, Information Retrieval, ESA},
  secondary-keywords = {Common-sense Knowledge},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Gabrilovich-Markovitch-aaai2006.pdf},
  abstract = {When humans approach the task of text categorization, they interpret the specific wording of the document in the much larger context of their background knowledge and experience. On the other hand, state-of-the-art information retrieval systems are quite \emph{brittle}---they traditionally represent documents as bags of words, and are restricted to learning from individual word occurrences in the (necessarily limited) training set. For instance, given the sentence ``Wal-Mart supply chain goes real time'', how can a text categorization system know that Wal-Mart manages its stock with RFID technology? And having read that ``Ciprofloxacin belongs to the quinolones group'', how on earth can a machine know that the drug mentioned is an antibiotic produced by Bayer? We propose to enrich document representation through automatic use of a vast compendium of human knowledge---an encyclopedia. We apply machine learning techniques to Wikipedia, the largest encyclopedia to date, which surpasses in scope many conventional encyclopedias and provides a cornucopia of world knowledge. Each Wikipedia article represents a \emph{concept}, and documents to be categorized are represented in the rich feature space of words and relevant Wikipedia concepts. Empirical results confirm that this knowledge-intensive representation brings text categorization to a qualitatively new level of performance across a diverse collection of datasets.},
}

@article{Davidov:2006:MGH,
  journal = {Journal of Artificial Intelligence Research},
  year = {2006},
  title = {Multiple-goal Heuristic Search},
  author = {Dmitry Davidov and Shaul Markovitch},
  volume = {26},
  number = {},
  month = {},
  pages = {417--451},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Davidov-Markovitch-JAIR2006.pdf},
  keywords = {Heuristic Search, Speedup Learning, Focused Crawling, Anytime Algorithms},
  secondary-keywords = {},
  abstract = {This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the partial marginal utility of sibling nodes, and the other generalizes marginal-utility over the state feature space. We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their superiority over existing methods.},
}

@article{Amit:2006:LBB,
  journal = {Machine Learning},
  year = {2006},
  title = {Learning to Bid in Bridge},
  author = {Asaf Amit and Shaul Markovitch},
  volume = {63},
  number = {3},
  month = {},
  pages = {287--327},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Amit-Markovitch-mlj2005.pdf},
  keywords = {Opponent Modeling, Learning in Games, Multi-Agent Systems, Bridge},
  secondary-keywords = {Adversary Search},
  abstract = {Bridge bidding is considered to be one of the most difficult problems for game-playing programs. It involves four agents rather than two, including a cooperative agent. In addition, the partial observability of the game makes it impossible to predict the outcome of each action. In this paper we present a new decision-making algorithm that is capable of overcoming these problems. The algorithm allows models to be used for both opponent agents and partners, while utilizing a novel model-based Monte Carlo sampling method to overcome the problem of hidden information. The paper also presents a learning framework that uses the above decision-making algorithm for co-training of partners. The agents refine their selection strategies during training and continuously exchange their refined strategies. The refinement is based on inductive learning applied to examples accumulated for classes of states with conflicting actions. The algorithm was empirically evaluated on a set of bridge deals. The pair of agents that co-trained significantly improved their bidding performance to a level surpassing that of the current state-of-the-art bidding algorithm.},
}

@techreport{Markovitch:2005:SCB,
  year = {2005},
  title = {Self-consistent Batch-Classification},
  number = {CIS-2005-04},
  institution = {Technion},
  author = {Shaul Markovitch and Oren Shnitzer},
  type = {Technical report},
  keywords = {Transduction, KNN, Semi-Supervised Learning},
  secondary-keywords = {Inductive Learning},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-CIS-2005-04.pdf},
  abstract = {Most existing learning algorithms generate classifiers that take as an input a single untagged instance and return its classification. When given a set of instances to classify, the classifier treats each member of the set independently. In this work we introduce a new setup we call \emph{batch classification}. In this setup the induced classifier receives the \emph{testing} instances as a set. Knowing the test set in advance theoretically allows the classifier to classify it more precisely. We study the batch classification framework and develop learning algorithms that take advantage of this setup. We present several KNN-based solutions \citep{FixHodges51, dudahart} that combine the nearest-neighbor rule with some additions that allow it to use the additional information about the test set. Extensive empirical evaluation shows that these algorithms indeed outperform traditional independent classifiers.},
}

@inproceedings{Esmeir:2005:IAA,
  year = {2005},
  title = {Interruptible Anytime Algorithms for Iterative Improvement of Decision Trees},
  address = {Chicago, Illinois},
  booktitle = {Proceedings of the 1st international workshop on Utility-based data mining},
  author = {Saher Esmeir and Shaul Markovitch},
  pages = {78--85},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-2005-KDD.pdf},
  keywords = {Anytime Learning,	Resource-Bounded Reasoning},
  secondary-keywords = {Anytime Induction, Decision Trees, Lookahead, Budgeted Learning, C4.5},
  abstract = {Finding a minimal decision tree consistent with the examples is an NP-complete problem. Therefore, most of the existing algorithms for decision tree induction use a greedy approach based on local heuristics. These algorithms usually require a fixed small amount of time and result in trees that are not globally optimal. Recently, the LSID3 contract anytime algorithm was introduced to allow using extra resources for building better decision trees. A contract anytime algorithm needs to get its resource allocation a priori. In many cases, however, the time allocation is not known in advance, disallowing the use of contract algorithms. To overcome this problem, in this work we present two interruptible anytime algorithms for inducing decision trees. Interruptible anytime algorithms do not require their resource allocation in advance and thus must be ready to be interrupted and return a valid solution at any moment. The first interruptible algorithm we propose is based on a general technique for converting a contract algorithm to an interruptible one by sequencing. The second is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is estimated to yield the highest marginal utility and rebuilds it with higher resource allocation. Empirical evaluation shows a good anytime behavior for both algorithms. The iterative improvement algorithm shows smoother performance profiles which allow more refined control.},
}

@inproceedings{Hamo:2005:CAS,
  year = {2005},
  title = {The Compset Algorithm for Subset Selection},
  address = {Edinburgh, Scotland},
  booktitle = {Proceedings of The Nineteenth International Joint Conference for Artificial Intelligence},
  author = {Yaniv Hamo and Shaul Markovitch},
  pages = {728--733},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Hamo-Markovitch-ijcai2005.pdf},
  keywords = {Subset Selection, Resource-Bounded Reasoning, Local Search},
  secondary-keywords = {Anytime Algorithms},
  abstract = {Subset selection problems are relevant in many domains. Unfortunately, their combinatorial nature prohibits solving them optimally in most cases. Local search algorithms have been applied to subset selection with varying degrees of success. This work presents Compset, a general algorithm for subset selection that invokes an existing local search algorithm from a random subset and its complementary set, exchanging information between the two runs to help identify wrong moves. Preliminary results on complex SAT, Max Clique, 0/1 Multidimensional Knapsack and Vertex Cover problems show that Compset improves the efficient stochastic hill climbing and tabu search algorithms by up to two orders of magnitudes.},
}

@inproceedings{Gabrilovich:2005:FGT,
  year = {2005},
  title = {Feature Generation for Text Categorization Using World Knowledge},
  address = {Edinburgh, Scotland},
  booktitle = {Proceedings of The Nineteenth International Joint Conference for Artificial Intelligence},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  pages = {1048--1053},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Gabrilovich-Markovitch-ijcai2005.pdf},
  keywords = {Feature Generation, Text Categorization, Information Retrieval},
  secondary-keywords = {Common-Sense Knowledge},
  abstract = {We enhance machine learning algorithms for text categorization with generated features based on domain-specific and common-sense knowledge. This knowledge is represented using publicly available ontologies that contain hundreds of thousands of concepts, such as the Open Directory; these ontologies are further enriched by several orders of magnitude through controlled Web crawling. Prior to text categorization, a feature generator analyzes the documents and maps them onto appropriate ontology concepts, which in turn induce a set of generated features that augment the standard bag of words. Feature generation is accomplished through contextual analysis of document text, implicitly performing word sense disambiguation. Coupled with the ability to generalize concepts using the ontology, this approach addresses the two main problems of natural language processing---synonymy and polysemy. Categorizing documents with the aid of knowledge-based features leverages information that cannot be deduced from the documents alone. Experimental results confirm improved performance, breaking through the plateau previously reached in the field.},
}

@article{Markovitch:2005:LER,
  journal = {Autonomous Agents and Multi-agent Systems},
  year = {2005},
  title = {Learning and Exploiting Relative Weaknesses of Opponent Agents},
  author = {Shaul Markovitch and Ronit Reger},
  volume = {10},
  number = {2},
  month = {March},
  pages = {103--130},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Reger-aamas2005.pdf},
  keywords = {Opponent Modeling, Learning in Games, Multi-Agent Systems},
  secondary-keywords = {Adversary Search, Decision Trees},
  abstract = {Agents in a competitive interaction can greatly benefit from adapting to a particular adversary, rather than using the same general strategy against all opponents. One method of such adaptation is Opponent Modeling, in which a model of an opponent is acquired and utilized as part of the agent's decision procedure in future interactions with this opponent. However, acquiring an accurate model of a complex opponent strategy may be computationally infeasible. In addition, if the learned model is not accurate, then using it to predict the opponent's actions may potentially harm the agent's strategy rather than improving it. We thus define the concept of opponent weakness, and present a method for learning a model of this simpler concept. We analyze examples of past behavior of an opponent in a particular domain, judging its actions using a trusted judge. We then infer a weakness model based on the opponent's actions relative to the domain state, and incorporate this model into our agent's decision procedure. We also make use of a similar self weakness model, allowing the agent to prefer states in which the opponent is weak and our agent strong; where we have a relative advantage over the opponent. Experimental results spanning two different test domains demonstrate the agents' improved performance when making use of the weakness models.},
}

@inproceedings{Gabrilovich:2004:TCM,
  year = {2004},
  title = {Text Categorization with Many Redundant Features: Using Aggressive Feature Selection to Make SVMs Competitive with C4.5},
  address = {Banff, Alberta, Canada},
  pages = {321--328},
  booktitle = {Proceedings of The Twenty-First International Conference on Machine Learning},
  publisher = {Morgan Kaufmann},
  author = {Evgeniy Gabrilovich and Shaul Markovitch},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Gabrilovich-Markovitch-icml2004.pdf},
  keywords = {Feature Selection, Text Categorization},
  secondary-keywords = {SVM, C4.5, Decision Trees},
  abstract = {Text categorization algorithms usually represent documents as bags of words and consequently have to deal with huge numbers of features. Most previous studies found that the majority of these features are relevant for classification, and that the performance of text categorization with support vector machines peaks when no feature selection is performed. We describe a class of text categorization problems that are characterized with many redundant features. Even though most of these features are relevant, the underlying concepts can be concisely captured using only a few features, while keeping all of them has substantially detrimental effect on categorization accuracy. We develop a novel measure that captures feature redundancy, and use it to analyze a large collection of datasets. We show that for problems plagued with numerous redundant features the performance of C4.5 is significantly superior to that of SVM, while aggressive feature selection allows SVM to beat C4.5 by a narrow margin.},
}

@inproceedings{Davidov:2004:PGL,
  year = {2004},
  title = {Parameterized Generation of Labeled Datasets for Text Categorization Based on a Hierarchical Directory},
  address = {Sheffield, UK},
  pages = {250--257},
  booktitle = {Proceedings of The 27th Annual International ACM SIGIR Conference},
  publisher = {ACM Press},
  author = {Dmitry Davidov and Evgeniy Gabrilovich and Shaul Markovitch},
  keywords = {Text Categorization, Dataset Generation},
  secondary-keywords = {Dataset Parameters},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Davidov-Gabrilovich-Markovitch-sigir2004.pdf},
  abstract = {Although text categorization is a burgeoning area of IR research, readily available test collections in this field are surprisingly scarce. We describe a methodology and system named ACCIO for automatically acquiring labeled datasets for text categorization from the World Wide Web, by capitalizing on the body of knowledge encoded in the structure of existing hierarchical directories such as the Open Directory. We define parameters of categories that make it possible to acquire numerous datasets with desired properties, which in turn allow better control over categorization experiments. In particular, we develop metrics that estimate the difficulty of a dataset by examining the host directory structure. These metrics are shown to be good predictors of categorization accuracy that can be achieved on a dataset, and serve as efficient heuristics for generating datasets subject to user's requirements. A large collection of automatically generated datasets are made available for other researchers to use.},
}

@inproceedings{Esmeir:2004:LBA,
  year = {2004},
  title = {Lookahead-based Algorithms for Anytime Induction of Decision Trees},
  address = {Banff, Alberta, Canada},
  pages = {257--264},
  booktitle = {Proceedings of The Twenty-First International Conference on Machine Learning},
  publisher = {Morgan Kaufmann},
  author = {Saher Esmeir and Shaul Markovitch},
  keywords = {Anytime Learning,	Resource-Bounded Reasoning},
  secondary-keywords = {Anytime Induction, Decision Trees, Lookahead, Budgeted Learning, C4.5},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-icml2004.pdf},
  abstract = {The majority of the existing algorithms for learning decision trees are greedy - a tree is induced top-down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Furthermore, these algorithms require a fixed amount of time and are not able to improve the learned tree if any additional time is available. To overcome this problem, we present a family of lookahead based algorithms for anytime induction of decision trees. Anytime algorithms allow a tradeoff between the solution quality and the consumed time resources. Two methods for looking ahead are introduced. The first one is depth-k lookahead, where k increases as the allocated time permits. The second method uses a novel strategy for evaluating candidate splits; a stochastic version of ID3 is invoked to estimate the size of the tree in which each split results, and the candidate that minimizes the expected size is preferred. Our algorithms were applied both on synthetic and real-world datasets. The experimental results indicate that for several hard concepts, our proposed approach has a good anytime behavior and yields significantly better decision trees when more time is available.},
}

@article{Finkelstein:2003:OSP,
  journal = {Journal of Artificial Intelligence Research},
  year = {2003},
  title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources},
  author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  volume = {19},
  pages = {73--138},
  keywords = {Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems},
  secondary-keywords = {Anytime Algorithms, Portfolio, Las Vegas Algorithms, Parallelization},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-jair2003.pdf},
  journalurl = {http://www.jair.org/abstracts/finkelstein03a.html},
  abstract = {The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem.},
}

@article{Markovitch:2003:SLR,
  journal = {Journal of Machine Learning Research},
  year = {2003},
  volume = {4},
  pages = {649--682},
  title = {Speedup Learning for Repair-based Search by Identifying Redundant Steps},
  author = {Shaul Markovitch and Asaf Shatil},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Shatil-jmlr2003.pdf},
  journalurl = {http://www.jmlr.org/papers/v4/markovitch03a.html},
  keywords = {Speedup Learning, Scheduling},
  secondary-keywords = {Local Search, Decision Trees},
  abstract = {Repair-based search algorithms start with an initial solution and attempt to improve it by iteratively applying repair operators. Such algorithms can often handle large-scale problems that may be difficult for systematic search algorithms. Nevertheless, the computational cost of solving such problems is still very high. We observed that many of the repair steps applied by such algorithms are redundant in the sense that they do not eventually contribute to finding a solution. Such redundant steps are particularly harmful in repair-based search, where each step carries high cost due to the very high branching factor typically associated with it. Accurately identifying and avoiding such redundant steps would result in faster local search without harming the algorithm's problem-solving ability. In this paper we propose a speedup learning methodology for attaining this goal. It consists of the following steps: defining the concept of a redundant step; acquiring this concept during off-line learning by analyzing solution paths for training problems, tagging all the steps along the paths according to the redundancy definition and using an induction algorithm to infer a classifier based on the tagged examples; and using the acquired classifier to filter out redundant steps while solving unseen problems. Our algorithm was empirically tested on instances of real-world employee timetabling problems (ETP). The problem solver to be improved is based on one of the best methods for solving some large ETP instances. Our results show a significant improvement in speed for test problems that are similar to the given example problems.},
}

@article{Grumberg:2003:MLE,
  journal = {Journal of Artificial Intelligence Research},
  year = {2003},
  title = {Learning to Order {BDD} Variables in Verification},
  author = {Orna Grumberg and Shlomi Livne and Shaul Markovitch},
  pages = {83-116},
  volume = {18},
  keywords = {Speedup Learning, BDD Ordering},
  secondary-keywords = {Learning to Order, Decision Trees},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Grumberg-Livne-Markovitch-jair2003.pdf},
  journalurl = {http://www.jair.org/abstracts/grumberg03a.html},
  abstract = {The size and complexity of software and hardware systems have significantly increased in the past years. As a result, it is harder to guarantee their correct behavior. One of the most successful methods for automated verification of finite-state systems is model checking. Most of the current model-checking systems use binary decision diagrams (BDDs) for the representation of the tested model and in the verification process of its properties. Generally, BDDs allow a canonical compact representation of a boolean function (given an order of its variables). The more compact the BDD is, the better performance one gets from the verifier. However, finding an optimal order for a BDD is an NP-complete problem. Therefore, several heuristic methods based on expert knowledge have been developed for variable ordering. We propose an alternative approach in which the variable ordering algorithm gains 'ordering experience' from training models and uses the learned knowledge for finding good orders. Our methodology is based on offline learning of pair precedence classifiers from training models, that is, learning which variable pair permutation is more likely to lead to a good order. For each training model, a number of training sequences are evaluated. Every training model variable pair permutation is then tagged based on its performance on the evaluated orders. The tagged permutations are then passed through a feature extractor and are given as examples to a classifier creation algorithm. Given a model for which an order is requested, the ordering algorithm consults each precedence classifier and constructs a pair precedence table which is used to create the order. Our algorithm was integrated with SMV, which is one of the most widely used verification systems. Preliminary empirical evaluation of our methodology, using real benchmark models, shows performance that is better than random ordering and is competitive with existing algorithms that use expert knowledge. We believe that in sub-domains of models (alu, caches, etc.) our system will prove even more valuable. This is because it features the ability to learn sub-domain knowledge, something that no other ordering algorithm does.},
}

@inproceedings{Finkelstein:2002:OSP,
  year = {2002},
  title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes},
  address = {Edmonton, Alberta, Canada},
  pages = {719--724},
  booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence},
  author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  keywords = {Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems},
  secondary-keywords = {Anytime Algorithms, Portfolio, Las Vegas Algorithms, Parallelization},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-aaai2002.pdf},
  abstract = {The performance of anytime algorithms having a non-deterministic nature can be improved by solving simultaneously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like starting from a different initial state), different algorithms (if several alternatives exist), or several instances of the same algorithm (for non-deterministic algorithms). In this paper we present a general framework for optimal parallelization of independent processes. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate its usefulness on a real problem.},
}

@inproceedings{Davidov:2002:MGS,
  year = {2002},
  title = {Multiple-goal Search Algorithms and their Application to Web Crawling},
  address = {Edmonton, Alberta, Canada},
  pages = {713--718},
  booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence},
  author = {Dmitry Davidov and Shaul Markovitch},
  keywords = {Resource-Bounded Reasoning, Speedup Learning},
  secondary-keywords = {Heuristic Search, Focused Crawling},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Davidov-Markovitch-aaai2002.pdf},
  abstract = {The work described in this paper presents a new framework for heuristic search where the task is to collect as many goals as possible within the allocated resources. We show the inadequacy of traditional distance heuristics for this type of tasks and present alternative types of heuristics that are more appropriate for multiple-goal search. In particular we introduce the yield heuristic that estimates the cost and the benefit of exploring a subtree below a search node. We present a learning algorithm for inferring the yield based on search experience. We apply our adaptive and non-adaptive multiple-goal search algorithms to the web crawling problem and show their efficiency.},
}

@inproceedings{Finkelstein:2001:OSP,
  year = {2001},
  title = {Optimal Schedules for Parallelizing Anytime Algorithms},
  address = {North Carolina},
  booktitle = {Proceedings of The AAAI Fall Symposium on Using Uncertainty within Computation},
  author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  pages = {49--56},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-fss2001.pdf},
  keywords = {Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems},
  secondary-keywords = {Anytime Algorithms, Portfolio, Las Vegas Algorithms, Parallelization},
  abstract = {The performance of anytime algorithms having a nondeterministic nature can be improved by solving simultaneously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like starting from a different initial state), different algorithms (if several alternatives exist), or several instances of the same algorithm (for non-deterministic algorithms). A straightforward parallelization, however, usually results in only a linear speedup, while more effective parallelization schemes require knowledge about the problem space and/or the algorithm itself. In this paper we present a general framework for parallelization, which uses only minimal information on the algorithm (namely, its probabilistic behavior, described by a performance profile), and obtains a super-linear speedup by optimal scheduling of different instances of the algorithm-problem pairs. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate the behavior of optimal schedules for different kinds of anytime algorithms.},
}

@techreport{Markovitch:1999:AML,
  year = {1999},
  title = {Applications of Macro Learning to Path Planning},
  number = {CIS9907},
  institution = {Technion},
  author = {Shaul Markovitch},
  type = {Technical report},
  keywords = {Speedup Learning, Macro Learning},
  secondary-keywords = {Path Planning, Deductive Learning},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-CIS9907.pdf},
  abstract = {Many robotics motion-planning techniques use common heuristic graph search algorithms for finding a path from the current state to the goal state. The research described here studies the application of macro-operators learning to the domain of map-driven robot navigation for reducing the search cost. We assume that a robot is placed in an environment where it has to move between various locations (for example, an office-like environment) where it is given tasks of delivering items between offices. We assume that a navigation task consists of a search for a path and movement along the found path. The robot is given a map of the environment ahead of time and has computation resources available. We suggest using this computation time for macro-learning. Macro-learning is a technique for speeding up the search process. Applying macro-learning for navigation brings interesting research problems. Using macros has positive effect on the search cost but negative effect on the solution quality (and therefore the movement cost). The paper describes an extensive set of experiments that study the tradeoff between these two effects and test their combined effect on the total navigation cost.},
}

@article{Lindenbaum:2004:SSN,
  journal = {Machine Learning},
  year = {2004},
  title = {Selective Sampling for Nearest Neighbor Classifiers},
  author = {Michael Lindenbaum and Shaul Markovitch and Dmitry Rusakov},
  volume = {54},
  number = {2},
  pages = {125--152},
  keywords = {Active Learning},
  secondary-keywords = {Selective Sampling, Lookahead, Value of Information},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Lindenbaum-Markovitch-Rusakov-mlj2004.pdf},
  abstract = {Most existing inductive learning algorithms work under the assumption that their training examples are already tagged. There are domains, however, where the tagging procedure requires significant computation resources or manual labor. In such cases, it may be beneficial for the learner to be active, intelligently selecting the examples for labeling with the goal of reducing the labeling cost. In this paper we present LSS - a lookahead algorithm for selective sampling of examples for nearest neighbor classifiers. The algorithm is looking for the example with the highest utility, taking its effect on the resulting classifier into account. Computing the expected utility of an example requires estimating the probability of its possible labels. We propose to use the random field model for this estimation. The LSS algorithm was evaluated empirically on seven real and artificial data sets, and its performance was compared to other selective sampling algorithms. The experiments show that the proposed algorithm outperforms other methods in terms of average error rate and stability.},
}

@inproceedings{Lindenbaum:1999:SSN,
  year = {1999},
  title = {Selective Sampling for Nearest Neighbor Classifiers},
  author = {Michael Lindenbaum and Shaul Markovitch and Dmitry Rusakov},
  address = {Orlando, Florida},
  pages = {366--371},
  booktitle = {The Proceedings of the Sixteenth National Confernce on Artificial Intelligence},
  keywords = {Active Learning},
  secondary-keywords = {Selective Sampling, Lookahead, Value of Information},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Lindenbaum-Markovitch-Rusakov-aaai1999.pdf},
  abstract = {In the passive, traditional, approach to learning, the information available to the learner is a set of classified examples, which are randomly drawn from the instance space. In many applications, however, the initial classification of the training set is a costly process, and an intelligently selection of training examples from unlabeled data is done by an active learner. This paper proposes a lookahead algorithm for example selection and addresses the problem of active learning in the context of nearest neighbor classifiers. The proposed approach relies on using a random field model for the example labeling, which implies a dynamic change of the label estimates during the sampling process. The proposed selective sampling algorithm was evaluated empirically on artificial and real data sets. The experiments show that the proposed method outperforms other methods in most cases.},
}

@article{Finkelstein:2001:OSM,
  journal = {Artificial Intelligence},
  year = {2001},
  title = {Optimal schedules for monitoring anytime algorithms},
  pages = {63-108},
  author = {Lev Finkelstein and Shaul Markovitch},
  volume = {126},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-aij2001.pdf},
  keywords = {Monitoring, Resource-Bounded Reasoning, Scheduling},
  secondary-keywords = {Anytime Algorithms},
  abstract = {Monitoring anytime algorithms can significantly improve their performance. This work deals with the problem of off-line construction of monitoring schedules. We study a model where queries are submitted to the monitored process in order to detect satisfaction of a given goal predicate. The queries consume time from the monitored process, thus delaying the time of satisfying the goal condition. We present a formal model for this class of problems and provide a theoretical analysis of the class of optimal schedules. We then introduce an algorithm for constructing optimal monitoring schedules and prove its correctness. We continue with distribution-based analysis for common distributions, accompanied by experimental results. We also provide a theoretical comparison of our methodology with existing monitoring techniques.},
}

@article{Markovitch:2002:FGU,
  journal = {Machine Learning},
  year = {2002},
  title = {Feature Generation Using General Constructor Functions},
  pages = {59--98},
  author = {Shaul Markovitch and Danny Rosenstein},
  volume = {49},
  keywords = {Feature Generation},
  secondary-keywords = {Constructive Induction, Feature Construction, Feature Selection, Decision Trees},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Rosenstein-mlj2002.pdf},
  abstract = {Most classification algorithms receive as input a set of attributes of the classified objects. In many cases, however, the supplied set of attributes is not sufficient for creating an accurate, succinct and comprehensible representation of the target concept. To overcome this problem, researchers have proposed algorithms for automatic construction of features. The majority of these algorithms use a limited predefined set of operators for building new features. In this paper we propose a generalized and flexible framework that is capable of generating features from any given set of constructor functions. These can be domain-independent functions such as arithmetic and logic operators, or domain-dependent operators that rely on partial knowledge on the part of the user. The paper describes an algorithm which receives as input a set of classified objects, a set of attributes, and a specification for a set of constructor functions that contains their domains, ranges and properties. The algorithm produces as output a set of generated features that can be used by standard concept learners to create improved classifiers. The algorithm maintains a set of its best generated features and improves this set iteratively. During each iteration, the algorithm performs a beam search over its defined feature space and constructs new features by applying constructor functions to the members of its current feature set. The search is guided by general heuristic measures that are not confined to a specific feature representation. The algorithm was applied to a variety of classification problems and was able to generate features that were strongly related to the underlying target concepts. These features also significantly improved the accuracy achieved by standard concept learners, for a variety of classification problems.},
}

@article{Carmel:1999:ESM,
  journal = {Autonomous Agents and Multi-agent Systems},
  year = {1999},
  title = {Exploration Strategies for Model-based Learning in Multiagent Systems},
  number = {2},
  pages = {141--172},
  author = {David Carmel and Shaul Markovitch},
  volume = {2},
  keywords = {Opponent Modeling, Exploration, Active Learning},
  secondary-keywords = {Lookahead, Exploration vs. Exploitation, Learning DFA},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-aamas1999.pdf},
  abstract = {An agent that interacts with other agents in multi-agent systems can benefit significantly from adapting to the others. When performing active learning, every agent�s action affects the interaction process in two ways: The effect on the expected reward according to the current knowledge held by the agent, and the effect on the acquired knowledge, and hence, on future rewards expected to be received. The agent must therefore make a tradeoff between the wish to exploit its current knowledge, and the wish to explore other alternatives, to improve its knowledge for better decisions in the future. The goal of this work is to develop exploration strategies for a model-based learning agent to handle its encounters with other agents in a common environment. We first show how to incorporate exploration methods usually used in reinforcement learning into model-based learning. We then demonstrate the risk involved in exploration � an exploratory action taken by the agent can yield a better model of the other agent but also carries the risk of putting the agent into a much worse position. We present the lookahead-based exploration strategy that evaluates actions according to their expected utility, their expected contribution to the acquired knowledge, and the risk they carry. Instead of holding one model, the agent maintains a mixed opponent model, a belief distribution over a set of models that reflects its uncertainty about the opponent�s strategy. Every action is evaluated according to its long run contribution to the expected utility and to the knowledge regarding the opponent�s strategy. Risky actions are more likely to be detected by considering their expected outcome according to the alternative models of the opponent�s behavior. We present an efficient algorithm that returns an almost optimal exploration plan against the mixed model and provide a proof of its correctness and an analysis of its complexity. We report experimental results in the Iterated Prisoner�s Dilemma domain, comparing the capabilities of the different exploration strategies. The experiments demonstrate the superiority of lookahead-based exploration over other exploration methods.},
}

@article{Ledeniov:1998:DCS,
  journal = {Journal of Artificial Intelligence Research},
  year = {1998},
  title = {The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference},
  pages = {37--97},
  author = {Oleg Ledeniov and Shaul Markovitch},
  volume = {9},
  keywords = {Speedup Learning},
  secondary-keywords = {Logic Programming, Learning to Order, Decision Trees},
  journalurl = {http://www.jair.org/abstracts/ledeniov98a.html},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Ledeniov-Markovitch-jair1998.pdf},
  abstract = {It is common to view programs as a combination of logic and control: the logic part defines what the program must do, the control part -- how to do it. The Logic Programming paradigm was developed with the intention of separating the logic from the control. Recently, extensive research has been conducted on automatic generation of control for logic programs. Only few of these works considered the issue of automatic generation of control for improving the efficiency of logic programs. In this paper we present a novel algorithm for automatic finding of lowest-cost subgoal orderings. The algorithm works using divide-and-conquer strategy. The given set of subgoals is partitioned into smaller sets, based on co-occurrence of free variables. The subsets are ordered recursively and merged, yielding a provably optimal order. We experimentally demonstrate the utility of the algorithm by testing it in several domains, and discuss the possibilities of its cooperation with other existing methods.},
}

@article{Finkelstein:1998:SML,
  journal = {Journal of Artificial Intelligence Research},
  year = {1998},
  title = {A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle},
  pages = {223--263},
  author = {Lev Finkelstein and Shaul Markovitch},
  volume = {8},
  keywords = {Speedup Learning, Macro Learning, Selective Learning, Active Learning},
  secondary-keywords = {Heuristic Search, Deductive Learning, Explanation-Based Learning},
  journalurl = {http://www.jair.org/abstracts/finkelstein98a.html},
  url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-jair1998.pdf},
  abstract = {One of the most common mechanisms used for speeding up problem solvers is macro-learning. Several methods for acquiring macros have been devised. The major problem with these methods is the vast number of macros that are available for learning. To make macro learning useful, a program must be selective in acquiring and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increasing order of difficulty. The only macros acquired are those that take the problem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of NxN sliding-tile puzzles. After learning on small puzzles, the system is able to efficiently solve puzzles of any size.},
}