「人間中心のAI社会原則検討会議」に参加しました。

土井 裕介

2018-05-10 15:39:51

5/8に開催された内閣府主催の「人間中心のAI社会原則検討会議」に出席してきました。

土井と申します。普段は細々とネットワークの研究を行いつつクラスタ関係とりまとめをやっています。出身大学がinterdisciplinaryなところなので、いろいろな領域に首を突っ込んでいます。そのような活動の一環で、社内のslackにAIと社会に関して考えるチャネルを作り、PFNフェローの丸山を中心として何人かの興味あるメンバーとで、社会動向のウォッチングや、必要な意見表明[1]などをしています。例えば、2017年頭に「AI開発ガイドライン(仮称)」へのパブリックコメントをPFN名で提出しましたが、そのパブリックコメントの最初のドラフトは私が書いたものでした。

そんな中、弊社丸山が掲題の「人間中心のAI社会原則検討会議」にお誘いいただきました。ただ、丸山は残念ながらこの日に外せない終日の予定が入っており、代理で土井が参加してきました。参加にあたり、PFNの意見を事前に文書でまとめるようにしたほうが良いだろう、とのことで、「『人間中心のAI社会原則検討会議』に対する意見」[2]としてまとめ、会議に提出しました。あくまで参考資料としてではありますが会議で配布されたので、こちらでもご紹介させてください。

この文書は特に何か難しいことが書いてあるわけではなく、「人工知能」または「AI」と呼んだ時にそれが何を指し示すのかを明確にして議論しないといけない、という話と、ある前提で議論した内容を別の前提に適用するとおかしなことになりますよ、という当たり前の話が書いてあるものです。

PFNとして提出した文書には、世間で「AI」として議論されている内容は主として以下の3つに分類できるのではないか? としています。

  • A. いわゆる汎用人工知能
  • B. ネットワーク化された情報システム
  • C. 機械学習システム

AとCはみなさん何となく理解されるかもしれませんが、これらを混同しているような議論も多いです。ただ個人的には、案外「AI」の文脈でBの話をされる方が多いことに驚いています。例えば証券市場のFlash Crash(自動取引による証券取引の不安定化)を「AIがもたらす問題」として挙げる方がいます。実は、今回の会議の委員にもこういう考えの方がいらっしゃいました。ただ、いわゆる単純なフィードバック制御であっても発散してしまい問題になるケースがあるのと同様、これはソフトウェアによる自動化とこれにともなう高速化、およびその影響範囲を拡大するネットワーク化に起因する具体的な問題です。PFNとしては、こういった問題をわざわざ「AI」などというあいまいな単語を使って議論する必然性はないと考えています。

また、会議の中でタイミングがなく発言できなかった内容をひとつ。「AI」が主語になった議論は個人的にはとてもおかしな議論に見えています。[3]でも書きましたが、上のABCどの定義であっても「AI」の中核はソフトウェアとして実現されます。現実の世界に何かの影響を与えるためには例外なく人間が与えたハードウェア(ソフトウェアを実行させるコンピュータ、コンピュータに供給される電源、外界と作用するためのセンサ・アクチュエータ、等)が必要です。言い換えると、どんな場合であれ「AIの性質を持つソフトウェアを構成要素として持つ何らかのシステム」があってはじめて議論がスタートします。システムには、通常「AI」とはみなされない、様々な技術や安全装置が含まれていて、それらと外界との作用の総体でシステム全体が機能します。我々が考えるべきは、このシステム総体が、人類社会とどのように調和していくかではないでしょうか。個人的には、PFNが機械学習の本質を理解して新しい学習の仕組みを作るように、社会も機械学習やAIと呼ばれる技術・仕組みの性質や限界を理解して、きちんと使いこなす、つまり社会システムの構成要素として人間がAIを主体的に位置付けることが、あるべき「人間中心のAI社会」の姿なのではないかと思います。

今回議論していて「なるほど確かに」と思ったのは、本来AIというのは知能を機械で模倣することで知能を理解しようとする研究の営みあるいはその研究分野を指すことばであった、という点です。これを、特定の機能や製品のラベルに転用した結果、現在はあいまいな単語となってしまいました。ことばは本来他者とのコミュニケーションに用いるものである以上、あいまいな単語を用いた議論では精度が出ません。いくらAIという冠をつけると見栄えが良いからといって、このあいまいさに無自覚なままAIということばにふりまわされた議論を重ねても何も得られません。この機会を有意義な成果につなげるために、引き続き社内でも議論を深めていこうと考えていますし、また議論の立脚点となるべき事実についても情報発信を続けていこうと思います。

references
[1] 人工知能技術の健全な発展のために
[2] 「人間中心のAI社会原則検討会議」に対する意見
[3] ソフトウェアとしての人工知能に関する論点整理 信学技報, vol. 117, no. 471, SITE2017-75, pp. 209-212, 2018年3月.

コミックマーケット93 参加レポート

Taizan Yonetsuji

2018-02-06 11:33:30

コミックマーケット93

PFNでは、2017年12月29日から31日まで、東京ビッグサイトで開催されたコミックマーケット93に我々が開発しているPaintsChainerの企業ブースとして出展してまいりました。

年末にも関わらず、非常に多くの方々にご来展頂き、3日間で1000人を超える方に、プロジェクションマッピングを用いた新しいユーザーインターフェースを体験いただきました。

また、PaintsChainer公式キャラクター「絵愛ちえな」ちゃんのお披露目も行う事が出来ました。


PaintsChainer(ペインツチェイナー)とは

PFNが開発・提供するオンライン線画自動着色サービス。白黒等で描かれた線画ファイルや写真画像をアップロードするだけで、イラスト上の顔や服装、風景等を認識し、完全自動着色または色指定による自動着色をおこないます。

線画に対する自動着色のWebサービス化は世界初で、大きな反響を頂きました。その後、モデルの追加やサイトのリニューリアル等に取り組んでいます。

https://paintschainer.preferred.tech/

 

プロジェクションマッピング上での自動着色

今回のコミックマーケット93のPFNブースでは、紙に書いた絵に色がつくという新たな体験を提供しました。

デジタルデータではなく、実際の紙に描いた線画を専用着色ブースにセットすることで、その線画を4K高画質カメラで読み込み、PaintsChainerが着色し、プロジェクションマッピングを用いて実際の紙に着色されたように投影しました。実際にその場で書いた絵を着色できるということで、時間をかけて力作を描いて下さった方々もおられました。

さらに、着色結果にカラーヒントを与えることで、好きな色に変える機能もプロジェクションマッピング上で提供しました。

例えば、自動着色で黄色に塗られた髪の色を、カラーヒントを与えることにより一瞬にして青や赤など好きな色に変えることができます。

こちらは、もともとWeb版のPaintsChainerにも搭載されている機能ですが、今回は投影により着色された線画紙自体に、絵の具や色鉛筆で着色するかのように色指定ができるインターフェースに作り変えました。こちらもまるで魔法のようだという事で非常に楽しんでいただくことが出来ました。

 

スタイラスペンによって線画に対し直接カラーヒントを与えられるようにし、認識は、テーブルに埋め込んだペンタブレットにて行っています。

 

マンガ向けの着色モデルを限定公開

通常のイラスト向けの着色モデルに加えて、コミケ会場ではマンガ向けの着色モデルも選択できるようにしました。こちらは、今回が初公開のモデルです。

マンガ向けモデルは、Webで無料公開しているイラスト向けモデル(現在は、「たんぽぽ」「さつき」「かんな」の3つのスタイルを公開中)とは異なる学習を行い、マンガが持つセリフ、吹き出し、枠といった特徴に適した着色モデルとなっています。


イラスト用さつきモデルで着色(ノーヒント)マンガモデルで着色(ノーヒント)

(ブラックジャックによろしく 佐藤秀峰 Give My Regards to Black Jack SHUHO SATO )

こちらのマンガモデルは、現在出版社・デジタル配信事業者と共に実用化を目指しています。

 

漫画版は公開利用行っておりませんが、通常のPaintsChainerの3モデルは今回コミックマーケット93で体験いただいたものと同じものがWeb上で無料でご利用頂けます。是非ご利用ください。

https://paintschainer.preferred.tech/

Amazon Picking Challenge 2016 ~ドイツ・ライプチヒにて~

神谷保徳

2016-09-02 16:25:17

神谷です。

7月上旬、ドイツ・ライプチヒで開催されたAmazon Picking Challenge(以降APC)に、PFNとして参加しました。これは、Amazonが主催しているロボット競技会で、Amazonの倉庫内に在庫された商品から、購入された商品を棚から集めるタスクの自動化を想定した競技です。今回で2回目で、前回からのタスクである、指定された商品を棚からロボットで取得しカゴに入れるPickタスクと、新しく加わった、カゴに入っている商品を棚に入れるStowタスクの、二つのタスクがあります。Pickタスクは、前回から商品の種類や難易度も上昇しています。

実際に我々が作り上げたシステムの技術内容に関しては、PFI&PFNセミナーで概要ではありますが既に発表しており[1][2]、また日経Roboticsに弊社システムの解説記事や弊社岡野原のコラム、APC全体の技術解説も載る予定ですので、今回はドイツ・ライプチヒにおいて、実際に我々がどんなことを行っていたか、旅行記風に紹介しようと思います。


6/28、お昼頃、会場入りしました。スーツケースをたくさん持っているのは、手持ちのロボット部材や、工具があるためです。ぎりぎりまで開発を行っていたため、手持ちとなった物が多くあります。
DSC01675

輸送されたロボットアーム達。実は、輸送に時間がかかるため、本番用ロボットアームは先に送り、直前までの開発には別のロボットを使用していました。それにまつわる様々なトラブル回避もありました。そうまでしたのは、それだけ短期間での開発だったためでもあります。
DSC01691

箱開け。きれいに、きっちりと梱包されています。ぎりぎりまでの輸送タイミング交渉、また税関など、この輸送自体に関してもかなりの問題解決/回避が行われました。
DSC01701
DSC01699

設置の様子。設置に関しても準備を凝らしていましたが、それでも電圧の違いによるトラブルが少しありました。ロジスティクスの方と協力し、短時間で完了しました。
DSC01707

本番前々日
設置後、調整と改良が続きました。
本番前の調整では、奇跡的に隣にあった、ホームセンターが大活躍しました。例えば、照明条件の違いから、ライトを購入したり。ロボット競技では、現地でのイレギュラーがつきものです。
DSC01840

本番前日
調整と改良を続けます。
DSC01847

また、Amazon.deの見学にも行きました。
DSC01775

試走のスケジュール表。試走では本気を出していない(動作の確認に徹している)チームもあり、まだまだ分かりません。
DSC01789

本番直前。ぎりぎりまで改良を行いました。
DSC01999

そして本番。オレンジのTシャツの人が、Amazonの委員の人です。ターゲットのアイテムと、棚内のアイテムの配置は数パターンあり、くじで選択する形です。委員の人がアイテムを慎重に配置していました。また、棚のずらしも、配置前に行われます。
DSC02006

本番中。ハラハラドキドキ。本番のロボットの動作の様子はYouTubeに上がっています[3]。
DSC02007

終わりました。幾つかミスはありましたが、満足のいく動作でした。
DSC02009

そして表彰式
DSC02015

表彰式後の一コマ
DSC02018

その夜のパーティ。みんな笑顔。
他のチームの方やAmazonの方ともいろいろなお話をしました。
DSC02026

次の日はデモです。試合までは調整であまり見られなかった他チームのシステムについて、拝見、質問をしました。我々が開発中に気付かなかったアイディアも幾つかありました。また、我々のシステムについてもいくつも質問を受けました。
DSC02036

お片付け。ロボット達はまたPFNに戻ってきます。おつかれさまです。
DSC02038



この数か月間、非常に大変でしたが、結果も伴い、とても良い形となりました。
DSC02011

—————————————————————————
[1]http://www.slideshare.net/pfi/amazon-picking-challenge
[2]https://www.youtube.com/watch?v=gqcO8ZX0jB8
[3]https://www.youtube.com/watch?v=w7NgejZMSsA

Deep Learningと音声認識

preferred

2015-07-16 13:00:10

西鳥羽です。こんにちは。

本日セミナーで「Deep Learningと音声認識」という内容で(ustreamで公開されているけども)社内セミナーで紹介させて頂きました。タイトルは前回の「Deep Learningと自然言語処理」に被せてます。

Broadcast live streaming video on Ustream

こちらがその資料になります。尚、セミナーでは「話し言葉コーパス」とすべきところを「書き言葉コーパス」としてしまっていました。資料では訂正してあります。

また、個々の参照は以下の通りです。

CTC関数に関しては以下が詳しいです。Chainerで実装してますがちゃんと動くようになったら公開したいですね。

100倍で考える

岡野原 大輔

2014-10-06 15:21:11

私が最近強く印象に残った言葉が10倍で物事を考えるです[wired]。
これが私の記憶の中で拡大解釈され、今は100倍で物事を考えるようになっています。

「100倍」というのは一見すると不可能なことの例えのように思えますが、決してそんなことはありません。

どの程度現実的か例をあげて考えてみましょう。

DWH(DBと考えても良いです)という分野を考えてみます*1。

*1 この分野は専門家ではないのであくまで外から見ている素人の意見です。

2014年10月現在 Google BigQueryは1GBの保存に月あたり 約3円、クエリ時1TBスキャンあたり500円という価格設定です。基本的なDBの操作は全部できて、その上でユーザーが自由に関数を定義できて、画面とつながって結果が数十秒で返ってきてです。これはこの分野を知る人にとっては衝撃的な価格です。

1昔前、DWHの世界では製品が数千万から数億円という範囲で売られていました。別に価格を不当に高く設定しているわけではなく、提供するためにそれだけのコスト(研究開発費、ソフトウェア開発費、サポート費など・・)をかけているため、このような高価格にベンダーは設定し、また他にできる製品もないためこの値段設定でもどんどん売れていました。

その後、Hadoopをはじめとして様々なOSSやそれを元にしたサービスが登場し、DWHの価格は急速に下がっていきます。Amazon Redshift(名前からして、高価格な赤色の製品を意識していると思います)がでてきた時、これはすごいのがでてきたと思った記憶があります。しかし現在のGoogle BigQueryはそんなRedshiftさえ一昔のものと思わせてしまうような機能、価格、先見性(配列を自然に扱えたり、許可さえあれば違うユーザーのテーブルとJoinできたりするなど)があります。

このDWHという世界では10年ぐらいのスパンでみれば1万倍以上の価格性能比の改善がみられました。おそらく今後もAmazonとGoogleの巨人たちが競争する限りコストは下がり機能は向上し続けるとみられます(囲い込むため殆ど無料に近いところまでいくのではないかとも思います。)

では、なぜ100倍のようなスケールでの変化が可能なのかを考えてみましょう。

ビジョナリー・カンパニー2という本で弾み車の例がでてきます。
弾み車は一度回し始めると惰性である程度は回るような車です。なので小さな力を同じ方向に与え続けると時間はかかりますが巨大で重い弾み車であっても高速に回すことができます。
企業や製品の中でも全く同じことが言えます。同じ方向に小さくても力を継続的に与え続けることで、外からみるといつの間にか革新的な変化が起きているように見えるのです。100倍という差も小さな変化の積み重ねで達成されるのです。

それでは、具体的にどのくらいの改善を積み重ねられれば100倍を達成できるかを定量的に見積もってみましょう。目標としている性能を1日あたり1%向上できるとします。1日目には1.01倍、2日目には1.01 * 1.01 = 1.0201倍です。1%を加えるのではなく、掛けるところに注意してください。

このペースで100倍の性能向上を達成するにはどれだけの時間が必要になるでしょうか。これは私自身計算して驚いたのですが、たったの460日です。週5日でやったとして約2年です。毎日1%改善すれば、2年後には100倍の差になって現れます。(この別な説明として収穫加速もありますが、ややこしくなるのでこれはまた別の機会に)

方向を明確に定めてそこに集中して弾み車を回し続けることで加速的に改善することで100倍のスケールで改善することができます。ここにコツコツ努力を積み重ねる大切さがあります。

この事実を受け入れたとして、いくつかの話題を考えてみましょう。

(1) 人、組織について

まずは改善し続ける人、組織とそうではない人、組織との差についてです。改善がもし達成できるのであれば最初のパフォーマンスというのはそれほど重要ではなく、改善し続けられるのかが重要なように思えます。改善できる場合、そのような人、組織は指数的に改善していきます。

(2) 改善と結果の関係

改善するといっても、方向が間違っているといくら改善しても役に立たないものができます。
これが特に難しいのは、最初は改善が顧客の満足度に直結していたのが、ある時点から改善が顧客にとって改善が許容できる誤差になってしまう点です。いわゆるイノベーションのジレンマの根っこもここにあります。

改善による差別化ができなくなると、改善を必要としない(例えば研究開発部門を持たない)企業が低コストで真似できるようになり、いわゆるコモディティ化が起きます。その結果、差別化が価格面でしかできなくなり利益が急速に悪化します。このような現象は過去より繰り返されてきました。昔は繊維、今は家電、PC、そして直近ではスマホなどでしょうか。

基本的に「大きくなるだけ」しか差別化できなくなるようになったら、その分野はコモディティ化しはじめていると思います。

(3) スケールメリット

この話は少し長くなります。

0から1を生み出す発明とは違って、改善の場合は(人的)資源を投入すれば達成できる場合が多く、いわゆるスケールメリットが効くという特徴がみられます。

国内だけや特定の業種向けの製品・サービスが最初は成功していたのが、(参入障壁が無い限り)時間をかけてみれば必ず巨大な資源を持つ企業がやってきて、最初は見劣るいけていない製品をスピード重視で出して宣戦布告をし、これならまだ気にする必要はないと思っているうちに、ものすごい勢いで改善を繰り返しあっという間に追い抜いて駆逐されるというのを見てきました

そのため、中小企業は(大企業からは魅力的にはみえない)ニッチな市場を狙っていない限り、生き残ることができません。

具体例を出してみましょう。

1990年代後半から2000年代はじめにかけてMicrosoftはPCの世界の覇権を握っていました。新しい市場が生まれ、そこで生まれ育った企業がでてきて次のMicrosoftになるのではと期待されるたびに、ものすごい速さでMicrosoftはそこに資源を投入し(ある場合は有力企業を買収した上でそれを起点とし)、中小企業では太刀打ちできない改善スピードを持ってしてそうした脅威を早いうちに叩いていきました。
このへんの話は例えばNetscapeがどのようにMicrosoftに徹底的に壊滅させられたかはその当時のNetscapeの中心人物だったHorowitzのにその時の様子が載っています。また、Internetの可能性に気づいたゲイツがいかに素早く対策をとったかについても現在は広く知られています。
実際2000年前半の頃までは、Microsoftにかなう企業はもうでてこないだろうと思われました。それほどMicrosoftは巨大でありかつ俊敏であったのです。

しかし、1998年にGoogleが誕生しMicrosoftからは(その当時は)魅力的ではないウェブ検索という分野で成長し始めます。GoogleにはMicrosoftに叩き潰されて来た人たちが多くいたので、どのようにしたら勝てるのかを考え抜いていました。Googleは検索連動型広告、コンテンツ連動型広告が莫大な収益をあげることをIPOするまで隠し続け、その間に自社の基盤や組織を育てあげ、想定されるMicrosoftからの強烈な攻撃を跳ね返すことができるほどまで成長することができました。

その後どうなったかについてはみなさんご存知の通りです。
一方でGoogle自身もその後FacebookにSNS、AmazonにCloudの分野では資源を投資しても追いつかない状況まで許しています。当時Google CEOだったシュミットは、なぜ対策を打てなかったのかを「忙しかったから」と答えています。実際大企業で巨大なビジネスを動かしながら、新しい芽に目をくばることは想像以上に難しいことだとは思います。

このようにスケールメリットが成立する世界で勝つには、成長する市場の中で大企業が気づかないうちに育ち、後で大企業が資本を投下して猛攻してきても追いつかないようにぶっちぎらなければなりません。

ぶっちぎることができなければ、ある程度大きくなってもその後全てとられてしまいます。ほどほどで生きるということができないwinner-take-allの世界です。

今は、Google, Amazon, Appleの巨人達が世界をつぶさに見張っています。しかし、歴史は一時期の覇者は次の覇者になることはできないことが多いことを示唆しています。大型コンピュータ、ミニコン、PC、スマホ(クラウド)へ。そのたびにプレイヤーは変わってきます。チャンスが無いわけではありません。彼らに勝つには彼らに気付かれないように次の市場でぶっちぎる必要があります。

(そして私達はPreferred Networksという会社をこっそり作りました。)

=======

この変化が激しい世界では10%の改善ではなく10倍、できれば100倍の改善を目指し、そして100倍になった世界はどのようになるのかを想像することがとても大切です。今のデータセンターがチップ一つに収まるとしたらどうなるのか、カメラが人よりも高精度に人や物を認識できたらどうなるのか、プログラマの人口が今の100倍になり、Word, Excelを書いている人がみなGoやSwiftを書くようになったらどうなるのか(その先には機械がプログラミングをするようになる世界がありますが)、そうした世界を想定し、その方向に向かって進めていけるかどうかが重要となります。

10年後の世界を考える人はクレイジーと思われるぐらいがちょうど良いぐらいなんだと思います。

SIGMOD 2014 に参加しました

楠本充
エンジニア

2014-07-03 12:23:01

初めまして,新入社員の楠本です.今年の4月からPFIで働いています.
先週 SIGMOD 2014 (Special Interest Group on Management of Data) という学会に参加してきたのでその参加記を記したいと思います.
SIGMOD はデータベース分野でトップに位置づけられる会議の1つです.SIGMOD では併設で PODS という理論系データベースの会議も同時開催されています.
今年はアメリカ合衆国ユタ州のスノーバードというスキーリゾート地で開催されました.この時期は夏だったのでスキーはなかったのですが自然が雄大な場所でした.(↓写真)

1

3

今回は修士時代にやっていた研究の論文が受理されたので,発表(と他の発表の聴講)をするために参加しました.

会議について

SIGMOD/PODS は全部で6日間開催されており,以下のようなスケジュールで行われていました.

  • 1日目:ワークショップ
  • 2日目:PODS
  • 3日目:SIGMOD / PODS
  • 4日目:SIGMOD
  • 5日目:SIGMOD
  • 6日目:ワークショップ

ワークショップは参加費が高かったので2日目から5日目にかけて参加しました.
会議ではいくつものセッションが常に並列されていました.チュートリアルやデモセッションも含めると常に6並列で行われていたようです.
そうなると全部の発表を見るのはとても無理なのですが,その埋め合わせとして(?)夜に全ての研究についてのポスターセッションが開かれていて,興味のあるものはオーラルで聞いて,聞き逃したりしたものはポスターで聞くということが可能になっていました.

リサーチペーパーには418本の提出があり,そのうち107本が採択されました (採択率25%).去年に比べると採択率が上がっています(去年は20%).
採択された論文の本数を国別で見ると今年は圧倒的に US が多く,その次に大きく差を開けて中国が続くという風になっていました.日本からは 3 本の論文が採択されていました.

1

来年の SIGMOD はメルボルン,再来年はサンフランシスコで開催される予定だそうです.

今回発表した論文について

今回採択された論文は NII の前原さんと河原林先生との共著です.
SimRank というリンクベースで2つのオブジェクトの類似度を計算する指標があるのですが,それを効率よく計算するアルゴリズムを提案しました.(論文リンク)
個人的な話をさせて頂きますと,僕は元々修士の頃に JST/ERATO の河原林巨大グラフプロジェクト という研究プロジェクトでリサーチアシスタントをやっていたのですが,今回の件はそこでやっていた研究の1つになります.
(余談ですが,今回の論文のテーマであるところの SimRank を違う問題設定で計算する研究を同時期にやっていて,そちらは先日 KDD(Knowledge Discovery and Data Mining) に採択されました.)

それぞれの発表について

SIGMOD はデータベースの会議なのでデータベースがメインに扱われているのですが,僕は(上に書いたように元々実ネットワークを対象にした研究プロジェクトにいたこともあって)実ネットワーク上のアルゴリズムやデータ構造に興味があるのでそういう系のセッションに張り付いて聞いていました.
聞いた発表でいくつか印象に残ったものを雑多に紹介したいと思います.

Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
(Youze Tang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University; Yanchen Shi, Nanyang Technological University)

影響最大化(Influence Maximization )とは「ソーシャルネットワーク上でいかに口コミを色んな人に広めるか」という問題です.
厳密には,ネットワーク \(G=(V,E)\) が与えられるので,そのうちの頂点の部分集合 \(S \subseteq V\) を選んで,最初に \(S\) が口コミを広げた後,最終的に広まる口コミの影響を最大にするのが目的です.
口コミの広まり方には色々なものがありますが,Independent Cascade Model というモデルがよく使われている気がします.このモデルでは,口コミはターン制で広がり,ある人が口コミを拡散することになった後,別の人に広まるかどうかは確率的に独立に決まるという風になっています.確率はネットワークの枝ごとに設定されています.
(説明が雑ですいません.詳しくはググってください.)
扱うものは口コミでなくても影響を広めるものならなんでもよいです.

Independent Cascade Model では貪欲法を使って選ぶと最適解の近似解が得られることが劣モジュラ性により保証されるという話があるのですが,このとき計算速度に時間が掛かることが問題になっていました.
既存研究で,確率的アルゴリズムによって計算時間を大体線形時間にしたものがあって,理論的には高速なものの実用的には定数倍が大きくて使えないというものがありました.
この発表では,(おそらくその既存研究の手法を元に?)実用的にも高速で精度もよいアルゴリズムを提案していました.

ちなみにこの発表は「Social Networks I」というセッションに配置されていたのですが,他の発表も影響最大化に関するものだったので,実質的に影響最大化に関するセッションになっていました.個人的には,影響最大化は問題としては面白いけど実際に使う場合どうするんだろうなぁと疑問に思うところもあるのですが,人気分野になっているようです.

Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs
(Yubao Wu, Case Western Reserve University; Ruoming Jin, Kent State University; Xiang Zhang, Case Western Reserve University)

グラフ上の \(k\)-近傍探索問題を考えます.つまり,ネットワーク \(G=(V,E)\) があり,クエリとして頂点 \(u \in V\) が与えられるので,\(u\) に似た頂点のトップ \(k\) を出力する問題です.
ここでは2つの頂点が似ている指標としてランダムウォークベースの指標 (Hitting time のいくつかの変種や,CIKM’13で提案された Effective importance) を考えます.
この手の研究ではインデックスを最初に構築して,インデックスサイズとクエリ時間のトレードオフを考えるのが普通なのですが,この論文ではインデックスを作成せず,クエリされた頂点 \(u\) を中心に局所探索をしてトップ \(k\) を求めるという手法を取っています.
そのために,これらの類似度の指標には局所的な最大値が存在しないことを証明し,その上で,局所探索の過程で今見ている頂点の類似度の上下界を管理し,見る必要が無くなったところは見ないように枝刈りするということをしているようです.

Reachability Queries on Large Dynamic Graphs: A Total Order Approach
(Andy Diwen Zhu, Nanyang Technological University; Wenqing Lin, Nanyang Technological University; Sibo Wang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University)

到達可能性クエリという問題に関する研究です.これは,有向無閉路ネットワーク \(G=(V,E)\) があり,クエリとして 2 つの頂点 \(u, v\) が与えられるので,\(u\) から \(v\) に向かう有向パスが存在するかどうかを答える問題です.インデックス構築時間・インデックスサイズ・クエリ時間の3つの要素の良いトレードオフを実現するアルゴリズムを考えることが課題です.
既存研究でも到達可能性クエリはよく研究されていて,巨大なグラフを効率よく扱える手法が幾つかあったのですが,静的なネットワークを対象にしたものがほとんどでした.この研究では動的グラフ,つまりリアルタイムでグラフの枝や頂点が削除されうる状況で到達可能性クエリを扱っていました.
で,その手法が結構面白いと思ったのですが,既存の静的グラフ用のいくつかの有力な手法に共通する要素を1つのフレームワークとして抽象化し,そのフレームワーク上で動的グラフ用のアルゴリズムを考案するということをしていました.そして,そのフレームワークに沿った,より効率の良い手法(正確にはラベリング方法?)を提案し,動的グラフで効率よく到達可能性クエリを捌くことができると主張していました.
既存の有力な手法には東大今井研の秋葉さんや矢野くんの手法が含まれています.
複数の既存手法を1つのフレームワークにまとめてしまうというのは結構驚きな気がします.

Independent Range Sampling
(Xiaocheng Hu, Chinese University of Hong Kong; Miao Qiao, Chinese University of Hong Kong; Yufei Tao, Chinese University of Hong Kong)

こちらは PODS の発表です.データ構造の話になります.
考える問題は次のようなものです:1次元上に点の集合 \(P\) があります.クエリとして区間 \([x,y]\) と \(t\ge1\) が与えられるので,点集合 \(P \cap [x, y]\) の中から \(t\) 個の点を一様な確率でランダムサンプリングしたい.
計算モデルとしては RAM モデルを仮定し,できるだけビット並列のようなことをして計算量を減らすのが目的です.
この研究では,いくつかの異なるモデル (点がstaticかdynamicか / 外部メモリ無しか有りか) について割とタイトな計算時間の上下界を得ていました.
基礎的な問題に対して計算時間の改良を与えられているのは面白いなぁと思いました.(ちょっと改善ポイントが細かい?というのはあるかもしれませんが.)
ちなみにこのセッションでは著者の Yufei Tao が他にもう1本論文を通していたようで,2回連続で発表していました.発表がとてもエネルギッシュで聞いていて楽しかったです.

謝辞

今回の SIGMOD 参加はJST/ERATO 河原林巨大グラフプロジェクトよりご支援を頂きました.関係者の方々に深く感謝致します.今後ともよろしくお願い致します.

今年の研究振り返り

oxy
エンジニア

2013-07-16 19:14:58

吉田です。弊社では主に研究開発に携わっていますが、最近は顧問的なポジションになっている気がします。

普段は国立情報学研究所 (NII)という所で研究していて、よく論文を国際会議に投稿するということをします。
先日、CIKMという会議の結果が帰ってきて、今年開催される国際会議の結果が全て出そろったので、思い出話をしてみたいと思います。
紹介する論文の順番は、各会議が開催された(る)順です。
所々、専門用語を説明なしに使っていますがご容赦ください。

続きを読む »

エラー処理を書いてはいけない

preferred

2011-12-09 14:55:55

昨日セミナーとして USTREAM させていただいた資料を公開いたします。

エラー処理を書いてはいけない

USTREAMのビデオ

タイトルは釣り気味ですが、内容はいたって真面目なのでご安心ください。

続きを読む »

高速な安定ソートアルゴリズム "TimSort" の解説

preferred

2011-10-26 19:36:54

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。

C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。

しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います(クイックソートマージソートヒープソート挿入ソートの知識を前提とします)。

続きを読む »