Algorithmic identification of probabilities is hard

作者：

Highlights：

• Inductive inference of probability measures from their random elements is studied.

• We disprove the main claim of the original paper by Vitanyi and Chater.

• We indeed show that learning cannot be achieved if we require bounded deficiency.

• If we remove the bounded deficiency requirement, we do get a weak positive result.

摘要

•Inductive inference of probability measures from their random elements is studied.•We disprove the main claim of the original paper by Vitanyi and Chater.•We indeed show that learning cannot be achieved if we require bounded deficiency.•If we remove the bounded deficiency requirement, we do get a weak positive result.

论文关键词：Algorithmic learning theory,Algorithmic randomness

论文评审过程：Received 12 April 2017, Revised 28 December 2017, Accepted 10 January 2018, Available online 15 March 2018, Version of Record 30 April 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.01.002