This paper belongs to the area of research known as universal pre diction of individual sequences (see [2] for a review): the predictor's goal is t o compete with a wide benchmark class of prediction strategies. In the previou s papers [15] and [14] we constructed prediction strategies competitive with the important classes of Markov and stationary, respectively, continuous pred iction strategies. In this paper we consider competing against possibly discontinuous s trategies. Our main results assert the existence of prediction strategies com petitive with the Markov strategies. This paper's idea of transition from continuous to general benchma rk classes was motivated by Skorokhod's topology for the space D of "c` adl` ag" functions, most of which are discontinuous. Skorokhod's idea was to allow small d eforma-tions not only along the vertical axis but also along the horizontal ax is when defining neighborhoods. Skorokhod's topology was metrized by Kolm ogorov so that it became a separable space ([1], Appendix III; [11], p. 913), w hich allows us to apply one of the numerous algorithms for prediction with exper t advice (Kalnishkan and Vyugin's Weak Aggregating Algorithm in this paper) to construct a universal algorithm. In Section 2 we give the main definitions and state our main results, Th eo-rems 1 and 2; their proofs are given in Sections 3 and 4, respectively .

Suppose F is a normed function class of prediction strategies (the "benchmar k class"). It is well known that, under some restrictions on F, there exists a "master prediction strategy" (sometimes also called a "universal s trategy") that performs almost as well as the best strategies in F whose norm is not too large (see, e.g., [9, 5]). The "leading prediction strategies" constructed in this paper satisfy a stronger property: the loss of any prediction strategy in F whose norm is not too large exceeds the loss of a leading strategy by the diverge nce between the predictions output by the two prediction strategies. Therefo re, the leading strategy implicitly serves as a standard for prediction strategies F in F whose norm is not too large: such a prediction strategy F suffers a small loss to the degree that its predictions resemble the leading strategy's predict ions, and the only way to compete with the leading strategy is to imitate it. We start the formal exposition with a simple asymptotic result (Prop osition 1 in 2) asserting the existence of leading strategies in the problem of on -line 1 regression with the quadratic loss function for the class of continu ous limited-memory prediction strategies.

We present an unsupervised learning algorithm that mines large text corpora for patterns that express implicit semantic relations. For a given input word pair X:Y with some unspecified semantic relations, the corresponding output list of patterns is ranked according to how well each pattern Pi expresses the relations between X and Y. For example, given X=ostrich and Y=bird, the two highest ranking output patterns are "X is the largest Y" and "Y such as the X". The output patterns are intended to be useful for finding further pairs with the same relations, to support the construction of lexicons, ontologies, and semantic networks. The patterns are sorted by pertinence, where the pertinence of a pattern Pi for a word pair X:Y is the expected relational similarity between the given pair and typical pairs for Pi. The algorithm is empirically evaluated on two tasks, solving multiple-choice SAT word analogy questions and classifying semantic relations in noun-modifier pairs. On both tasks, the algorithm achieves state-of-the-art results, performing significantly better than several alternative pattern ranking algorithms, based on tf-idf.

In this note we introduce the notion of islands for restricting local search. We show how we can construct islands for CNF SAT problems, and how much search space can be eliminated by restricting search to the island.

This paper belongs to the area of learning theory that has been variously referred to as prediction with expert advice, competitive on-line prediction, p rediction of individual sequences, and universal on-line learning; see [7] for a re view. There are many proof techniques known in this field; this paper is based on K alnishkan and Vyugin's Weak Aggregating Algorithm [16], but it is possible that som e of the numerous other techniques could be used instead. In Section 2 we give the main definitions and state our main results, Th e-orems 1-4; their proofs are given in Sections 3-6. In Section 7 we inf ormally discuss the notion of stationarity, and Section 8 concludes.

We present in this paper a general algorithm for solving first-order formulas in particular theories called "decomposable theories". First of all, using special quantifiers, we give a formal characterization of decomposable theories and show some of their properties. Then, we present a general algorithm for solving first-order formulas in any decomposable theory "T". The algorithm is given in the form of five rewriting rules. It transforms a first-order formula "P", which can possibly contain free variables, into a conjunction "Q" of solved formulas easily transformable into a Boolean combination of existentially quantified conjunctions of atomic formulas. In particular, if "P" has no free variables then "Q" is either the formula "true" or "false". The correctness of our algorithm proves the completeness of the decomposable theories. Finally, we show that the theory "Tr" of finite or infinite trees is a decomposable theory and give some benchmarks realized by an implementation of our algorithm, solving formulas on two-partner games in "Tr" with more than 160 nested alternated quantifiers.

Questions related to the evolution of language have recently known an impressive increase of interest (Briscoe, 2002). This short paper aims at questioning the scientific status of these models and their relations to attested data. We show that one cannot directly model non-linguistic factors (exogenous factors) even if they play a crucial role in language evolution. We then examine the relation between linguistic models and attested language data, as well as their contribution to cognitive linguistics.

Diagrammatic, analogical or iconic representations are often contrasted with linguistic or logical representations, in which the shape of the symbols is arbitrary. The aim of this paper is to make a case for the usefulness of diagrams in inferential knowledge representation systems. Although commonly used, diagrams have for a long time suffered from the reputation of being only a heuristic tool or a mere support for intuition. The first part of this paper is an historical background paying tribute to the logicians, psychologists and computer scientists who put an end to this formal prejudice against diagrams. The second part is a discussion of their characteristics as opposed to those of linguistic forms. The last part is aimed at reviving the interest for heterogeneous representation systems including both linguistic and diagrammatic representations.

A standard approach in pattern classification is to estimate the distributions of the label classes, and then to apply the Bayes classifier to the estimates of the distributions in order to classify unlabeled examples. As one might expect, the better our estimates of the label class distributions, the better the resulting classifier will be. In this paper we make this observation precise by identifying risk bounds of a classifier in terms of the quality of the estimates of the label class distributions. We show how PAC learnability relates to estimates of the distributions that have a PAC guarantee on their $L_1$ distance from the true distribution, and we bound the increase in negative log likelihood risk in terms of PAC bounds on the KL-divergence. We give an inefficient but general-purpose smoothing method for converting an estimated distribution that is good under the $L_1$ metric into a distribution that is good under the KL-divergence.

We present here a formal foundation for an iterative and incremental approach to constructing and evaluating preference queries. Our main focus is on query modification: a query transformation approach which works by revising the preference relation in the query. We provide a detailed analysis of the cases where the order-theoretic properties of the preference relation are preserved by the revision. We consider a number of different revision operators: union, prioritized and Pareto composition. We also formulate algebraic laws that enable incremental evaluation of preference queries. Finally, we consider two variations of the basic framework: finite restrictions of preference relations and weak-order extensions of strict partial order preference relations.