運命の分かれ道、面接にたちはだかる「鶏の王」

KingChicken

こんにちは、シバタアキラです。白ヤギの経営に、カメリオのアップデートに何かと忙しい日々ですが、引き続きこちらのブログでもお話させていただきたいと思っています。

就職活動開始ということで、忙しい大学生の方もいっぱいいらっしゃることかと思われます。私は研究バカでしたので、いわゆる就活ということをあまりやって来ませんでしたが、これまで何度か就職面接を受けたことがあります。そのすべてを覚えているわけではないですが、中には強く思い出に残っているものもあります。成功しても、失敗しても、就職・転職活動は運命の分かれ道ですから。

本来であれば人の運命を決めることは神のみのなせることであると、不真面目に通っていたカトリックの学校で習ったような気がします。現在では仕事柄沢山の方と面談・面接することがあり、短い時間の中で正しい判断をすることはとても難しいことだと痛感しています。また、多くの方にとってこの短い面談の時間は後の記憶にも残る出来事になる可能性が高いため、候補者に与える印象、候補者との距離の取り方には気を使います。

私がこれまで受けた面接にはざっくり3種類くらいありました:

  1. 私の周りとの適応能力を図ることにフォーカスした面接
    こういう面接に私が受かったことはありませんでした
  2. 頭脳労働の現場で実際にある問題への解決能力を図る面接
    「ケース面接」などと呼ばれ、こういう面接は得意でした
  3. 非常に高度な問題に対するクリエイティブな解決力を問う面接

私の記憶に強く残っている面接は3つ目のタイプで、それには名前がついていました。”King Chicken”(「鶏の王」)という名前です。出だしからちょっと複雑です:

鶏が大量に飼われている牧場をイメージしてください。二匹の鶏のペアの間には固定の上下関係があります。強い鶏が弱い方の鶏の頭をつつくという関係を持っていて、その関係は変わらないという仮定です。一方で、この上下関係は「線形」ではない、と考えられます。つまり、AがいつもBを突き、BがいつもCを突くからと言って、Aが必ずCを突く関係にあるとは限らない、ということです。

そんな中で「鶏の王」を次のように定義します:
群れの中にいる鶏Kと他の鶏Cを考えた時、K→CのようにKがCを直接つつく関係にある、もしくは、K→F→Cのように別の鶏F一匹を介してCを間接的につつく(この場合、Kは直接はCに突かれる、C→Kの関係にある)という関係が、Kと他のすべての鶏に対して成り立つような場合に、Kを「鶏の王」と呼ぶ。例えば下図のような関係にある五匹の鶏の群れに関しては、C2は王です。C3,C4,C5を直接つつき、C1をC3を介して間接的につついています。

Screen Shot 2015-03-23 at 12.04.00 AM

(図はここから引用)

ここで問題です。あらゆる鶏の群れには「鶏の王」が存在するのでしょうか?

データサイエンティストの面接

これは、ニューヨークの某スタートアップに面接に行った時に出された問題でした。その時私を面接したのは、Cathy O’Neilというデータサイエンティスト。2008年の金融危機まで、D.E.Shawというニューヨークのヘッジファンドでデリバティブ(サブプライムローンなどに代表される複雑な金融商品)の開発を行い、その後転じて反ウォールストリート運動(Occupy Wall Street)などでも活動するようになった。現在はMathbabeというブログで知られ、最近までコロンビア大学でデータジャーナリズムプログラムのディレクターもしていたみたいです。

この問題は、グラフ理論、という比較的新しい数学理論の問題です。インターネットや、ソーシャルネットワーク等の巨大化とともにその重要性は現在も増しています。多分誰の役にも立ちませんが、この問題を華麗に解いて面接に合格する方法はこんなかんじです:

群れの中で最も直接つつく他の鶏の多い鶏Cを考えます。鶏の群れを、Cが直接突く鶏Sc(C→Sc)と、逆に直接の関係としてはCを突くDc(Dc→C)を考えます。

Screen Shot 2015-03-23 at 12.39.27 AM

(図はここから引用)

ここで、もしもCが王ではないと仮定します。そうだとすると、CからDcの中に間接的につつくことのできない鶏がいるということになります。そうだとすると、Dcの中にはScの中の鶏すべてをつつく鶏が居るということになります(そうでなければCは間接的にすべてのDcをつつくから)。しかし、Dcの中の鶏は、既にCを直接つつく関係にあるため、Scの中の鶏すべてプラス1匹をつつく存在になり、当初仮定していた最も直接つつく他の鶏の多い鶏Cと矛盾することになるのです。だからCは王である。証明終わり

このような問題が出てきてサラサラと解く人がいるのかどうかは知りませんが、データサイエンティストの面接でこんな問題が出てくるとは全くの予想外でした。そこで私はどうしたかというと、その場ではほとんどそれらしい解を出すことができませんでした。直感的には王は居るような気がしたのですが、それを証明する事ができず、結局5分ほどもごもごやって、助け舟をもらい、それでもわからず、15分ほどしてゲームオーバー。この時点でCathyと私の間にはどんよりとした空気が流れていました。

その場で彼女はこの問題の応用として、さらに2つの質問を出しましたが、それに関しても答えらしい答えは出すことができませんでした:

  • 非常に巨大な群れにおいて、鶏の王はどれくらい存在するのか?また(より現実的に)多くの鶏のペアは互いに出会うこともなく、つつく・つつかれるの関係が存在しないとしたらどうか
  • 実世界に存在するTwitterなどのネットワーク(少数の有名人が多くの人とつながるような、Scale Freeという種類のネットワーク)には王は居るのか

面接にリベンジはない

面接でこんな挑戦的な問題を出されたのは初めてのことで、私の心のなかは不気味に奮い立っていました。その後数日しても二次面接の連絡がなかったことは言うまでもありませんが、悔しさと興味から私はプログラムを書いていました。そして後日彼女に送ったメールがこれです:

Hello Cathy,
It was great to talk to you on Friday! I’d like to thank you for your time and interesting conversation.
One thing kept bugging me, about King Chicken, which I did somewhat poorly during the interview. Nonetheless, I was interested in exploring it a little bit further.
Towards the end of our discussion we talked whether king chicken can be found in the real-wold network such as Twitter. And if so/not so what conditions are necessary for king chicken to exist within a network…

モンテカルロ・シミュレーションの末に私が見つけたのは、

  • 30羽以上の群れにおいては、すべての鶏が王になる(これは面接中にCathyが言っていた)
  • 400羽以上の群れにおいては、60%以上のつながり(つつく、つつかれるの関係)を取り除いても、ほとんどの鶏が王になる
  • しかし、それ以上つながりを取り除くと、突然王の数が激減する

これを示したのが下の図です。X軸は群れの大きさ(3のX乗)Y軸は取り除くコネクションの割合。群れが大きくなると王の数が増える一方、つながりの数を減らすと突然王が減ることが色で表されています。

KingChicken_CompleteNetworkそして、より「現実的な」ネットワーク、ScaleFreeネットワークの場合は

  • 非常に小さい群れでなければ鶏の王は一匹も存在しない
  • ネットワークのつながり率を増やしても王の数は増えない
  • 王の定義を拡張して、4匹を経由した関節的なつつきを考慮に入れたとしても、王の数はほとんど増えない

ということがわかりました。それ(一番最後のポイント以外)を示したのが下の図です。

KingChicken_ScaleFreeNetwork_Rank4これだけやったらなんか返事が帰ってくるだろう、という期待も少なからずありましたが、結局彼女から返事が来ることはありませんでした。多分彼女にとっては候補者が鶏の王を華麗に解くのかはそんなに重要なことではなかったのかもしれません。

これは世の常ですが、一度もらったチャンスを逃すと、二度目に相手を振り向かせるのはとてもむずかしいことです。後から何とかしようとするくらいならば、どうやって一発でヒットを打てるのか、それにかけなくてはいけません。だからこそ面接は、その人の真価が問われる時であり、運命の分かれ道となるわけですね。

白ヤギでもいろいろな問題を出題し、候補者の力量を測っています。どのような問題を出せばより正確な判断ができるようになるのか常に試行錯誤していますが、いつかは鶏の王をスラスラと解き、物足りなそうな顔をするような候補者が毎日現れるような会社を作りたいと思います。

そして白ヤギでは自分たちの力でサービスを作ることを大切にしている、スバラシイチームに加わりたい方を大募集中です。詳細はWantedlyを御覧ください。