Random Features~Shift invariant kernelからGraph kernelまで~

こんにちは。レトリバのリサーチャーの木村です。10/16(水)のRetrieva Engineer Casual TalkでRandom Featuresについて発表しました。これはそのフォローアップ記事になります。

動画はこちらです。


Random Features 〜Shift invariant kernelからGraph kernelまで〜 - Retrieva Engineer Casual Talk vol.3

スライドはこちらです。

カーネル法はデータ数{n}について{\mathrm{O}(n^ 3)}の計算量を必要とし、データ数が増えると直接用いることが困難であるという問題があります。 この問題に対し、カーネル関数を近似的に高速計算するための手法の一つとしてRandom Featuresがあります。 Random Featuresでは内積の期待値がカーネル関数値と一致するような特徴ベクトルを得ることが目的です。 このようにして得られた特徴ベクトルを用いて線形学習を行うことによって、近似的にカーネル関数を用いた非線形学習を高速に行うことができます。 セミナーでは最初に提案されたShift invariantカーネルに対する手法から、文字列、グラフ構造に対する手法まで紹介しました。

私は学生時代カーネル関数を厳密に高速計算するためのアルゴリズムを研究していたこともあり、とても楽しくこのテーマを調査することができました。 近年深層学習の圧倒的な盛り上がりの前にカーネル法の勢いはどちらかというと下火になっていますが、興味深い論文は毎年出てきているのでこれからも動向をチェックしていきたいと思います。

Railsオンプレミス製品のためのDockerベストプラクティスver1.0

レトリバの今村です。2019年9月中旬、Answer Finder 2.1.0 をリリースいたしました。「Docker による提供形態の開始」が 2.1.0 の主な変更点となりますが、本記事ではその内容の設計の過程で得られた知見やハマりどころなどを紹介します。

レトリバ製品開発部で確立できた「Docker まわりの定石」に関する一種の備忘録的な内容となります。Answer Finder をはじめとして、レトリバの製品は Ruby on Rails アプリケーションがほとんどのため、本記事で紹介する Docker イメージは基本的には Rails アプリ提供用のものです。

続きを読む

組織デザインの展開 ~官僚制からティール組織まで~

こんにちは。レトリバの飯田です。6/19(水)の社内セミナーで組織設計の話をしました。これはそのフォローアップ記事になります。

動画はこちらです。


組織デザインの展開~官僚制からティール組織まで~

スライドはこちらです。

www.slideshare.net

このテーマは、社会人になってから調べていたものの、体系立てられていなかったため、今回取り組みました。 組織論は、粒度が多岐にわたり、同じようなことが出自の違いにより、違う言葉で言われている場合があり、混乱しやすい分野と感じています。アジャイルスクラムティール組織・OKRなどなど、様々な手法や用語が飛び交っていますが、これらがどこに位置付けられて、それぞれどういった関係であるのかを把握するのは、そこそこに労力を必要とします。 今回は、これらをできる限り統一的な視点で整理を行いました。(個々のトピックの詳細については、それぞれの書籍をご参考ください。)

組織構造は、意図してそのようにできるものではない部分があり、ビジネスの状況や構成員のマインドにも依存します。 しかし、構造を意識できていれば、可能な範囲で最善の手を打てると考えています。 また、組織構造は働く上での多くの不幸を抑制する可能性があると考えております。 古くて、新しいテーマであり続けると思いますので、今後もウォッチしていきたいと思います。

2019年度人工知能学会全国大会に参加しました!

こんにちは。レトリバ研究開発部の飯田、木村です。


レトリバでは、研究動向・業界動向の把握のため、研究開発部の人間は積極的に国内学会に参加しており、今回は、人工知能分野で最大規模とも言える、人工知能学会の全国大会に参加しました。

 

概要

今回の人工知能学会は新潟で開催されました。
スポンサー・協賛合わせて、90社と、この分野の盛況感が伝わってきます。

 

分野も多岐にわたっており、深層学習一色というわけでもなく、人工知能に関連する様々な分野の取り組みを聞けるのもこの学会の醍醐味だと思います。

 

分野の動向として特に印象的だったのは、丸山宏先生の招待講演でした。

https://www.ai-gakkai.or.jp/jsai2019/invited-talk

 

 この講演は、深層学習の登場によって、何がどのように変わっているのかと言ったことを、計算モデルの視点から俯瞰的に述べられている、非常に刺激的な講演でした。
今後発展する方向性の一つが示されていたと感じました。

 

個別の面白かった発表

以下では個別に面白かった発表を紹介したいと思います。

続きを読む

bit vectorで編集距離の計算を高速化する

レトリバ製品開発部の@ysk24okです。

本記事ではbit vectorを用いて編集距離の計算を高速化するアルゴリズムを紹介します。論文はこちらです。

dl.acm.org

クエリの長さを m、検索対象のテキストの長さを$n$としたとき編集距離の計算量は$O(mn)$であることが知られていますが、bit vectorを活用することでword長を$w$とすると計算量を$O\bigl(\frac{m}{w}n\bigr)$($m\leq w$のときは$O(n)$)に低減できる手法になります。

1999年発表の古い論文ですが、この論文で提案されているアルゴリズムが弊社の製品に実装されていて初見では理解できなかったことに加え、日本語での論文解説が無いようだったので解説記事を書くことにしました。

  • 編集距離(Levenshtein Distance)とは
  • 近似文字列照合(approximate string matching)における編集距離
  • 編集距離の計算
  • 提案手法
    • cell structure
    • cell logic
    • cell logicの並列化
      • Eqの計算
      • 同じ列のcell間の依存の排除
  • 比較
    • 実行環境
    • 結果
  • まとめ
  • 参考文献
続きを読む

コンテナ仮想、その裏側 〜user namespaceとrootlessコンテナ〜

レトリバのCTO 武井です。

やあ (´・ω・`) うん、「また」コンテナの記事なんだ。済まない。

技術ブログの開設と新セミナー運用の開始にあたって、「前に話した内容をブログにしつつ、新しい差分をセミナーにすれば、一回の調べ物でどっちのネタもできて一石二鳥じゃないか」と思っていたのですが、

前のセミナーが情報詰め込みすぎでブログの文量がとんでもないことになって、
→ それが前提条件になってしまっているのでセミナー資料の文量も膨れ上がって、
→ 差分だけと思っていたUser名前空間も思った以上のボリュームで、
→ やっと一息かと思ったら、フォローアップ記事が残っていることを思い出すなど ←いまここ

一石二鳥作戦のはずが、どうしてこうなった……。
計画大事。


そんなわけで、今回は4/17にお話ししました「コンテナ仮想、その裏側 〜user namespaceとrootlessコンテナ〜」というセミナーのフォローアップ記事となります。 セミナーでは喋れなかったことなどを加筆しつつ、改めてコンテナ仮想の裏側で動いているUser名前空間について説明していこうと思います。

また、セミナーでは時間切れしてしまった、「手作りrootlessコンテナ」をシェルスクリプトで実装してみようと思います。

冒頭でもちらりと触れましたが、このセミナーは、前に話したセミナーを前提に話しております。 こちらはちょっと前にフォローアップ記事を挙げておりますので、先に↓の記事に目を通していただければと思います! (タイトルの付け方ミスったなぁ……)

tech.retrieva.jp

  • はじめに: rootlessコンテナとは?
  • user名前空間の歴史と背景
  • いざ実践: 準備
  • いざ実践: とりあえずrootになってみる
  • いざ実践: unshare -U
  • いざ実践: uid_map/gid_map
    • ちょっと寄り道: uid_map/gid_mapをもうすこし詳しく
  • いざ実践: 井の中のrootはなにができるのか
  • いざ実践: 井戸の中の王国建設
  • いざ実践: が、ダメッ
    • ユーザが作れない
    • ネットワークが繋がらない
    • ファイルシステムイメージの管理がダサい
  • podmanを見てみる
    • podmanのuid_map/gid_map
    • podmanのuid_map/gid_map: newuidmap/newguidmap
    • podmanのネットワーク
    • podmanのネットワーク: slirp4netns
    • podmanのイメージ管理
    • podmanのイメージ管理: fuse-overlayfs
  • できた!手作りrootlessコンテナ
  • 参考文献

続きを読む

Graph Neural Network

こんにちは、西鳥羽 Jiro Nishitoba (@jnishi) | Twitter です。5/15の全体セミナーでGraph Neural Networkの話をしました。これはそのフォローアップ記事になります。

動画はこちらです。

www.youtube.com

スライドはこちらになります。

www.slideshare.net

大学生の頃に「複雑ネットワーク」がブームになってきた時代で少し調べたことがあり、修士時代は離散数学アルゴリズム系の研究室にいてグラフに関する研究をしていたことがあるので元々グラフには興味を持っていました。その後紆余曲折を経て機械学習特に長い系列のDeep Learningにふれるようになってグラフからは離れていました。最近Graph Convolution Networkの話がちらほら見受けられるようになったので「Deep Learningとグラフがつながるときでは」と少し気合を入れて調べて見たのが今回のセミナーの経緯となります。

Graph Neural Networkについては手法がいっぱい出てきたのはもちろんですが、なぜか去年辺りからサーベイ論文もいっぱい出てきました。 今回読んでいたのは以下の2つです。

[1901.00596] A Comprehensive Survey on Graph Neural Networks

[1812.08434] Graph Neural Networks: A Review of Methods and Applications

はじめのサーベイ論文のほうが取り上げられている手法が多いですのでとにかくいろんな手法が知りたい人にはおすすめです。ただ、2つ目の方は数多くある手法の一般化についても触れられいて、より俯瞰してみることができます。 そして更に何故かGraph Kernelに関してもサーベイ論文がこの1,2ヶ月で複数出てきました。今回のGraph Kernel部分については1つ目の方を参考にしています。後者の方はセミナー準備中にでてきて時間が取れず読めませんでしたが、よりしっかり説明していそうな雰囲気です。自分でセミナーしておいて言うのもなんですがGraphでの機械学習はブームなのでしょうか。

[1903.11835] A Survey on Graph Kernels

[1904.12218] Graph Kernels: A Survey

今回調べてて一番面白かったのはGraph Neural Networkの一般化とその性能解析が進んでいたことです。今回のセミナーで主に取り上げたのは以下の2つの論文です。

How Powerful are Graph Neural Networks? | OpenReview

[1810.02244] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

元々理論屋だったのもあってこういう「意外と強くないのではないか」というのをきっちり示しているというのは面白いと思っています。もちろん、だからGraph Neural Networkが全部ダメということはなくてスライドの最後に取り上げた

  • WL subtree kernelとGNN構築の計算量の比較
  • Non local Neural Networkの性能 -- Graph Attention Network -- Transformer内のself-attention
  • グラフの構造+αを組み合わせるマルチモーダルなことで性能が上がるか

のあたりでもしGraph Neural Networkの性能が良ければ実用として強いのではないかと思っています。まだまだホットな分野だと思います。

C++テンプレートを再考する

レトリバ製品開発部の酒好き武闘派エンジニア田村です。 仕事でC++ばかり書いてるのに何故かセミナーで趣味のElixirを話しましたが、文字だと勢いで押しきれない気がするのでC++を取り上げることにしました。

C++20(またはC++2a)の規格化が来年近づいてきていますが、C++20では、ついに何度も棚上げされてきたコンセプトが採択されました。g++ -std=c++2a で試そうかと思ったのですが、コンパイラがまだ対応していない悲しみの中、まずはテンプレートを見直そうと勉強したところ、思った以上にだいぶ深かったので、今回は単純なコンテナの型指定や関数の引数の型指定以外でのtemplateのテクニックを取り上げたいと思います。帰ってこれなくならない程度の深さで…。基本・応用テクニックを中心にC++20の新機能、コンセプトもコンパイルできないため規格書ベースですが、少しだけ触れられればと思います。普段コンテナの型指定にしかtemplateを使っていなかった人やC++興味あってもあまり触れていない人の刺激になれば幸いです。

続きを読む

RubyKaigi2019に参加しました。

こんにちは。youchanこと大崎 瑶です。レトリバでは製品開発とPoCなどをやっています。

レトリバはRubyKaigi2019のスポンサーとして後援しました。おなじみのキーキャップをノベルティとして提供させていただきましたがみなさん手に取っていただけたでしょうか?

f:id:Youchan:20190426153755p:plain:w600
レトリバキーキャップ

そういうわけでRubyKaigi2019の参加レポートをお送りしたいと思います。

Parties & Services

これはここ数年の傾向ですがパーティーなどスポンサー企業提供のサービスが過熱してます。今回はそれが顕著に出ましたね。これからもエスカレートしつづけるかは分りませんが過去最高のものになりました。RubyKaigiの楽しみの一つでもあります。 個人的に参加したものを中心に紹介します。

ナイトクルーズ

まずは前日のナイトクルーズです。

f:id:Youchan:20190426155205p:plain:w400

永和システムマネジメントアジャイル事業部の提供になります。豪華クルーザーを1挺借り切っての豪華なパーティーはこれから始まるRubyKaigiの充実ぶりを予感させるものでした。

屋台

ランチには屋台が登場しました。福岡といえば屋台ということですが、まさか会場に屋台を呼ぶとは大胆です。もちろんスポンサードされているものですので無料です。私は3日間で6つの屋台をコンプリートしました。 株式会社ドリコムの提供でした。

懇親会

オフィシャルパーティーはなんと商店街を借り切ってのパーティーとなりました。これまた大胆な試みです。この様子は地元のテレビでも紹介されたそうです。

headlines.yahoo.co.jp

コード懇親会

2日目の夜は各企業がスポンサーをしてパーティーをするのが恒例になりました。私は株式会社Speee提供のコード懇親会に参加しました。 コード懇親会はコードを書きながら懇親する会です。様子は参加者のみなさんのフィードバックを見ると分かるでしょう。

github.com

Ruby Puzzle

クックパッド株式会社の2人のフルタイムRubyコミッターによるコードパズルです。不完全なコードに任意の文字列を挿入することによって"Hello world"を表示するプログラムを完成させるというものでした。どの問題も1文字だけ挿入して完成させる回答が存在していてそれを最も早く見付けられた人が表彰されました。

techlife.cookpad.com

実は私も2-2の問題の勝者になりました。;)

続きを読む