北海道苫小牧市出身のPGが書くブログ

正しいのになぜかみんなが「変だ！」という問題にPerlで答えてみた

perl, math

正しいのになぜかみんなが「変だ！」という問題：　x,y,zを自然数とする。このとき、x=3ならばy=5になる。あるいは、y=5ならばz=8になる。

@noricoco

これは良問！さすが @noricoco 先生 > RT

@hyuki

Perlで解答するとこうだろうなあ。 perl -e 'for my $x(0, 1) { for my $y (0, 1) { for my $z (0, 1) { ($x && $y || !$x) || ($y && $z || !$y) or die } } }'

@hiratara

続きを読む

ツイートする

Permalink | コメント(2) | トラックバック(0) | 10:55

今日はPRML復々習レーン kick-off meetingの日です

レポート, PRML, math

1年前に挫折したわけですが、一応もう一回来てみました。適当にメモします(キックオフなので打ち合わせ中心だと思いますが)。

ご挨拶 / @naoya_t さん

• 今日はエクストリームリーディングします
• 自己紹介タイム
• 今後は幹事役を分散したい
  • 会場安いとことか募集
• 全員に発表してもらいたい → 発表しないと身に付かない
• グループ分けして1章〜2章をエクストリームリーディングしましょう
• 暇な人は演習問題を(答え有り)
• 休憩

1章の黙読

各自15分程度目を通す。

• 1.66の導出はベイズの定理から形式的に出てくる？
  • 暗にグラフィカルモデルを考える必要がある？(以降の章で出てくる)
  • ここでαとβはハイパーパラメーターで確率変数ではない(独立性の問題)
  • 適宜、常識的な範囲で独立性を補わなければ出ないのではないか
  • 機械形式的に1.66を出せる人は教えて下さい！
• 1.6の情報量は何に使うの？
  • EMアルゴリズムで
  • ロジスティック回帰でもちらっと
• 1.68は解析的に解ける？ 最終的に求まる分散1.70と1.71はよく使う式？
  • 宿題。実際はgnuplotとかが勝手にやってくれる。導出の仕方を覚えておくことはよい。

2章1節の黙読

各自10分程度目を通す。

• 共役性の定義は？
  • パラメータを置き換えれば一致する、程度で

2章2節の黙読

• 機械学習などで事前分布に共役な分布を選ぶ理由は？
  • 悩まない、ということは1つの手
  • 自然言語処理だと頻度分布とかを選んだ方が精度が高いんじゃないか → αを非対称にすればOK
  • 計算の都合だけど、絶対そうしなければいけないという理由はない
  • 過学習と関係ある？ → 事前分布のご利益としては。ただ、他の分布でも一緒。
• 十分等計量のありがたさは？
  • 後で出てくるので割愛
• ベータ分布のμのハイパーパラメータ
  • 4〜5個のサンプルで初めて、いいところを探している
  • 極所解に落ち入らない？
  • 過学習は気をつけているけど、ベストかは不明
  • データが多くなると、パラメータチューニングで苦労するという印象はある
• β分布やディリクレ分布は事前分布以外に使い道があるのか。μを使ってるのが気持ち悪い
  • 後でxを使ってるので。
  • 知ってる範囲では使ってるところは見たことがない
• P.76 の有効観測数は α_k - 1 では？
  • 恐らくそうでしょう
  • となると、α_k が 0.1 の場合に有効観測数が負になる。これはどう解釈すべき？

2章はしっかりやりたいので、次回以降に持ち越して担当決めて腰据えてやりましょう。

来月は2.3のガウス分布から2章最後まで。3章頭もやるかも。

発表スライドであらすじ、質疑を中心で。

発表時間は5分程度でも、重要と思った箇所は長い時間でも。読んでること前提でOK。

本レーンは1枠1時間程度(今回は本レーンよりだいぶ細かく切ってる)。

来月分の割当を完了。

ツイートする

Permalink | コメント(2) | トラックバック(0) | 13:43

逆FizzBuzz(Inverse FizzBuzz)の正規表現書いた(解けてないけど)

perl

ええ、そうなの！？ と思ったので深追いしてみた。

逆FizzBuzzって、オートマトンなので正規表現を使うと楽に出来るはず。

Perl で 逆FizzBuzz

状態遷移図を書いてみるとこう。

ほんとは1〜15まで全て状態を書いて、ε遷移を加えてεの長さも1とした最少の単語を見付けなければならない。

で、これをこのPDFの方法で正規表現に書き直してみる。だるかったのでfizzはF、buzzはB、fizzbuzzはZにしておいた。

my $reg_inv_fizzbuz = qr/^(
    (((((F?B)?F)?F)?B)?F)?Z
    (FBFFBFZ)*
    (F|FB|FBF|FBFF|FBFFB|FBFFBF)
    |(((((F?B)?F)?F)?B)?F)?Z
    |((((F?B)?F)?F)?B)?F
    |(((F?B)?F)?F)?B
    |((F?B)?F)?F
    |(F?B)?F
    |F?B
    |F
)$/x;

これでfizz buzz の列について回答が存在するか否かは判定できる。ただ、正規表現に変換してしまった時点で各遷移の重み付けの情報は飛んでしまったので、逆fizzbuzzの解答にはならなかった。

おしまい。

【追記】

正規表現は使ってないけど、一応automata的な解答は作っておいた。もっと簡単にかけると思ったら思ったより面倒。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 16:36

今日は Akasaka.scala 36 の日です

レポート, scala

Akasaka.scala 36に途中から参加してます。タグは#akskscalaです。

Scala言語仕様読書会8 / @seratch さん

6章の後半。

• 前置、中置、後置演算
  • :が右結合なのはなぜ？ → ::のため
• 代入演算子

play2.0について / @seratch さん

• play コマンド
  • sbtのラッパー (sh/bat)
  • play new hello-play → 1 - Create a simple Scala application を選ぶ
  • play run → 9000ポート
• 参考資料
  • 公式ドキュメント
  • Play20/samples/scala
  • Google Groups の [2.0] つきのスレッド
  • StackOverFlow の playframework-2.0
  • #playframework, #play_ja

ツイートする

Permalink | コメント(0) | トラックバック(0) | 19:30

95%の信頼区間とは

math, scala

10000本のクジにx本の当たりが入っているとする。ここから100本のクジを引いた結果を元に、当たりクジが何本入っているか区間推定したい。

非復元抽出なので厳密にいえば100本中の当たりクジの本数yは超幾何分布に従うが、抽出する数と比較して全体数が大きいので二項分布で近似して良いだろう。さらに引いたクジの本数も十分に大きいので、正規分布として近似できる。

当たりくじの割合がp = x / 10000でそこから100本クジを引くのだから、確率変数yが二項分布だと考えれば平均値は100p、分散は100p(1-p)となる。これを元に正規化した、(y - 100p) / 10√(p(1-p))は標準正規分布に従うと言える。標準正規分布であれば-1.96から1.96の間の値をとる確率が95%であるから、-1.96 < (y - 100p) / 10√(p(1-p)) < 1.96 をpについて解けば*1、pがその範囲内に入る確率は95%であるということになる。これが95%の信頼区間。

見方を変えれば、この方法で推定すると、5%の確率で外れるってことになる。本当かどうか、シミュレーションしてみる。100個を無作為抽出してそこから95%の信頼区間を求めるという試行を1000回やって、実際の確率pが信頼区間に入った回数、入らなかった回数をカウントしてみる。

import scala.math._
import scala.util.Random._

val n: Int = 10000
val x: Int = 4321
val p: Double = x.toDouble / n.toDouble
val sampleN: Int = 100
val count: Int = 1000

val population: Array[Boolean] =
  (1 to n).map(n => if (n <= x) true else false).toArray

def square(x: Double) = x * x

def randomSampling[T](x: Seq[T], n: Int) = {
  val shuffled: Seq[T] = shuffle(x)
  shuffled.take(n)
}

def solveQuadratic(
  a: Double = 1, b: Double = 0, c: Double = 0
): (Double, Double) = {
  val hanbetu = sqrt(square(b) - 4 * a * c)
  ((- b - hanbetu) / 2.0 / a, (- b + hanbetu) / 2.0 / a)
}

def estimate (samples: Seq[Boolean]): (Double, Double) = {
  val n = samples.length
  val x = samples count {x => x}

  solveQuadratic(n + square(1.96), - 2 * x - square(1.96), square(x) / n)
}

val results = (1 to count).map { _ =>
  val sample = randomSampling(population, sampleN)
  val (min, max) = estimate(sample)
  if (min <= p && p <= max) true else false
}

println(
  "hit: %d, miss: %d" format (
    results count {x => x}, results count {x => ! x}
  )
)

結果は以下の通り、やはり5%は推定に失敗するという結果になる。

hit: 952, miss: 48

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:22