Shaul Markovitch's Papers - Abstracts

1. David Carmel and Shaul Markovitch. Incorporating opponent models into adversary search. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, Oregon, 1996.
   Abstract:
   This work presents a generalized theoretical framework that allows incorporation of opponent models into adversary search. We present the M* algorithm, a generalization of minimax that uses an arbitrary opponent model to simulate the opponent's search. The opponent model is a recursive structure consisting of the opponent's evaluation function and its model of the player. We demonstrate experimentally the potential benefit of using an opponent model. Pruning in M* is impossible in the general case. We prove a sufficient condition for pruning and present the M* algorithm which returns the M* value of a tree while searching only necessary branches.
2. David Carmel and Shaul Markovitch. Learning Models of Intelligent Agents. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, Oregon, 1996.
   Abstract:
   Agents that operate in a multi-agent system need an efficient strategy to handle their encounters with other agents involved. Searching for an optimal interactive strategy is a hard problem because it depends mostly on the behavior of the others. In this work, interaction among agents is represented as a repeated two-player game, where the agents' objective is to look for a strategy that maximizes their expected sum of rewards in the game. We assume that agents' strategies can be modeled as finite automata. A model-based approach is presented as a possible method for learning an effective interactive strategy. First, we describe how an agent should find an optimal strategy against a given model. Second, we present an unsupervised algorithm that infers a model of the opponent's automaton from its input/output behavior. A set of experiments that show the potential merit of the algorithm is reported as well.
3. David Carmel and Shaul Markovitch. Learning models of intelligent agents. Technical Report CIS9606, Technion, March 1996.
   Abstract:
   
4. David Carmel and Shaul Markovitch. Learning and using opponent models in adversary search. Technical Report CIS9609, Technion, March 1996.
   Abstract:
   
5. David Carmel and Shaul Markovitch. Opponent modeling in multi-agent systems. In Gerhard Weiss and Sandip Sen, editors, Adaption And Learning In Multi-Agent Systems, volume 1042 of Lecture Notes in Artificial Intelligence. Springer-Verlag, 1996.
   Abstract:
   
6. Shaul Markovitch and Yaron Sella. Learning of Resource Allocation Strategies For Game Playing. Computational Intelligence, 12(1):88--105, 1996.
   Abstract:
   Human chess players exhibit a large variation in the amount of time they allocate for each move. Yet, the problem of devising resource allocation strategies for game playing has not received enough attention. In this paper we present a framework for studying resource allocation strategies. We define allocation strategy and identify three major types of strategies: static, semi-dynamic, and dynamic. We then describe a method for learning semi-dynamic strategies from self--generated examples. We present an algorithm for assigning classes to the examples based on the utility of investing extra resources. The method was implemented in the domain of checkers, and experimental results show that it is able to learn strategies that improve game-playing performance.
7. Shaul Markovitch and Lev Finkelshtein. A Selective Macro-learning Algorithm and its Application to the NxN Sliding-tile Puzzle. Technical Report CIS9617, Technion, 1996.
   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 increased 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 \NN\ sliding-tile puzzles. After learning on small puzzles, the system is able to solve puzzles of any size.
8. Uri Keidar, Shaul Markovitch, and Erez Webman. Utilization Filtering of Macros Based on Goal Similarity. Technical Report CIS9608, Technion, 1996.
   Abstract:
   Deductive learners acquire knowledge that is implicitly available to improve the performance of the problem solver. One of the most known form of deductive learning is the acquisition of macro operators. Macro-operators carry cost as well as benefits. When the costs outweigh the benefits, we face the utility problem. The vast number of macros available to the learner forces it to be selective to avoid the utility problem. The most common approach to selective macro-learning is using acquisition filters. Such filters try to estimate the utility of a macro before inserting it into the macro knowledge base. One problem with this approach is that the utility of a macro strongly depends on the problem being solved. In this work we suggest an alternative approach called {\em utilization filtering}. Instead of being selective when the macro is {\em acquired}, the learner is selective when the macro is {\em utilized}. We propose to use similarity-based filtering. A macro is considered as potentially useful for a particular problem if it proved to be useful for similar problems. Without further knowledge about the states in the search space, we suggest to use the heuristic function to determine similarity between states. Initial testing of this approach in the grid domain showed that indeed it is beneficial to delay selectivity to the utilization stage.
9. Iddo Dagan, Shaul Marcus, and Shaul Markovitch. Contextual Word Similarity and Estimation from Sparse Data. Computer Speech and Language, 9:123--152, 1995.
   Abstract:
   In recent years there is much interest in word cooccurrence relations, such as n-grams, verb-object combinations, or cooccurrence within a limited context. This paper discusses how to estimate the probability of cooccurrences that do not occur in the training data. We present a method that makes local analogies between each specific unobserved cooccurrence and other cooccurrences that contain similar words. These analogies are based on the asumption that similar word cooccurences have similar values of mutual information. Accordingly, the word similarity metric captures similarities between vectors of mutual information values. Our evaluation suggests that this method performs better than existing, frequency based, smoothing methods, and may provide an alternative to class-based models. A background survey is included, covering issues of lexical cooccurrence, data sparsness and smoothing, word similarity and clustering, and mutual information.
10. Shaul Markovitch and Paul D. Scott. Information Filtering: Selection Mechanisms in Learning Systems. Machine Learning, 10(2):113--151, February 1993.
    Abstract:
    Knowledge has traditionally been considered to have a beneficial effect on the performance of problem solvers but recent studies indicate that knowledge acquisition is not necessarily a monotonically beneficial process, because additional knowledge sometimes leads to a deterioration in system performance. This paper is concerned with the problem of harmful knowledge: that is, knowledge whose removal would improve a system's performance. In the first part of the paper a unifying framework, called the {\it information filtering model\/}, is developed to define the various alternative methods for eliminating such knowledge from a learning system. This framework identifies five locations in the information flow of a learning system where selection processes, called filters, may be inserted to remove potentially harmful knowledge. These filters are termed selective experience, selective attention, selective acquisition, selective retention, and selective utilization. The framework can be used by developers of learning systems as a guide for selecting an appropriate filter to reduce or eliminate harmful knowledge. In the second part of the paper, the framework is used to identify a suitable filter for solving a problem caused by the acquisition of harmful knowledge in a learning system called \LASSY/. \LASSY/ is a system that improves the performance of a PROLOG interpreter by utilizing acquired domain specific knowledge in the form of lemmas stating previously proved results. It is shown that the particular kind of problems that arise with this system are best solved using a novel utilization filter that blocks the use of lemmas in attempts to prove subgoals that have a high probability of failing.
11. Shaul Markovitch and Yaron Sella. Learning of Resource Allocation Strategies for Game Playing. In Proceedings of The Thirteenth International Joint Conference for Artificial Intelligence, pages 974--979, Chambery, France, 1993.
    Abstract:
    Human chess players exhibit a large variation in the amount of time they allocate for each move. Yet, the problem of devising resource allocation strategies for game playing did not receive enough attention. In this paper we present a framework for studying resource allocation strategies. We define allocation strategy and identify three major types of strategies: static, semi-dynamic, and dynamic. We then proceed to describe a method for learning semi-dynamic strategies from self generated examples. The method assigns classes to the examples based on the utility of investing extra resources. The method was implemented in the domain of checkers, and experimental results show that it is able to learn strategies that improve game-playing performance.
12. David Carmel and Shaul Markovitch. Learning Models of the Opponent's Strategy in Game-playing. In Proceedings of The AAAI Fall Symposium on Games: Planing and Learning, North Carolina, 1993.
    Abstract:
    
13. David Lorenz and Shaul Markovitch. Derivative Evaluation Function Learning Using Genetic Operators. In Proceedings of The AAAI Fall Symposium on Games: Planing and Learning, New Carolina, 1993.
    Abstract:
    
14. Iddo Dagan, Shaul Marcus, and Shaul Markovitch. Contextual Word Similarity And Estimation From Sparse Data. In Proceedings of the 31st Annual Meeting of the Association for Computational Linguistics, pages 164--171, Ohio State University, 1993.
    Abstract:
    In recent years there is much interest in word cooccurrence relations, such as n-grams, verb-object combinations, or cooccurrence within a limited context. This paper discusses how to estimate the probability of cooccurrences that do not occur in the training data. We present a method that makes local analogies between each specific unobserved cooccurrence and other cooccurrences that contain similar words, as determined by an appropriate word similarity metric. Our evaluation suggests that this method performs better than existing smoothing methods, and may provide an alternative to class based models.
15. Paul D. Scott and Shaul Markovitch. Experience Selection and Problem Choice in an Exploratory Learning System. Machine Learning, 12:49-67, 1992.
    Abstract:
    
16. Lev Finkelshtein and Shaul Markovitch. Selective acquisition and utilization of macro operators: A learning program solves the general N X N puzzle. Technical report CIS9216, Computer Science Department, Technion, Haifa, Israel, 1992.
    Abstract:
    
17. Shaul Markovitch and Irit Rosdeutscher. Systematic experimentation with deductive learning: Satisficing vs. optimizing search. In Proceedings of Knowledge Compilation and Speedup Learning workshop, Aberdeen, Scotland, 1992.
    Abstract:
    Most of the research conducted in the area of deductive learning is experimental. However, many of the experiments reported are far from being systematic and thorough. There are many parameters that are embedded in the system's architecture and it is not clear how they effect the utility of the learned knowledge. In this paper we describe an attempt to perform systematic experiments in the domain of deductive learning. The part described here explores how the search strategy employed during problem solving and during learning effects the utility of learning process. It was concluded that the utility of deductive learning is negative when the learned knowledge is applied in optimizing search procedure during problem solving, but becomes positive in satisficing search. It was also concluded that for off-line learning it is more beneficial to use optimizing search during the learning process. Knowledge acquired in this method improves both the efficiency and the quality of the problem solving.
18. Paul. D. Scott and Shaul Markovitch. Representation Generation in an Exploratory Learning System. In D. Fisher and M. Pazzani, editors, Concept Formation: Knowledge and Experience in Unsupervised Learning. Morgan Kaufmann, 1991.
    Abstract:
    
19. Reuven A. Hasson, Shaul Markovitch, and Yaron Sella. Using Filters to Improve Efficiency of Game-playing Learning Procedures. In Proceedings of Eleventh International Conference of the Chilean Computer Science Society, pages 125--137, Santiago, Chile, 1991.
    Abstract:
    In this paper we describe a learning system which acquires knowledge in an attempt to improve the performance of a problem solver that plays the game of {\em fives}. We present experimental results indicating that the performance of the problem solver is improved at the beginning, but degrades afterwards down to almost its initial level. We introduce a selection mechanism that tests the system performance with and without the acquired knowledge and allows its addition to the knowledge base only if it proves to be beneficial. We introduce additional selection mechanisms to reduce the number of tests that need to be performed by the above filter and save learning resources. Experiments show that the addition of the filters eliminates the deterioration in performance and improves the learning outcome significantly.
20. Paul D. Scott and Shaul Markovitch. Knowledge Considered Harmful. In Proceedings of IEEE Colloquium on Knowledge Engineering, London, 1990.
    Abstract:
    
21. Marcial Losada and Shaul Markovitch. Groupanalyzer: A system for dynamic analysis of group interaction. In Proceedings of 23rd Hawaii International Conference for System Sciences, Kailua-Kona,Hawaii, 1990.
    Abstract:
    
22. Shaul Markovitch and Paul D. Scott. Utilization Filtering: A Method for Reducing the Inherent Harmfulness of Deductively Learned Knowledge. In Proceedings of The Eleventh International Joint Conference for Artificial Intelligence, pages 738--743, Detroit, Michigan, 1989.
    Abstract:
    This paper highlights a phenomenon that causes deductively learned knowledge to be harmful when used for problem solving. The problem occurs when deductive problem solvers encounter a failure branch of the search tree. The backtracking mechanism of such problem solvers will force the program to traverse the whole subtree thus visiting many nodes twice - once by using the deductively learned rule and once by using the rules that generated the learned rule in the first place. We suggest an approach called utilization filtering to solve that problem. Learners that use this approach submit to the problem solver a filter function together with the knowledge that was acquired. The function decides for each problem whether to use the learned knowledge and what part of it to use. We have tested the idea in the context of a lemma learning system, where the filter uses the probability of a subgoal failing to decide whether to turn lemma usage off. Experiments show an improvement of performance by a factor of 3.
23. Shaul Markovitch and Paul D. Scott. Information Filters and Their Implementation in the SYLLOG System. In Proceedings of The Sixth International Workshop on Machine Learning, Ithaca, New York, 1989. Morgan Kaufmann.
    Abstract:
    
24. Shaul Markovitch. Information Filtering: Selection Mechanisms in Learning Systems. PhD thesis, EECS Department, University of Michigan, 1989.
    Abstract:
    Traditionally knowledge was considered as beneficial to the performance of problem solvers. Recent studies indicate that knowledge acquisition is not necessarily a monotonic process, and that sometimes additional knowledge leads to deterioration in system performance. This thesis studies the problem of harmful knowledge in learning systems, defines a unifying framework to deal with the problem, and tests the framework in the context of a useful learning system. Knowledge is harmful if the problem solver's performance would be improved by removing it. The information filtering model is proposed as a unifying framework for reducing or eliminating harmfulness of knowledge. The framework identifies five logical types of selection processes (filters) that can be incorporated into learning systems in order to reduce harmful knowledge: selective experience, attention, acquisition, retention and utilization. The framework is implemented and tested within the context of LASSY, a learning system that improves the performance of a PROLOG interpreter by utilizing acquired domain specific knowledge. LASSY incorporates two primary learning mechanisms: one deductive and the other inductive. The deductive mechanism is a lemma learner which uses theorems proved in the past as shortcuts for future proving. The inductive mechanism is a module that acquires average costs and number of solutions for various calling patterns that are used for reordering subgoals in rule bodies. LASSY incorporates all five types of selection mechanisms. The two novel ones are an experience filter which uses a model of the task domain to generate training problems that are likely to generate relevant knowledge and utilization filter which is used for filtering out the usage of lemmas in branches of the search tree which have high probability of failing. The system's performance was improved by a factor of two when using the lemma learner and its filters. The subgoal reordering improved the system performance by a factor of 23. When combined, the system's performance was improved by a factor of 36. It is concluded that it is not beneficial to be greedy, even for knowledge, and that being selective by inserting information filters can reduce the harmfulness of knowledge in learning systems.
25. Shaul Markovitch and Paul D. Scott. Automatic Ordering of Subgoals - A Machine Learning Approach. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 224--242, Cleveland, Ohio, USA, 1989.
    Abstract:
    This paper describes a learning system, LASSY1, which explores domains represented by Prolog databases, and use its acquired knowledge to increase the efficiency of a Prolog interpreter by reordering subgoals. The system creates a model of the tasks it faces and uses the model to generate informative training tasks. While performing the training tasks the system updates its inductive knowledge base which includes statistics about number of solutions and costs of various subgoals calling patterns. The collected averages are used by a subgoal ordering procedure to estimate the costs of subgoals sequences during its search for a good ordering. The paper contains a detailed analysis of the cost computation and a detailed account of the ordering procedure. Experiments done with LASSY show an improvement of performance by a factor of 10.
26. Shaul Markovitch and Paul D. Scott. POST-prolog: Structured partially ordered prolog. TR CMI-89-018, Center for Machine Intelligence, Ann Arbor, Michigan, 1989.
    Abstract:
    
27. Paul D. Scott and Shaul Markovitch. Uncertainty based selection of learning experiences. In Proceedings of The Sixth International Workshop on Machine Learning, Ithaca, New York, 1989. Morgan Kaufmann.
    Abstract:
    The training experiences needed by a learning system may be selected by either an external agent or the system itself. We show that knowledge of the current state of the learner's representation, which is not available to an external agent, is necessary for selection of informative experiences. Hence it is advantageous if a learning system can select its own experiences. We show that the uncertainty of the current representation can be used as a heuristic to guide selection of experiences, and describe results obtained with DIDO, an inductive learning system we have developed using an uncertainty based selection heuristic.
28. Paul D. Scott and Shaul Markovitch. Learning novel domains through curiosity and conjecture. In Proceedings of International Joint Conference for Artificial Intelligence, pages 669--674, Detroit, Michigan, 1989.
    Abstract:
    This paper describes DIDO, a system we have developed to carry out exploratory learning of unfamiliar domains without assistance from an external teacher. The program incorporates novel approaches to experience generation and representation generation. The experience generator uses a heuristic based on Shannon's uncertainty function to find informative examples. The representation generator makes conjectures on the basis of small amounts of evidence and retracts them if they prove to be wrong or useless. A number of experiments are described which demonstrate that the system can distribute its learning resources to steadily acquire a good representation of the whole of a domain, and that the system can readily acquire both disjunctive and conjunctive concepts even in the presence of noise.
29. Shaul Markovitch and Paul D. Scott. The Role of Forgetting in Learning. In Proceedings of The Fifth International Conference on Machine Learning, pages 459--465, Ann Arbor, MI, 1988. Morgan Kaufmann.
    Abstract:
    This paper is a discussion of the relationship between learning and forgetting. An analysis of the economics of learning is carried out and it is argued that knowledge can sometimes have a negative value. A series of experiments involving a program which learns to traverse state spaces is described. It is shown that most of the knowledge acquired is of negative value even though it is correct and was acquired solving similar problems. It is shown that the value of the knowledge depends on what else is known and that random forgetting can sometimes lead to substantial improvements in performance. It is concluded that research into knowledge acquisition should take seriously the possibility that knowledge may sometimes be harmful. The view is taken that learning and forgetting are complementary processes which construct and maintain useful representations of experience.