Few paths, fewer words: model selection with automatic structure functions

The paper “Kolmogorov structure functions for automatic complexity in computational statistics” appeared in the Lecture Notes in Computer Science proceedings of the conference COCOA 2014, Maui, Hawaii.
The paper then appeared in the journal Theoretical Computer Science 2015.

The ideas are implemented in the Structure function calculator.

A new paper Few paths, fewer words: model selection with automatic structure functions has been conditionally accepted for publication in Experimental Mathematics.

Some slides

Covering the computable sets

I participated in the workshop on Algorithmic Randomness in Singapore and the conference on Computability, Complexity and Randomness.

With host Frank Stephan and fellow participant Sebastiaan Terwijn we wrote a paper entitled Covering the recursive sets which appeared in Lecture Notes in Computer Science, Conference on Computability in Europe, 2015, and has now been published in Annals of Pure and Applied Logic.

ビヨーン教授の最新研究の概要

この記事は、ハワイ大学のビヨーン・ヒュース-ハンセン教授(Prof. Bjørn Kjos-Hanssen)のオートマトン複雑性に関する最新の研究について、日本の読者向けに概要をまとめたものである。

1. 目的
オートマトン複雑性に関する研究の目的は、特定の文字列を受領するオートマトンで、できるだけ状態数が少なく、その文字列と同じ長さの他の文字列をできるだけ受領しないオートマトンの効率のよい検索方法を見つけることである。言い換えれば、コルモゴロフ構造関数の考え方によるモデル選択をオートマトン上でより効率よく行うことである。
コルモゴロフ構造関数については歴史の項目で後述する。
モデル選択とは、自然界にある文字列でモデル化できるものが発見されたときに、背景となっているその文字列を生成する仕組みをオートマトンでモデル化することを指す。その文字列を受理し、他の文字列をできるだけ受理しないオートマトンを考えることができれば、そのオートマトンがモデルとして適切だと推測することができる。

2. オートマトン複雑性分野の歴史
オートマトン複雑性分野は近年研究の始まった分野であり、新規性が期待される。
当分野の主な歴史は、以下の通りである。

1960年代末 コルモゴロフ複雑性(Kolmogorov Complexity)
チューリングマシンにおける文字列の複雑性をそれに最適なプログラムの長さで定義
1973年 コルモゴロフ構造関数(Kolmogorov Structure Function)
文字列に対してプログラムとそのプログラムが受領する文字列の数を対応付ける関数で、文字列のモデリングの適切さを測る
2001年 ShallitとWangによるオートマトン複雑性(Automatic Complexity by Shallit and Wang)
コルモゴロフ複雑性を、オートマトンに拡張。オートマトンでの複雑性をその文字列を受領し、他の同じ長さの文字列を受領しないオートマトンの最小の状態数で定義
2014年 Vereshchagin のオートマトン複雑性上での構造関数(Vereshchagin structure function for Automatic complexity)
オートマトン上での構造関数を、オートマトンの状態数と特定の文字列を受領するその状態数のオートマトンが受領する最小の文字列数の対応として定義

3. 当研究に期待される成果
現在、文字列に対する最適なモデルの推測の効率のよいアルゴリズムは発見されていないが、この研究によって、より正確に効率よく推測できるようになる。

4. 当分野において期待されるインパクト
オートマトン複雑性上での構造関数の計算速度の向上が期待されている。

5. 諸科学において期待されるインパクト
構造関数はco-NP問題であるため、未解決問題であるP=NP、co-NP=NPなどの問題についての理解を深めることができる。

当研究は現在進行中で、公開時期は未定である。
引き続きビヨーン教授の最新の情報に注目していただきたい。

 

小林 佐保,千葉大学 理学部 数学・情報数理学科
Saho Kobayashi, Undergraduate, Department of Mathematics and Informatics, Faculty of Science, Chiba University

The Tukey test: starting with a known variance

Consider normal random variables $Y_i$ with means $\mu_i$, $1\le i\le k$.
The Tukey test often seems overly complicated, but it becomes clearer if we first assume that variance of $Y_i$, $\sigma^2$, is known.

Let’s draw $r$ samples from each, called $Y_{i,j}$, $1\le j\le r$.
Denote the sample averages by $\overline Y_{i+}$.
Let $W_i = \overline Y_{i+}-\mu_i$.
Let $Q=R$, the range, be defined by
$$
R = \max_i W_i – \min_i W_i = \max_{i,j} |W_i-W_j|.
$$
Suppose we understand the distribution of $R$ well enough to find a number $Q_\alpha$ such that
$$
\Pr(R\le Q_\alpha) = 1-\alpha
$$
Define the intervals
$$
I_{i,j} = (\overline Y_{i+}-\overline Y_{j+} – Q_\alpha, \overline Y_{i+}-\overline Y_{j+} + Q_\alpha)
$$
Then it is easily seen that
$$
\Pr(\text{for all $i$, $j$, }\mu_i-\mu_j \in I_{i,j}) = 1-\alpha.
$$
and hence for all $i$, $j$,
$$
\Pr(\mu_i-\mu_j\in I_{i,j}) \ge 1-\alpha.
$$
(Larsen and Marx make a mistake here, mixing up the last two equations.)
Thus, the hypothesis that $\mu_i=\mu_j$ can be rejected if we observe $0\not\in I_{i,j}$.

Now, if the variance is unknown, we instead define $Q=R/S$ where $S$ is a certain estimator of the variance.
An important point is that we want to understand the joint distribution of $R$ and $S$, which is easiest if they are independent.
We do have an estimator of $\sigma^2$ that’s independent of the $W_i$, namely the residual sum of squares (a.k.a. sum of squares for error),
$$
\mathrm{SSE} = \sum_i \sum_j (Y_{i,j}-\overline Y_{i+})^2
$$
So we take $S^2$ to be a suitable constant time $\mathrm{SSE}$.
Namely, we want $S^2$ to be an unbiased estimator of $\sigma^2/r$, the variance of $W_i$. And we know that $\mathrm{SSE}/\sigma^2$ is $\chi^2(rk-k)$ distributed.
This leads us to define
$$
S^2 = \mathrm{MSE}/r
$$
where $\mathrm{MSE} = \mathrm{SSE}/(rk-k)$.
A point here is that $\mathrm{SSE}/\sigma^2$ is a sum of $k$ independent $\chi^2(r-1)$ random variables (one for each $i$), hence is itself $\chi^2(rk-k)$.

The Complexity Option Game

2014 M.A. graduate Malihe Alikhani completed her Master’s project on American option pricing and optimal stopping for success runs. She participated in the Cornell Summer School in Probability 2014.

Her project constitutes one of the parts of the new paper Pricing Complexity Options, which appeared in
Algorithmic Finance, 2015.

Entry at IOS Press

The best version of the paper is at arxiv.org

The ideas are implemented in the Complexity Option Game!