2015年に読んだ面白論文紹介場所参加記事です。 例によって、2015年に発表された論文とは限りません。私が去年読んだ中からの選抜です。 また例によって、人類の科学史における重要性とかそういったことに興味はないので、 単純に自分にとって読んで面白かった、これを読む前と後では物事の考え方が変わったなあ、 と思った論文を選んでいます。
☆ Newtonian Program Analysis
☆ Quick Detection of High-degree Entities in Large Directed Networks
☆ An Axiomatic Characterization of the Hirsch-Index
の３本立てです。
In Journal of the ACM, 2010. [著者版PDFはこちら]
Newtonian Program Analysis https://t.co/ApWi9AneOh 読んだ＆面白かった。方程式を数値計算で解く時とかに使うニュートン法を、掛け算と足し算しかできない（=引いて割って極限取って微分とかできない）世界でも使える形に魔改造してやる。(続
─ kinaba (@kinaba) 2015, 10月 21ニュートン法 というアルゴリズムは聞いたことがある方も多いと思いますが、例えば
x2 - 2 = 0
という方程式の解を求めようと思ったら、f(x) = x2 - 2 として、適当に x=4 くらいから始めて、
という感じで、数値計算で方程式の近似解を求める手法です。上に例示したステップで強調したように、 普通ニュートン法というと、引き算 や 割り算 や 微分 を何度も適用していく計算法です。
さて、この論文はニュートン法に対する 縛りプレイ に挑戦した記録であります。すなわち、 引き算も割り算も使わずに、足し算と掛け算だけの世界でニュートン法を実行する ということをやっています。 数学的に言うと、ω-continuous semiring 上でニュートン法を定式化し直した、ということだそうです。
なぜそんな縛りプレイがしたいのか？というと、実数以外の… そもそもやりたくても引き算や割り算ができない対象に関する方程式を解く道具として、 ニュートン法を使いたいからなのです。具体的には、集合演算。 例えば集合の∩(共通部分を取る演算)と∪(合併を取る演算)は分配法則を満たすので掛け算と足し算みたいなものですが、 これを使って書かれた X = Y∩Z ∪ T みたいな方程式を解きたい。 この手の集合演算による方程式は、 データフロー方程式 という形で、コンパイラの内部で最適化などをするときに頻出します。（どの変数がどの辺りまで生きてる、とか、 この文より前に確実に実行される文はどれ、などの解析。） 一般的なデータフロー方程式の解き方は、とりあえず初期値として X=空集合 や Y=全体集合 あたりから始めて、 方程式に従って右辺の計算して左辺に代入して更新的な作業を収束するまで繰り返すのですが、 ニュートン法でこの収束を加速するのが目的になります。
具体的な足し算と掛け算だけでの実現法は…論文を読んでのお楽しみということで。
この論文は何で読もうかと思ったかというと、 @ranhaさんが参加していてフィジーで死ぬとかtwitterで発言している LPAR という会議、 どういう所なんだろう、と思って過去のLPARの論文集読んでたら、参照されていたとかでした。 ニュートン法を初めて自分が知った頃は、 何かアルゴリズムを見たら代数構造抽象化してみるみたいな発想が自分にはまだなかったとは言え、 後々今に至るまでこういうことができると考えてみたこともなかったので、なるほど面白いなあと思いました。
論文 http://t.co/sgC7ic8Wxd 読んだ。グラフ全体を読まずに少数の観測だけで次数の高い頂点を見つける劣線形時間アルゴリズム、言い換えると雨にも負けず厳しいAPI制限にもめげずにTwitterの人気アカウントランキング作るアルゴリズム。
─ kinaba (@kinaba) 2015, 1月 8IEEEのデータマイニングの国際会議で発表された論文で、 Yandex というロシアで最強の検索エンジンの会社のチームによる研究のようです。 グラフ構造が与えられた時に、次数の大きい頂点トップ100を求めよう！というのは、 グラフを全部読んでいいのなら、単に辺の本数を数えるだけなので、線形時間で実現できます。 しかし、グラフのほんの一部しか見ることができないとしたら？ それでも高次数の頂点を見つけられるか？という問題。
こういう、全体を一舐めするよりも速く、線形よりも速いオーダの時間で答えを出そうというタイプの問題が、 アルゴリズムや理論計算機科学の分野でよく研究されていること。それ自体は知識として知ってはいたのですが、 正直、でも、現実にそういう問題と繋がらなくてイマイチ実感が湧かないなあ…と思っていました。 それが、この論文の対象が滅茶苦茶わかりやすい応用だったので、目から鱗が落ちた次第です。 つまり、「Twitter の API 呼び出しって回数制限があって、とても全ユーザの情報をクロールはできないけれど、 それでも Twitter の人気ユーザーランキング作りたいのだ！」という。わかる。 言われて見れば当たり前なのですが、API limit がありますという状況はなるほどこの手のアルゴリズムが欲しいです。
提案されているアルゴリズムは実にシンプルで、例えばAPIリクエスト上限が1000回だとすると、
で、トップ500人気ユーザを近似的に求めるというものです。かなり上手く行くらしい。 どんなグラフでも上手く行くわけではなく、人間関係から作られたグラフ構造、いわゆる Social Graph の特徴的な性質を使うと、少ないクエリ回数でも精度良く求められることが証明もされています。
面白いなーと思ったのが
TwitterはユーザIDが自然数連番なのでランダム抽出ができて有難い、というのが面白かった。１ユーザから始めてクロールする系の手法よりだいぶ強いらしい。なんかウェブAPI作る時は問題なければ特に用途考えずランダム抽出API作っておくと乱択アルゴリズム神が神応用考えてくれるのかも
─ kinaba (@kinaba) 2015, 1月 8この辺り。「ユーザーをランダムに抽出する」という部分は上記のアルゴリズムで必須の部分で、 誰かのfollower/followingを辿ってクロールするなどでは偏ってしまって、あまり旨くないらしい。 明示的にそういうAPIがあることってあんまりないですが、 Twitterの様に自然数連番（やめたユーザやアクティブでないユーザに当たる部分はそんなに影響しない、 と論文にはありました）だと使う側が勝手にやれてよかった、というのは、これも言われてみるとなるほど。
In Mathematical Social Sciences, 2008. [著者版PDFはこちら]
http://t.co/mvRMXt2DBN の続きでh-indexの公理化の論文色々読んでた。引用数のmultisetを単一の数にマップするindexはこういう性質を満たすといいな、という条件を幾つか集め、例えばこれとこれを満たす関数はh-indexしかあり得ぬ、的に特徴付ける
─ kinaba (@kinaba) 2015, 6月 23Hirsch-index (h指数) というのは、研究者の凄さを表す尺度の一つで、 ある研究者が「n 回以上他の研究から引用された論文を n 本書いている」なら、その人のh指数はn以上になる、 というものです。
例えば Google Scholar によると Kazuhiro Inabaさん の現時点でのh指数は 7 で、7回以上引用された論文を7本書いている （が、8回以上引用された論文の数は8に満たない）ということを表しています。 本当かなこれ、もっと少ない気がするんですが、まあいいや。 凄い計算機科学者、例えば チューリング のh指数は84だそうです。
h指数は、一本だけ突出して引用数の多い論文があっても、増えません。 逆に、ものすごく大量に論文を書いていても、どれも全く引用されていなければ、増えません。 「いろいろなところから参照される良い論文をコンスタントに何本も書いている」ということを評価する軸です。 野球にも打率とか本塁打数とかOPSとか色々な指標があるように、h指数も、 あくまである一つの側面からの評価で、これが絶対唯一の評価軸というわけでは、 勿論ありません。時と場合に応じて適切に解釈する必要があるでしょう。
この論文は、ある意味、その「時と場合」から逆に h指数を特徴づける、 というアプローチです。すなわち
- 公理B: １つの論文の引用数だけがどれだけ増えても、その著者の指数は精々 1 しか増えない (※「一発屋」ではほとんど増えない)
- 公理A1: 指数が既に x ある人が、新たに論文を書いてそれが x 回引用されても、指数は増えない (※引用数の少ない論文をたくさん書いてもほとんど増えない)
- 公理D: 指数が既に x ある人が、新に論文を書いてそれが(x+1)回引用されつつ、 しかも既存の論文の引用数も全部 1 ずつ増えると、さすがに指数は増える (※引用数も本数も増やせば、さすがに増える)
この３つの条件を満たす自然数値の指数が欲しければ、それは h指数しかない、ということを証明しています。 元々の「n回以上がn本」というちょっとトリッキーな定義は、噛み砕くと、 上に３つ上げたような評価軸を同時に反映する唯一の方法だった、というわけです。
これは
前から知りたいのが、この簡潔な定義を保ったまま"引用回数"を何かのランキングでの"順位"に置き換えたバリエーションてどう作ればいいんだろう、と。まぐれで一度だけ1位とったことがあるが普段は三桁順位安定な人より、最高こそ3位でもそこそこ頻繁に一桁台に登場する人の方が良くでる定義。
─ kinaba (@kinaba) 2015, 6月 16引用数のように「多い方が良い」ものではなく、 順位のように「小さい方が良い」ものに適用できるような h指数的な評価値ってないかなあ、 ということを考えていた時に教えてもらった論文でした。
一撃で天下り的に巧い指標を考えるんじゃなくて、こうであって欲しい、ああであって欲しい、 と満たして欲しい条件を列挙していく中で数学的に必然的に一つに絞る、 という発見の仕方ができたら、確かに納得感がありそう。面白い＆強力なアプローチだなと感心したのでありました。 （しかしその後そういえばすっかり順位版h指数を考えたいという疑問忘れていた…やらないと…）