排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
This paper resolves the problem of predicting as well as the best expert up to an additive term of the order o(n), where n is the length of a sequence of letters from a finite alphabet. We call the games that permit this weakly mixable and give a geometrical characterisation of the class of weakly mixable games. Weak mixability turns out to be equivalent to convexity of the finite part of the set of superpredictions. For bounded games we introduce the Weak Aggregating Algorithm that allows us to obtain additive terms of the form . 相似文献
2.
Consider a binary string x
0 of Kolmogorov complexity K(x
0) n. The question is whether there exist two strings x
1 and x
2 such that the approximate equalities K(x
i
x
j
) n and K(x
i
x
j
, x
k
) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x
0)). It becomes negative in the case of better accuracy, namely, O(log n). 相似文献
3.
Andrej Muchnik Alexander Shen Mikhail Ustinov Nikolai Vereshchagin Michael Vyugin 《Theoretical computer science》2007
Assume that a program p on input a outputs b. We are looking for a shorter program q having the same property (q(a)=b). In addition, we want q to be simple conditional to p (this means that the conditional Kolmogorov complexity K(q|p) is negligible). In the present paper, we prove that sometimes there is no such program q, even in the case when the complexity of p is much bigger than K(b|a). We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively. 相似文献
4.
Michael V. Vyugin 《Journal of Computer and System Sciences》2005,70(4):539-554
The notions of predictive complexity and of corresponding amount of information are considered. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. We consider predictive complexity for a wide class of bounded loss functions which are generalizations of square-loss function. Relations between unconditional KG(x) and conditional KG(x|y) predictive complexities are studied. We define an algorithm which has some “expanding property”. It transforms with positive probability sequences of given predictive complexity into sequences of essentially bigger predictive complexity. A concept of amount of predictive information IG(y:x) is studied. We show that this information is noncommutative in a very strong sense and present asymptotic relations between values IG(y:x), IG(x:y), KG(x) and KG(y). 相似文献
1