過学習への対処 (てきとーなイメージ)
機械学習をするとき少ないデータ数ではよくわからない部分、というのは往々にして存在する。このとき、「わからん、困った」とか言うのがゼロ頻度問題だし、そんなこと気にせず突っ走ってアグレッシブな推定をする困ったさんが過学習である。ような気がする。
こういうとき、対処法は大まかに分けて2つくらいになるっぽい。
- より穏当なモデルを使う。より具体的に言うと、低次元のモデル、あるいはスパースなモデルを使う。
- 正則化とか情報量基準に基づくモデル選択とかなんかはこんな感じだよね
- 1個に定まるし、パラメータも少なくなるので割とシンプルで軽いイメージ
- サンプリングして組み合わせる。学習データを変えたり、学習器を変えたりで異なるものを幾つか平均とか何とかして組み合わせる。すると、わかりにくいところはばらつきが大きくなってボケた感じになってくれて嬉しい。
- bagging とか、boosting とか、random forest とか？
- 学習も遅くて消費メモリも多くなるイメージ
- Deep-learning はこれを狙ってる感
認知系でも exemplar model とか prototype model とかあって、それぞれに対応するっぽい感じがするし、割と自然なのかもしれない。
そういえば、1 は全体を同じ次数で表現するのは問題があるときが多くて、マッチ長を使う自然言語処理とかではよく見るけど、わからないところだけ低次のモデルを使う smoothing というのをよくやっているのを見る気がする。よく使われているところだと PPM とかそうな気がする。
ところで 2 でこれに相当するものってなんだろう? よくわからん。
英語
単語とか文とか作っているレベルだと言語によって違うけれど、その上に載ってる段落構成であるとか、文章全体の構成であるとか、そういったものは使用言語に依存するものではない。高次構造というのはまじめに調べれば違いがわかるのかもしれないが、閉じた社会で使われるものでない以上、それを維持できるような平衡状態に至るのは困難であるし、文などある程度大きな意味単位になればそれは単独で意味を持つものなので、文法とは切り離して他の論理により並び替えをすることもできる。どこに境界があるかとかは曖昧で明確に分けられるものではないけれども、上の方に行けば行くほどそういう傾向が強まるのではないかと思う。
そう考えると、日本語でできないプレゼンは英語でもできないし、日本語を学ぶ授業で教えないことを英語を学ぶ授業で教えるというのはトチ狂ってるなあと思うね。
傾向とは
プログラミングコンテストを運営する上で、傾向として考慮すべき点としては、
- ジャンル
- 難易度
があり、ジャンルは、
- 1問ごとのジャンル傾向
- 全体のバランス
と言った要素からなり、難易度の方は細かく分けると、
- ひらめき量: 大まかな方針が見えにくさ
- 考察量: 方針が見えたあとでの詳細を検討しないといけない量
- 実装量: 詳細が詰まったあとのコード量
に分けられて、さらに、それに直交して
- 既存のアルゴリズム成分 = ライブラリ分、知識力とか
- ad hoc 成分 = 自分で頑張る分、応用力とかロバスト性とかに対応
という分け方もできて、さらに、
- アルゴリズム・モジュールの段数: 組み合わせるパーツが増えればその分超線形で難しくなる
といった要素もある。単純に一言で表わされるようなステレオ・タイプで片付けていいものではない。
- F 問題は考察量・実装量が多い
- G 問題はひらめき量・考察量が多い
と見なせるし、
- 序盤はモジュールが 1 段で、
- C or D 以降は 2 段以上になる
と言った見方もできる。
さて、 D あたりだとどうかというと、おおよそ、
- グラフが役に立って
- まあまあ ad hoc 成分があり
- 2段以上の構成
という類型である。
普段よくある例としては、グラフの拡大を伴う最短路である。しかし、いくら出しやすいからといって、同じ種類を繰り返し出していればそれは ad hoc ではなく、やるだけになってしまうし、違う練習になってしまう。上の分析を全く満たせない。果たしてどんな問題を出すと良いのだろう？
今回の模擬国内 D だと、(ICPCの練習をした人ではなく) グラフを勉強した人だと最小全域木はそれなりに知られていて、単純に適用するだけでなく1ひねりアルゴリズムを変更する必要があって、さらに連結性を保つ時刻を前処理で求める部分まであって完璧である。難易度の見積もりも、解いたチーム数を例年と比較すると、若干少なめであるが誤差の範囲内で、裏付けも十分である。
この問題は(単品としてみれば)それなりに上手くいったが、ad hoc 成分というのはどこまでが該当するかは、選手層の実力によって変わり、年によって変動もある。さらに、老成してくれば、初心者にはそうは見えないものが似ているように見えてきてしまう。これらの要因から、全体としてインフレ傾向というトレンドはあるが、細かい見積もりは困難であり、往々にして見誤る。実際今年の B・C・E 問題はそうであった。それ以外に問題文が難しいということもあったが、それを抜きにしてもこの通りである。
近年は AOJ であったり、あり本であったり、選手が特急券を手にする機会が増えて、コミュニティも拡大したというのはいいことだと思う。しかし、そのせいか、他の人も自分と同じバックグラウンドを持って、同じような基準を持っていると勘違いしている人もいるように思う。誰が全域木の知識に比べて、最短路の知識は特別であると決めたのだろう？特急券を持った彼らの通っている道が基本的に過去の偉大な選手の切り開いた道にすぎず、自分自身はそれほど多くの年数の問題も見ていないし、後ろの方の問題も解こうとしていない、そんな状況下で掴んだ傾向なんて、単にテスト前日に山を張っているだけとどこが違うというのか。さらに言えば、その山が完全に当たった結果なんて調べてどうするというのか。過去のコンテストに極端にマッチさせた選手とか、いかにも汎化誤差が大きい選手育成して意味があるのか。これから、地区大会・世界大会へと羽ばたく伸びしろのある選手を選抜できるのか。調子に乗るな。傾向を踏まえるといっても限度がある。もっと広い視野を持て。よく知っている人の言い訳で通用するほど距離が近いものばかりになるとは限らない。
自省を促したい。
今回失敗した点に関しては十分反省し、質の向上に励みたい。しかしながら、それはわ某が主張するように気合でなんとかなるものではないし、某いが期待したように、放置しても妖精さんが裏でうまくやってくれてなんとなくうまくいくとか、そういうものではあってはならない。スタッフも少し長く生きただけで、能力に限りがある。目標を達成でき、かつ 持続可能な コンテスト運営を目指して、頑張りたい。
言語の普遍性?
言語学系だと色々普遍的な規則があるかのように言われているものがあるらしいけど, http://wals.info/ を見るだけで単に視野が狭かっただけってわかることも多かったような気がする.
それがいつまでも流布するのは, せいぜいが論文中の断片的な例文だけで現実のコーパスを横断的に見た人が少ないというような気がする. というより, レポートとかの構成法自体が, 過去の論文のサマライズが基本の世界だし.
来る日も来る日も Wikipedia を見続けた日々と比較してそれってどうなのだろう.
