計算可能な予測

履歴
2019年7月 校正

タイトル
Computable prediction

種類
査読ありの会議録

国際会議と雑誌
Miyabe K. (2019) Computable Prediction. In: Hammer P., Agrawal P., Goertzel B., Iklé M. (eds) Artificial General Intelligence. AGI 2019. Lecture Notes in Computer Science, vol 11654. Springer, Cham
DOI https://doi.org/10.1007/978-3-030-27005-6_14

Abstract
We try to predict the next bit from a given finite binary string
when the sequence is sampled from a computable probability measure on the Cantor space.
There exists the best betting strategy among a class of effective ones up to a multiplicative constant,
the induced prediction from which is called algorithmic probability or universal induction by Solomonoff.
The prediction converges to the true induced measure for sufficiently random sequences.
However, the prediction is not computable.

We propose a framework to study the properties of computable predictions.
We prove that all sufficiently general computable predictions also converge to the true induced measure.
The class of sequences along which the prediction converges is related to computable randomness.

We also discuss the speed of the convergence.
We prove that, even when a computable prediction predicts a computable sequence,
the speed of the convergence cannot be bounded by a computable function monotonically decreasing to $0$.

ダウンロード
preprint
slide

一様相対化

履歴
2019年6月19日 オンライン

タイトル
Uniform relativization

種類
簡易査読ありの会議録,サーベイ

国際会議と雑誌
In: Manea F., Martin B., Paulusma D., Primiero G. (eds) Computing with Foresight and Industry. CiE 2019. Lecture Notes in Computer Science, vol 11558. Springer, Cham
DOI: https://doi.org/10.1007/978-3-030-22996-2_5

Abstract
This paper is a tutorial on uniform relativization. The usual relativization considers computation using an oracle, and the computation may not work for other oracles, which is similar to Turing reduction. The uniform relativization also considers computation using oracles, however, the computation should work for all oracles, which is similar to truth-table reduction. The distinction between these relativizations is important when we relativize randomness notions in algorithmic randomness, especially Schnorr randomness. For Martin-Löf randomness, its usual relativization and uniform relativization are the same so we do not need to care about this uniform relativization.

We focus on two specific examples of uniform relativization: van Lambalgen’s theorem and lowness. Van Lambalgen’s theorem holds for Schnorr randomness with the uniform relativization, but not with the usual relativization. Schnorr triviality is equivalent to lowness for Schnorr randomness with the uniform relativization, but not with the usual relativization. We also discuss some related known results.

ダウンロード
preprint
slide

Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales: a game-theoretic approach

履歴
2018年5月4日 AOP受理

タイトル
Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales: a game-theoretic approach
(with T. Sasai and A. Takemura)

種類
正論文

国際会議と雑誌
Annals of Probability,
Annals of Probability, Vol. 47, No. 2, 1136-1161, March 2019.

Abstract
We prove an Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales. Our proof is given in the framework of the game-theoretic probability of Shafer and Vovk. As many other game-theoretic proofs, our proof is self-contained and explicit.

ダウンロード
arXiv

Muchnik degrees and Medvedev degrees of the randomness notions

履歴
2018年9月 受理
2018年3月11日 投稿

タイトル
Muchnik degrees and Medvedev degrees of the randomness notions

種類
査読ありの事後会議録

国際会議と雑誌
ALC2015とALC2017の共同議事録
World Scientificから出版

Proceedings of the 14th and 15th Asian Logic Conferences, pp. 108-128 (2019) January

Abstract
The main theme of this paper is computational power when a machine is allowed to access random sets.
The computability depends on the randomness notions and we compare them by Muchnik and Medvedev degrees.
The central question is whether, given an random oracle, one can compute a more random set.
The main result is that, for each Turing functional,
there exists a Schnorr random set whose output is not computably random.

ダウンロード
Muchnikdegrees

Coherence of reducibilities with randomness notions

履歴
2017年2月1日 TOCS受理

タイトル
Coherence of reducibilities with randomness notions

種類
正論文

国際会議と雑誌
Theory of Computing Systems – October 2018, Volume 62, Issue 7, pp 1599–1619
DOI: https://doi.org/10.1007/s00224-017-9752-2

Abstract
Loosely speaking, when $A$ is “more random” than $B$ and $B$ is “random”,
then $A$ should be random.
The theory of algorithmic randomness has some formulations of “random” sets
and “more random” sets.
In this paper, we study which pairs $(R,r)$ of randomness notions $R$
and reducibilities $r$ have the follwing property:
if $A$ is $r$-reducible to $B$ and $A$ is $R$-random,
then $B$ should be $R$-random.
The answer depends on the notions $R$ and $r$.
The implications hold for most pairs, but not for some.
We also give characterizations of $n$-randomness via complexity.

ダウンロード
preprint