20万円でサーバを

今日は某君に

「サーバ欲しいなら20万くらいで自分で組立てなよ．64GBメモリくらいマルチコアサーバ組立てられるでしょ？？」

とは言ってみたのものの，さて，どんなスペックが20万で手に入るか？

まずはメモリ

Skylake向けのDDR4 16GB×2枚組が販売開始 - AKIBA PC Hotline!

”Skylake向けをうたうDDR4-2400 16GB×2枚セット「CMK32GX4M2A2400C14」がCORSAIRから発売された。店頭価格は税込37,940円（詳細は「今週見つけた新製品」参照のこと）。”

ということで，16GBが2本で約4万なので，64GBメモリなら8万ですよ．　128GBでも16万ですよ．

とりあえずは8万円で64GB買うとします．

 

次にマザボ．

DIMMは4本でいいので，microATXで十分（miniITXは2本しか刺さらないし）

　　Intel製USB 3.1コントローラ搭載のZ170マザーがさらに3モデル、GIGABYTE - AKIBA PC Hotline!

”スタンダードモデルの「GA-Z170X-UD3」と「GA-Z170-HD3P」も同時発売されている。店頭価格は前者が税込22,000円前後、後者が税込17,300円前後”

”GA-Z170-HD3Pは、エントリークラスのATXマザーボード。　　　主な搭載デバイスはHDMI・DVI・VGA出力、DDR4メモリスロット×4、1000Base-T LAN(Realtek)、8chサウンド、SATA Express、M.2、USB 3.1 Type-C、PS/2×1など。拡張スロットはPCI Express x16×1、PCI Express x4×1(x16形状)、PCI Express x1×2、PCIバス×2。2Way CrossFireXに対応しているが、SLIは利用できない。”

 

とりあえず2万もあればマザボが買えます．　十分です．　3万出すともっといいの買えます．

機能的には十分．　ここまでまだ10万です．

 

 

さて，肝心のCPUですが，

上記のマザボだと第6世代Core i シリーズが乗ります．　

”Support for Intel^® Core™ i7 processors/Intel^® Core™ i5 processors/Intel^® Core™ i3　processors/Intel^® Pentium^®processors/Intel^® Celeron^® processors in the LGA1151 package”

これだけ見てもよくわからないと思いますが，とりあえずリストはこんな感じ↓

GIGABYTE TECHNOLOGY Socket 1151 - Intel Z170 - GA-Z170-HD3P (rev. 1.0)

 

Socket 1151
マザーボード									製品	GA-Z170-HD3P
									PCB	1.0
ベンダー	CPU モデル	Frequency	L3 Cache	GPU Frequency	Core Name	Process	Stepping	Wattage	BCLK	BIOSバージョンから
Intel	Core i7-6700K	4.00GHz	8MB	350 MHz / 1150 MHz	Skylake	14nm	R0	91W	100	F2
Intel	Core i7-6700	3.40GHz	8MB	350 MHz / 1150 MHz	Skylake	14nm	R0	65W	100	F2
Intel	Core i7-6700T	2.80GHz	8MB	350 MHz / 1100 MHz	Skylake	14nm	R0	35W	100	F2
Intel	Core i5-6600K	3.50GHz	6MB	350 MHz / 1150 MHz	Skylake	14nm	R0	91W	100	F2
Intel	Core i5-6600	3.30GHz	6MB	350 MHz / 1150 MHz	Skylake	14nm	R0	65W	100	F2
Intel	Core i5-6600T	2.70GHz	6MB	350 MHz / 1100 MHz	Skylake	14nm	R0	35W	100	F2
Intel	Core i5-6500	3.20GHz	6MB	350 MHz / 1150 MHz	Skylake	14nm	R0	65W	100	F2
Intel	Core i5-6500T	2.50GHz	6MB	350 MHz / 1100 MHz	Skylake	14nm	R0	35W	100	F2
Intel	Core i5-6400	2.70GHz	6MB	350 MHz / 1150 MHz	Skylake	14nm	R0	65W	100	F2
Intel	Core i5-6400T	2.20GHz	6MB	350 MHz / 1100 MHz	Skylake	14nm	R0	35W	100	F2

 

気になるのは値段ですが，，，最上位の6700Kが現状5万円です．

ちなみに　

• Base Frequency (GHz)：4.0GHｚ
• Turbo Boost maximum single core turbo frequency (GHz)：4.2GHz
• Total Cache：8MB
• Cores/Threads：4/8
• Memory Type：DDR4/DDR3L
• Memory Speed Support(DDR4/DDR3L)：2133/1600
• Graphics：Intel HD Graphics 530

要するに，古い世代の2GHzくらいの8コアCPUより全然メモリアクセスも速いし，スペック高いです．

逐次処理も4GHzで処理しちゃいます．

 

さて，HDDとケースにまだ5万円も残っているので，20万もあればけっこうなサーバが自作できそうだということが伝われば幸いです．

個人的にはどうせサーバを自作するなら，30万出して，Xeon対応のマザボかって，Xeon積みたいですけどね．

 

あとは，感覚的に，

・ケース＋電源　1.5万円

・SSD　1.5万円

・HDD　1万円ｘ２

 

---

追記：2016/01/31

Core i7-6700Kが税込40,980円など、上位CPUが限定特価で大幅安 - AKIBA PC Hotline!

1月23日付けの価格調査で、Core i7-6700Kの最安値が前回比5,000円安の税込40,980円、Core i7-6700が3,758円安の税込36,720円に急落。

税込みでCPUが現在４万円くらい．

DDR4 8GB×2枚は9千円台に、DDR3 4GB×2枚は特価で久々の4千円割れ - AKIBA PC Hotline!

前回お伝えした大容量モデル、DDR4-2133 16GBは、1枚単位で販売するSAMSUNGの単体品が税込13,500円に下落。CRUCIALの2枚組/4枚組も、それぞれ税込31,800円、税込64,600円に下がっている。

メモリも税込みで6.4万円

 

安い．

天体力学講義

私の天文の研究はGRAPE使ったN体計算の研究がほとんどですが，さかのぼると一番最初にN体計算の講義を聞いたのは学部生の時に受けた稲垣先生の天体力学講義．

http://www.kusastro.kyoto-u.ac.jp/~inagaki/s-g.htm

”重力だけを考えた系の進化は、基本的にはニュートンの方程式で与えられ、古典中の 古典である。しかしながら、ニュートンの方程式も 2 体問題までは解析的に解けるが 3 体問題以上は、特殊解を除き、一般的には解析的には解けない。このような問題は 数値解は求まるが、初期条件を少し変えると解が大きく変わるというカオス的性質を 持っている。従って、厳密には数値解の信頼性も問題になる。”

２浪したわたくしは，自身の能力を顧みず，学部１回生の時から天文学科の授業沢山聞いていたと思うけど，ちょっとだけ理解していたけど，単位認定に出された問題がさっぱりだった．

 

　　「３体ピタゴラス問題を解け　（3:4:5で構成される直角三角形上に，質量比3:4:5の質量比を持った初速度0の軌道を求めよ）」

 

これ，今でこそググれば沢山答えや，シミュレータが出てくるんだけど，当時の私はさっぱりでした．

ピタゴラス三体問題のシミュレーション

ピタゴラス3体問題 (Burrau’s problem of three bodies) | 配電盤

ピタゴラスの三体問題をGeoGebra4.2でGIFアニメにしてみる。: Fallen Physicist, Rising Engineer

ピタゴラスの３体問題

いや，３体問題が非線形という感覚がなく，解析的になんで解けないのかよくわからなかったので，そっからN体シミュレーションに興味持ったのは事実．

で，
その後卒論では，天体核理論教室に配属させてもらって，大規模構造のN体計算（N=2000程度）でシミュレーションコード自分で書いてみたり，，大学院では理論の勉強して最終的にはGRAPEシリーズを使う事になって，結局その時の知見が今の研究にも大いに生かされているわけです．

 

 

さて，

今日はこんな悲しいニュースを知りました．

和歌山市磯の浦の遺体　京大名誉教授か | WBS和歌山放送ニュース

稲垣先生の訃報です．

 

無知な１回生の「数値的に解くってどういうことですか？」っていう質問に丁寧に答えて頂いたり，ありがとうございました．

心よりご冥福をお祈りします．

 

 

CUDA7.5

CUDA7.5が出ました．

 

16-bit floating point (FP16) data format

• Store up to 2x larger datasets in GPU memory
• Reduce memory bandwidth requirements by up to 2x
• New mixed precision cublasSgemmEX() routine supports 2x larger matrices

 

前から言われていたFP16．つまり単精度じゃなくて半精度演算．

倍精度よりも単精度の速いわけでしたが，半精度だと単精度の倍の速度が出るとか．

あと，メモリも半分で良い．行列も倍のサイズが持てる．

 

これ，たぶんDeep Nueral Netを超意識していて，，cuDNNの演算部分で sigmoid とかtanhとかReLUがたぶんそれほど高精度にいらないから，FP16導入してこれだけで実質x2の高速化とかになるんじゃないだろうか？

 

で，

とりあえずTool kit を落として来てSampleを見てみると，

　　6_Advanced/matrixMulDynlinkJIT/cuda_drvapi_dynlink_cuda.h

このサンプルだけに使われていて，

/**
* Array formats
*/
typedef enum CUarray_format_enum
{
CU_AD_FORMAT_UNSIGNED_INT8 = 0x01, /**< Unsigned 8-bit integers */
CU_AD_FORMAT_UNSIGNED_INT16 = 0x02, /**< Unsigned 16-bit integers */
CU_AD_FORMAT_UNSIGNED_INT32 = 0x03, /**< Unsigned 32-bit integers */
CU_AD_FORMAT_SIGNED_INT8 = 0x08, /**< Signed 8-bit integers */
CU_AD_FORMAT_SIGNED_INT16 = 0x09, /**< Signed 16-bit integers */
CU_AD_FORMAT_SIGNED_INT32 = 0x0a, /**< Signed 32-bit integers */
CU_AD_FORMAT_HALF = 0x10, /**< 16-bit floating point */
CU_AD_FORMAT_FLOAT = 0x20 /**< 32-bit floating point */
} CUarray_format;

・・・・・

CU_RES_VIEW_FORMAT_FLOAT_1X16 = 0x13, /**< 1 channel 16-bit floating point */
CU_RES_VIEW_FORMAT_FLOAT_2X16 = 0x14, /**< 2 channel 16-bit floating point */
CU_RES_VIEW_FORMAT_FLOAT_4X16 = 0x15, /**< 4 channel 16-bit floating point */
CU_RES_VIEW_FORMAT_UNSIGNED_BC6H = 0x20, /**< Block compressed 6 unsigned half-float */

 

けど色々と見たけど16bit演算しているような箇所は見当たらなかったので，float4型に代わる hfloat8とかできるのかと思ったけど，まだ不明．

---

追記

 New Features in CUDA 7.5 | Parallel Forall

もうちょっと詳しいページがあって，

「A new header, cuda_fp16.h defines the half and half2 datatypes and __half2float() and __float2half() functions for conversion to and from FP32 types, respectively.」

と書いてあった． half 型と half2はあるみたいなのと， half => floatの変換とその逆もあるらしい．

「The range of half-precision numbers is approximately 5.96 \times 10^{-8} \ldots 6.55 \times 10^4. half2 structures store two half values in the space of a single 32-bit word」

ということで値の範囲も書いてあった．

 

Fast Multiplicative Algorithm for Sparse Non-negative Tensor Factorization

 非負値スパーステンソル因子分解におけるMultiplicative更新手法の高速化

　　　　リンク　＞　情報学広場：情報処理学会電子図書館

 

っていうので，先日HPCS2015でポスター展示出してきました．

NMFに詳しい人は un-folding とか k-mode expansion とか聞いたことあると思うんですけど，基本的やっていることはそれです．

－－－

やったことは，定式化ではなくて実装の話で，

　１）　高次テンソルをk-mode展開して各因子毎に行列表現に展開する

　２）　各因子毎に異るデータ構造を取得して，因子毎に更新データを保存しておく

　３）　因子行列は全因子間で共有する

－－－

 

１）はこんな感じで行列表現して，更にスパースデータであれば要素毎に潰しやすくなる

 

２）も，X，\hat{X}に対して，上図みたいにデータ構造を因子毎に持っておくと，

こんな感じでランダム・アクセスが防げるので処理が速くなる．

 

３）因子行列 In はしょうがないので全因子間で（マルチスレッドを意識していますけど）共通に持たせる． 

 

 

ただ，これはあらゆるパターンでうまくいくわけではなくて，データ構造が小さい割に次元が多いような構造だと逆に処理が遅くなるし無駄にメモリ空間を食います．

原稿には書いていないけど，ここらへんのベンチマークは簡単に取ってみたけど，たぶんCPUのキャッシュサイズにもよるんだと思うけど，　1Kくらいのデータサイズだと逆に遅くなる．100Kくらいになると効いてくる．

 

で，実はこんなことやっているのは更にもっと速くしたいので，この処理自体は目的の途中段階なんですが，CPU単体でも結構速く動くし，今度のオープンハウスでこのネタの話もするので一先ずHPCSで発表してきました． 

 

---

以下，雑記

業績にカウントしたくて発表したのではなくて，何かと技術の参照先として未発表だと色んな所で面倒なことになるし，なんでもいいから公開情報の参照先があると便利なので，そういう意味でHPCSのポスター発表は多用させてもらっています．　

あと，昔はポスターインデキシングがあって，けっこうみんな後から興味持って聞きに来てくれるんだけど，今回は企業紹介ばかりなのと全然知り合いも減ってきた感があるしポスター聞きに来てくれる人が少なかったので，自分で東大の大島さんを捕まえて無理にでも説明してきてしまった．

 

とりあえず，公知日は1週間前というのは覚えておこうと思う

 

JWEIN2015

一応じぶんもプログラム委員なので

JWEIN2015 - JSSST_SIG_EIN

• 日程: 2015年8月19日（水）～ 8月21日（金）の3日間
• 場所: 日本大学理工学部　駿河台キャンパス CSTホール

ネットワークが創発する知能研究会(JWEIN2015) 開催案内および発表論文募集

 

 申込サイト

• 下記のサイトにアクセスしてオンラインで申し込みしてください．
• JWEIN2015発表申込サイト（Easy Chair）

 

■ 発表区分:

　・口頭発表 （論文多数の場合はポスター発表になる場合もあります） 　※研究会プログラム委員会による厳正な査読を行います．

■ 投稿フォーマット

• TeXフォーマット，MS-WORDフォーマット（日本語または英語）
  • ページ数は6～8ページです．
  • ◆◆◆スタイルファイルはこちら◆◆

 

---

さて，PCだからといって行くだけでは勿体無いので，やはり何かしら研究報告したい．

そしてやはり「国内学会和文論文誌での論文特集「ネットワークが創発する知能」への優先的な論文募集を行います．」

っていうのに投げて少しでも論文投稿に貢献したいところではある．

昨年度は，「既存手法使った適用だしなぁ・・・」と思いつつも投稿してみて，査読者から色々とrejectに近いような意見を頂いたけど，真摯に対応しつつ，分析手法に独自性を持たせて主張点を180度変えたらなんとか採録されたので，やはり日本語論文誌でも出し続けるのは重要だよね．っていう実感もあるので，今年も頑張りたい．

で，

• 　投稿〆切：7月10日（金）
• 　採択通知：7月31日（金）※予定
• 　最終原稿：8月14日（金）※厳守

 うむ，なにげに今から新しいことする時間が確保できる気がしないが，それでも延期されることを前提にしてでも頑張りたい．

肉まぐろフェスタ

GW初日はソレイユの丘で肉まぐろフェスタに参加。

まぁ肉食べたのはわたくしだけなんですけどね。

写真はきむらてつのサーロインステーキサンド(700円)とサーロインステーキの牛カツレツ(1400円)。
カツレツはレアで最初は「イマイチ...」と思ったけど、ついて来たわさびと醤油で食べるとけっこううまい。

他のケバブとかも食べたかったけど、さすがにお腹いっぱい、というより脂にやられました～

あとトルコアイス🍦が出てて、テレビでやってたみたいにおもしろおかしく渡してくれるので、息子ちゃんも喜んでました。

新年度新学期二年生

早いもので息子ちゃんはもう小学二年生．

今朝も興奮しながら学校に行きました．

 

「ジェリックに会えるのかな？」（保育園の一個下の友達）

自分が一年の入学式はあれだけ緊張していたのに二年ともなるとこんなに違うんですね．

黄色い帽子もかぶらないでいいし，ランドセルの黄色いカバーも無い．

本人は帽子もカバーも嫌だったわけじゃないけど，やはりお兄ちゃんになることがとても嬉しいのだと思う．

 

クラスも先生も変わってしまうのでこちらもドキドキなのですが，，，

一年三組の担任先生，本当に一年間ありがとうございました．

お陰様で登校拒否もせず，ちょっとずつ我が子も自信を取り戻しながら成長することが出来ました．

 

新しい担任先生，これから一年間，個性の強い七歳児ですがよろしくお願いいたします．

H26年度

なんか数年前も年度を振り返った結果「あの記事消したほうが・・・」と，色々と心配されたので，たぶん今年度もまとめるとみんなに心配されるのでギリギリグレーなところで．

 

さて，この一年間を振り返る・・・

 

4月，共著者様のWebSciのポスターが，社内で一悶着有りましたが採録

Regular behavior measure for location based services

Aki Hayashi, Tatsushi Matsubayashi, and Hiroshi Sawada. 2014. Regular behavior measure for location based services. In Proceedings of the 2014 ACM conference on Web science (WebSci '14). ACM, New York, NY, USA, 299-300. DOI=10.1145/2615569.2615657 http://doi.acm.org/10.1145/2615569.2615657

もっと大変だったのは息子ちゃんの小学校入学だったかもしれない．

学校の先生と密に連絡とったり，毎朝小学校の教室までついて行ってた．1年振り返って本当に成長したな～～って思う．

 

 

5月は，某社内案件がまだまだ続いていた上に，4月から始まった共同実験と，部下が一人増えて何かと大変だったと思う．

それでも共同実験の分析初めて割りと研究していたっていう気にはなっていたし，色々と分析手法を考えていたので楽しかったと思う．

 

 

6月は，研究指導が3人になり，その3人が全く違う方向性の研究でとっても大変だったけど，割と研究してた．

DELLで１０Gのスイッチ買って導入して，勉強のためにスイッチの設定していたけど，うん，なんでみんな苦労していたのかとてもわかった．

 

 

7月は部下が不在だったのに，日記読み返すとなんか他のグループの業務お手伝いにやたら時間取られていたようだ．．．

それでも自分の時間が結構取れたので，研究会ｘ２に投稿しつつ，共著も研究会ｘ２を投稿．

 

 

８月，

・ERATO河原林研の発表会があり，家庭内決裁が承諾されたので聞きに行く．

・・生で初めてniamさん，iwiwiさんなどなどと話す．　

・・所長と密会していたためにissei_satoさんの話が聞けず．．．

・・河原林先生とも色々と話すがとても気さくで，若くて驚いた．　などなど

・JWEINに参加．PCなのに実は初参加＆初主著投稿という．

こんな内容の発表

　　”松林, 幸島, 林, 澤田, 非負値テンソル因子分解を用いた購買行動におけるブランド選択分析.ネットワークが創発する知能研究会(JWEIN2014)”

しばらく会社に引き篭もっていたので，やはり社外の人と話すのはとても刺激的だと実感した８月でした．

 

 

９月，NetEcoと社内の新しい案件

NetEcoもPCで，近くの湘南国際村開催だったので色々とお手伝いを．こんな内容

　　”松林, 幸島, 林, 澤田, 非負値テンソル因子分解を用いたパターン抽出とその応用例,情報処理学会 第11回ネットワーク生態学シンポジウム, 2014”

 

 

１０月，ココらへんからホントブログに書けないことで色々と有りました．

 

 

１１月，この月も色々と大変でしたわ．

・IBISMLで共著者がこんなので発表を　”異粒度複数行列の制約付き非負値因子分解について，幸島匡宏・松林達史・澤田宏”　　IBISML 2014

・WebDBで共著者がこんなのを発表を　”林, 幸島, 松林, 澤田, 購買ログを利用した消費者行動分析のための習慣度算出手法,　Web DB Forum, 2014”

・WebDBは聴講参加＆なんか頼まれまして初の出席参加．ceekzさんやtksakakiさんと初めまして（tksakakiさんは一方的に知っているだけだが．．．），chiemiさんやら，R社に写ったsuhara君や，数年ぶりにtsubosaka君に会うなど，なかなか楽しかったわけです．

 

 

１２月，組織改編（２年ぶり何回目？）で色々と体制変わったけど，本格的にストレスで心臓が痛い毎日でした．

・グループ再編で，増えたのは雑用と責任感で，減ったのは＊＊＊＊＊＊　いや，ほんと色々と思い出したくもない

・投稿論文が照会．・特許が拒絶で帰ってくるなど．．　年末に家族ともどもインフルエンザが大変でした．

 

 

１月，引き続き胃が痛い状況でしたが12月の頑張りのお陰でだいぶ正常化されてきた（泣）

・インフルの中，査読と，自分の論文改訂．共同実験対応に追われる日々

 

 

２月，３月は共著で国際会議４件ぐらいだしてたぶんその対応が．

・３月は論文採録（久しぶりに嬉しいニュース）．JWEINで話しした内容ですが，査読者様達のおかげで更にスッキリした内容になりました．

 

 

 

そんなこんなの2014年度でしたが，毎日つらいつらい言っている反面，息子ちゃんの保育園送迎が無くなったのと，息子ちゃんの成長のお陰で今までよりも頻度高く首都圏開催の研究会に参加できるようになってきたと思いますし，研究者としては少しずつまた前に進み始められている気がします（すごーーく遅いけど）．

 

ということで，2015年も積極的に研究会に参加（＆投稿発表）を進めていき，少しずつ研究速度をあげていきたいと思います．

そのために，今まで以上に研究に対する摩擦力をどうにかする努力も．

ぐうぶろぐ 再開しよう そうしよう

完全放置してます　やる記です

 

Twitterで垂れ流している愚痴をここに書き留めるのもアレなのと，gooブログの画像アップロードがダメな子なのでgooブログやめようかとはてな使ってみたりしましたが，最近はブログ自体を書き留めるほど偉そうなこと何もやっていないのでネタが無いというのが正直なところです．

まぁ，それでもやっぱりブログのほうが後で見返せるよね？とは自分でも思いますので，2015年度はブログもちょっと再開したい．

Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks ...

本格的にムービー作ったらしく，まずはこちらを

アルゴリズムが世界を変える Season 1.0

 

そして秋葉君自信がブログを書いているので，なによりそっちを見るべき　＞＞　WWW'14 に論文採択 - (iwi)の日記

 

で，
ここまでは概要なので，
アルゴリズムの本質を理解するには．．．

 

秋葉君のHPにあるスライド．＞＞Takuya Akiba (The University of Tokyo)

 

で，やはり最後は論文を

Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling

 

---

すでに他人がなんか書く必要がないほどコンテンツが充実しているのが，秋葉君が人外たるところです．とてもじゃないけど見習えないですｗ

Dynamicということで，静的グラフじゃなくて，動的に変化するグラフに対する最短経路問題へのアプローチ．（WWWは最近，動的な研究はうけるのかも）

グラフ上の最短パス 

「対応しているグラフの変更は今の所残念ながら辺の追加のみです．しかし，現実のネットワークでは辺の追加の方が削除よりも遥かに多いため，実用的にはそれでもかなり価値があるという事を主張しています．」

多分来年のWWWには削除どころか，ノード変化も合わせて投稿しているのが秋葉君だと思う．

 「辺に時間の入った大規模なグラフデータにおいて，距離を使った指標がどのように時間経過と共に変化していくかを観察できるようになります．」

これはエッジの追加される時間だろうか？
重み自体に時系列の重みがあっても面白いのだけど，多分粒度の問題で，マクロ的にはエッジに時系列変化があるけど，ミクロ的には0/1で，その集合で表されるのかな，とも思う．

 

とりあえず論文理解よりも，ブログの最後の方がとてもいいので，ゴメンナサイ，コピペで張らせてもらいます．

特に今回は，「更新で削除が対応していない」という点がかなりきつい防御ポイントで，VLDB で落とされたのもその点の影響も大きかったと思います． 「WWW に 5 年で 6 本」で有名な松尾先生も仰っている通り，論文を通すためには失点を少なくすることが重要であり，こういう大きな突っ込まれ得るポイントがあると，例え面白くても「論文を通す」という観点からは結構厳しいです．そのような部分を今回は議論で押し切ることができたというのは少し自信につながり嬉しいです．

 

追記，WWWではなくて，SIGMODのだけど参考に

Fast Exact Shortest-Path Distance Queries on Large Networks by PLL(SIGMOD'13)　秋葉 拓哉

 

---

追記：聞いてきました．

 

質疑では「エッジの追加が重要とは言っても，エッジを削るっていうのも重要じゃやないのか？」という話が出ました．

きっとここが一番難しいんだけど，個人的には問題設定を限ればできるんじゃないかなぁとも思う．

ノードの追加はそもそも次数0のノードを持っておけばいいはずなので対応可能らしく，実際にノードの追加は入っている様子．削除は難しいのだけど，メモリ空間さえ許せば，枝刈りの時に参照しているノード情報を持っていれば，影響を受けるノードが全探索しなくても済むはず．

個人的には，幅優先で探索の枝刈りをするだけだとIndexingは速くても削除に対応しづらいので，部分グラフ構造を抽出した後の処理に限定すればエッジ削除も対応しやすくなるとは思う．

問題は部分グラフ構造が本当に効くような現実データがそんなに無いような気がする（現実のグラフ構造はもっと複雑）ので，reviewerに文句言われるだろうなぁ，という気がしている．

もっと友人関係に絞って，友人関係グラフも重み付きで閾値で切るとかする問題に限定すると面白いかも．

（自分の可視化では，結構高い共起度で閾値切りしてたので，話題のグラフはサブグラフだらけなので） 

 

で，懇親会とは色々と秋葉君とお話しましたが，こちらも色々と見習い，負けずに頑張って行きたいものです．

Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations

とりあえずブログにわかりやすくまとめられています．　　todo314さん（大坂さん）のブログ　＝＝＞　AAAI-14に論文採択 - とどの日記

 

論文　＝＝＞　www-imai.is.s.u-tokyo.ac.jp/~takiba/papers/infmax_aaai14.pdf

---

 

 

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm(ICML'14)　相馬 輔

 

論文　＞＞　jmlr.org/proceedings/papers/v32/soma14.pdf

---

広告における最適化の問題

 

うーーむ，現実的にマーケターこのアルゴリズムが受け入れられるのだろうか？と悩んでしまう．

とはいえ，うちの人達も機会最大化とかやっているので，勉強になる．

 

文章要約に使えるというところで，「単語を選ぶだけ」って言ってしまうと怒られるんじゃないか？

 

「広告効果が時間減衰するとう仮定」
とうのは某君も興味がオオアリな話．

Linear-Time FPT Algorithms via Network Flow

Linear-Time FPT Algorithms via Network Flow(SODA'14)　岩田陽一

 

論文

[1307.4927] Linear-Time FPT Algorithms via Network Flow

---

 頂点被覆問題の話で，

NPハードの問題なんだけど，今回は「ｋ個で被覆できますか？」っていう判別に線形時間内でOm4^k)で解きますよ．って言う問題．

 

一般的に最小頂点被覆問題というと，

　「刑務所とかで監視員を何人，どこに配置すればいいのか？」

っていうのが有名なんだけど，頂点に対して0/1じゃなくて，0,0.5,1と離散値取って問題を解くっていうアプローチ．

 

こういうの好きなんだけど，結構やり尽くされていないんですね．

Max-flow min-cut theorem and faster algorithms in a circular disk failure model

Youtube（あげていることが凄い・・・）

円板形領域損傷モデルにおける最大流最小カット定理と高速アルゴリズム(INFOCOM'14)　小林 佑輔

 

次に論文

www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2013/METR13-15.pdf

---

INFCOM：ネットワーク関連の国際会議で理論系も多い．採択率20%弱で（320/1645）結構ハード

 

まず予備知識に「連結度」．
「どのくらいのエッジを取り除いても連結が保たれるか？」 
という研究がベースで， 実際のNWでも耐故障や信頼性の問題としてとても重要．

現実的なNWを考えれば，ネットワークは超高次元なグラフを考えず，地理上に埋め込めるような低次元に埋め込めるNWを考えればイイ．（この場合は平面2次元グラフ）．”円板形領域損小モデル”は，実空間的にノードを考えて，円内に含まれるノードを考慮する．

通常最小カットは，最小個数の辺を数える．
ここでは平面グラフなので，円盤でカットする．

 

「最大流アルゴリズム」

・・・実は平面NWなので問題をシンプルに解きやすい．

　「『上』から順に選びます」

と言う事ができます．通常位相空間上だと「上」とか無いですが，この場合はあるので，上から順番に決められる．

　たぶん一般の場合は高次元の超球体を考えて，空間の端から考えればいいのでしょうが，実用的でないだろうし，超球体が大きすぎる気がするので，「平面と円板」なのでしょうね．
 

ちょっとYoutubeだと問題設定がわかったけどアルゴリズムがよく分からなかったので，論文読んでおくかな．．（時間ないけど．．） 

 

ERATO感謝祭の予習

金曜日（8/8）にこんなのが有ります

JST ERATO 河原林巨大グラフプロジェクト・感謝祭Summer 2014

 

いや，生半可なものじゃなくて，

• 特に理論計算機科学分野（STOC,FOCS,SODA)のみならず、データマイニング、データベース、機械学習、AI,　WEB, ネットワーク分野（KDD, SIGMOD, VLDB, AAAI, ICML, WWW,　INFOCOM)等でも論文が採用されるようになりました。今回は、上記国際会議に採用された論文に関する研究成果発表会を開催します（理論計算機分野に関する研究成果以外を中心とする予定です）。

って言うことなので，プログラム内容がガチです．

• 10:25-10:30　河原林　健一　研究総括挨拶
• 10:30-11:00　小林　佑輔　Max-flow min-cut theorem and faster algorithms in a circular disk failure model (INFOCOM)
• 11:00-11:30　相馬　輔　Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm（ICML）
• 11:30-12:00　吉田　悠一　Almost Linear-Time Algorithms for Adaptive Betweenness Centrality using Hypergraph Sketches（KDD)
• 13:30-14:00　大坂 　直人　Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations（AAAI)
• 14:00-14:30　岩田　陽一　Linear-Time FPT Algorithms via Network Flow (SODA)
• 14:30-15:00　楠本　充　Efficient SimRank Computation via Linearization（KDD), Scalable Similarity Search for SimRank（SIGMOD)
• 15:30-16:00　秋葉　拓哉　Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling (WWW)
• 16:00-16:30　前原　貴憲　Computing Personalized PageRank Quickly by Exploiting Graph Structures（VLDB)
• 16:45-17:30　招待講演　佐藤　一誠　（東京大学/JSTさきがけ研究員）　ビッグデータ時代の大規模ベイズ学習(ICML)

ということで，

こりゃどうみても流し読みだけでも予習が必要ではないでしょうか？

で，概要もあるのでちょっとずつお勉強していきます．