Academication-AI

AI活用・オープンイノベーションのためのメディアです。最先端のAIビジネス事例情報と研究情報をお届けします。

【研究者向け】Fast and Provably Good Seedings for k-Means — NIPS2016

【一言まとめ】重要な手法であるk-meansの初期値設定の改善手法を提案した。

【著者】Olivier Bachem, Mario Lucic, S. Hamed Hassani,Andreas Krause

【所属機関】ETH Zurich (チューリッヒ工科大学)

【URL】https://papers.nips.cc/paper/6478-fast-and-provably-good-seedings-for-k-means

【Abstract】
Seeding — the task of finding initial cluster centers — is critical in obtaining high-quality clusterings for k-Means. However, k-means++ seeding, the state of the art algorithm, does not scale well to massive datasets as it is inherently sequential and requires k full passes through the data. It was recently shown that Markov chain Monte Carlo sampling can be used to efficiently approximate the seeding step of k-means++. However, this result requires assumptions on the data generating distribution. We propose a simple yet fast seeding algorithm that produces *provably* good clusterings even *without assumptions* on the data. Our analysis shows that the algorithm allows for a favourable trade-off between solution quality and computational cost, speeding up k-means++ seeding by up to several orders of magnitude. We validate our theoretical results in extensive experiments on a variety of real-world data sets.

【Abstract翻訳】
Seeding — 最初のクラスタ中心を見つけるタスクは、k-Meansのための高品質なクラスタリングを得る上で非常に重要です。 しかし、k-means ++シード(最先端のアルゴリズム)は、本質的にシーケンシャルであり、データをk回フルパスする必要があるため、大量のデータセットには適していません。 最近、マルコフ連鎖モンテカルロサンプリングを用いて、k-means ++の播種ステップを効率的に近似することが示された。 しかし、この結果は、データ生成分布に関する仮定を必要とする。 私たちは、単純で高速なシードアルゴリズムを提案します。このアルゴリズムは、データを前提としない*良いクラスタリングを証明します*。 我々の分析によれば、このアルゴリズムは解の品質と計算コストとの間の有利なトレードオフを可能にし、k-means ++シードを最大数桁まで高速化します。 さまざまな現実世界のデータセットについて広範な実験を行い、理論結果を検証します。

 

【どんなもの?】
K-means 法の初期値設定方法の改善手法

【先行研究と比べてどこがすごい?】
既存手法の弱いところを補強している
→分布の仮定が無い.理論解析)

【技術や手法のキモはどこ?】
MCMCを使うが,最初のクラスタ中心に注目

【どうやって有効だと検証した?】
・連鎖長に対する反応
・距離計算回数

【議論はある?】
1回全データのスキャンが必要

【次に読むべき論文は?】
・ Approximate k-means++ in sublinear time — AAAI

【関連リンク】

【研究者向け】k*-Nearest Neighbors: From Global to Local — NIPS2016【論文】

kNNをまともに使っている人は知っておくべきNIPS2016の論文

【一言まとめ】重み付きk近傍法の新たな精度の良いアルゴリズムを提案

【著者】

【所属機関】

【URL】https://arxiv.org/abs/1701.07266

【Abstract】
The weighted k-nearest neighbors algorithm is one of the most fundamental non-parametric methods in pattern recognition and machine learning. The question of setting the optimal number of neighbors as well as the optimal weights has received much attention throughout the years, nevertheless this problem seems to have remained unsettled. In this paper we offer a simple approach to locally weighted regression/classification, where we make the bias-variance tradeoff explicit. Our formulation enables us to phrase a notion of optimal weights, and to efficiently find these weights as well as the optimal number of neighbors efficiently and adaptively, for each data point whose value we wish to estimate. The applicability of our approach is demonstrated on several datasets, showing superior performance over standard locally weighted methods.

【Abstract翻訳】
重み付きk最近傍アルゴリズムは、パターン認識および機械学習における最も基本的な非パラメトリック方法の1つである。 近所の最適な数と最適な重みを設定する問題は、長年にわたり多くの注目を集めてきましたが、この問題は依然として不安定なままでした。 この論文では、偏微分トレードオフを明示的にする、局所的に重み付けされた回帰/分類への簡単なアプローチを提供します。 我々の定式化により、最適重みの概念をフレーズにし、価値を推定したい各データ点について、効率的かつ適応的にこれらの重みと最適な近傍数を効率的に見つけることができる。 我々のアプローチの適用性は、いくつかのデータセットで実証されており、標準的な局所重み付け法よりも優れた性能を示しています。

【どんなもの?】
k近傍法を用いる際に,データに重みを与えて行う.

【先行研究と比べてどこがすごい?】
メモリベース手法に比べ,高精度.計算量O(nlogn)

【技術や手法のキモはどこ?】
・評価関数を不等式で評価
・緩い仮定での最適化問題に帰着

【どうやって有効だと検証した?】
回帰問題における数値実験(CV)(RBFカーネル

【議論はある?】
連続値のみが対象

【次に読むべき論文は?】
・ Information estimators for weighted observations — Neural Networks(2013)

【関連リンク】
https://www.slideshare.net/ssuser8e1bc7/knearest-neighbors-nips-icdm

Y CombinatorのRequests for Startup【注目テクノロジー分野・アイディア】part.1

かの有名なアクセラレータの

Y Combinator

がまとめてくれている「アイデアを刺激するためのリスト」です。

Requests for Startups

かなり便利だし刺激を受けることができると思ったので、一部を日本語訳・まとめをしようと思います。

 

 

エネルギー

・エネルギーコストが下がると生活の質が上がる

原子力エネルギーや再生利用エネルギーのようなエネルギー源は環境、経済、戦争の軽減、安定した未来の確保、食糧と水の豊富化などを助けることができる

・エネルギー貯蔵と伝達。10倍のバッテリーがあれば、エネルギーを簡単に動かすことができるように、新しいものが可能になる。

 

AI

潜在的な影響力は大きいもののまだ十分賢い使い方がされていない。

・自家用車、創薬、プログラミングアシスタント、詐欺検出などのような「狭い」ドメインに新しい研究を適用する人々に興味がある。

 

ROBOTICS

・物理的な世界で物事を成し遂げるための主要な方法

・自走車もロボットと見なす。 ロボットは、私たちがどのように空間を探検するか、あるいは人間の身体を探検する方法。

 

BIOTECH

・疾病と戦ったり、老化を遅らせたり、人間とコンピュータを融合させたり、思い出をダウンロードしたり、遺伝的プログラミングなどをするような多くの方向性がある。我々はこれが数十年にわたって驚くほど強力で議論の余地のある分野であると確信している。 1970年代のマイクロコンピュータのような感じだ。

・DNAを読むことは信じられないほど迅速かつ安価になっている。 興味深いアプリケーションがたくさんある。 私たちがDNAを書くことをよりうまくいくようになれば、おそらくもっと興味深いアプリケーションが出てくる

・悪い人が新しい感染症を素早く作り出した時に、良い人たちが新しい治療法やワクチンを素早く作り出すことができればいい。

 

HEALTHCARE

・米国の医療はひどく有様。 GDPの20%を医療に費やすことに近づいている。 これは持続不可能だ。

・より少ないお金で健康管理を改善する方法に興味がある。 私たちは予防的な医療に特に関心がある。これは、おそらく健康を改善するための最も効果的な方法だからだ。 センサーとデータは、さまざまな分野で面白いが、特に医療の分野では興味深い。

・医療機器もスタートアップの肥沃な土壌のように思える。

 

PHARMACEUTICALS(医薬品)

・医薬品の開発は、より遅く、より高価になっている。

・私たちは、これを新しいやり方で行う企業に資金を提供したい。 nootropics(向知性薬、スマートドラッグ)のような領域は、過小視されているようだ。

 

Education

・技術を使用して教育を修復しようとする最初の試みは、インターネットを使って従来のコンテンツをより多くの視聴者に配信することに焦点を当てている。 これ自体はいいが、インターネットは根本的に異なるメディアであり、はるかに多くのことが可能だ。

・大量の技術と1対1の対話を組み合わせたソリューションは、特に興味深い。

 

HUMAN AUGMENTATION(人間拡張)

・これは非常に一般的なカテゴリ。なぜなら、これを行うにはさまざまな方法があるからだ。バイオテクは私たちがより長く生きられ、よりスマートになるのを助けます。 ロボットは私たちがそうでなければできなかった身体的なことを手助けすることができます。 ソフトウェアは、われわれをより幸せにする簡単な行動に焦点を当てることができます。 そして何度も繰り返します。

 

VR & AR

・VR(仮想現実)とAR(拡張現実)は、未だ達成されていない。

・しかし、私たちは波が来ていると感じてる。つまり始めるのが正しい時期だ。

 

TRANSPORTATION & HOUSING(交通と住宅)

・すべてのエネルギーの約半分が輸送に使用され、人々は通勤に膨大な時間を費やしている。

・Face to Faceのやりとりは依然として重要です。 人々はまだ移動する必要がある。 そして、住宅は輸送の難しさのために部分的に高価になっています。 私たちは、人々がどこかで素敵に生活し、一緒に働き、通勤が楽になる良い方法に興味を持っている。

・具体的には、軽量で短距離の個人交通に興味を持っている。

 

 

part.2に続きます

 

私たちについて

Ations株式会社はオープンイノベーションを加速させることを目指しています。

現在は人工知能(AI)領域に絞り、開発会社とクライアントのAIリテラシーギャップを埋めるべく、メディアの運営および、AIコンサル、AIアドバイザリー、イベントや勉強会をしております。

いつでも気軽にご連絡ください。

また、「世界にテクノロジーを届けオープンイノベーションによって、科学の発展を加速させたい」と志を同じくする方は是非ご協力ください。

ライター、エンジニア、デザイナー、インターン、オープンイノベーター、サイエンスコミュニケーター、研究者を募集しています。

ations.strikingly.com

 

機械学習を用いてGoogle Play上の詐欺アプリを検出したところ、結果的に新手の不正のやり方が見つかった【MIT Technology Review】

また新たな機械学習の適用先の事例が増えたことには変わりないが、以下のMIT Technology Reviewのタイトルが少しミスリーディング。

機械学習自体が不測の新手不正トレンドを見つけたみたいな書き方。

www.technologyreview.jp

 

人工知能関連技術の一種である機械学習を用いたのは、

【インプットデータ】 過去のアプリのレビュー

【アウトプット】 詐欺レビューか正当なレビューか

これにより、詐欺レビューが書かれた詐欺アプリが見つかり、それらの傾向を見ていくと、

マルウェアが一般ユーザーに、詐欺アプリの肯定的なレビュー書くよう強要していたのだ。「フェアプレーのおかげで、新手の宣伝強制型攻撃手法が見つかりました。ユーザーは、アプリに対して肯定的なレビューを書くよう、執拗に求められるのです。さらに他のアプリまでインストールさせられ、またレビューを書かされるはめになります」と研究チームはいう。

ことがわかったという話。

 

ニューラルネットワークはどこまで人の脳に近づけるのか【DeepMind】

DeepMindのブログでの発表が波紋を呼んでいます。

deepmind.com

上のブログの記事は以下の2月に出されたDeepMindの論文を元に書かれています。

Overcoming catastrophic forgetting in neural networks

 

簡単に言うと、

「人間の脳のような学習の仕方の糸口が掴めた(かもしれない)」

 

もう少し細かく言うと

「人間は段階的に学び、スキルを一度に1つずつ取得し、新しい課題を学習する際に以前の知識を適用することができるが、

これまでのニューラルネットワークは一度に提示されたタスクを解くためにしか学習できず、次のタスクを学習する時には前の学習を上書きして忘却してしまう。これは認知科学において「壊滅的な忘却(catastrophic forgetting)」と呼ばれている。

この問題を解決する糸口として、過去のタスクの重要度に応じて、ネットワークの接続度を保護し、壊滅的な忘却が起こらないようにした。」

 

 

 

 

日本でも以下のようにセンセーショナルな記事が。

pc.watch.impress.co.jp

 

DeepMindはニューラルネットワークから脳を作り出そうとしている。

日本だと全脳アーキテクチャが取り組んでいるアプローチと似ている。

 

 

 

 

 

【研究者向け】PixelCNNを並列化【DeepMind2017/03/10】

自然画像の生成に用いられるPixelCNNを大幅に高速化

 

【論文名】Parallel Multiscale Autoregressive Density Estimation

【URL】https://arxiv.org/pdf/1703.03664.pdf

【abstract翻訳】

PixelCNNは、自然画像の密度推定でstate-of-the-artを達成している。トレーニングは高速ですが、推論にはコストがかかる。ピクセルごとに1つのネットワーク評価が必要で、つまりN個のピクセルについてはO(N)である。 これはアクティベーションをキャッシングすることで高速化できるが、それでも各ピクセルを順次生成する。 本研究では、ある画素群を条件付き独立としてモデリングすることにより、より効率的な推論を可能にする並列化PixelCNNを提案する。 当社の新しいPixelCNNモデルは、O(N)ではなくO(log N)サンプリングという、以前に匹敵する密度推定と数倍のスピードアップを達成し、512x512の画像を実際に生成することができる。 私たちはモデルをクラス条件付き画像生成、テキスト - イメージ合成、およびアクション条件付きビデオ生成で評価し、効率的なサンプリングを可能にする非ピクセル自己回帰密度モデルの中で最良の結果を得ることを示す。

 

【abstract】

PixelCNN achieves state-of-the-art results in density estimation for natural images. Although training is fast, inference is costly, requiring one network evaluation per pixel; O(N) for N pixels. This can be sped up by caching activations, but still involves generating each pixel sequentially. In this work, we propose a parallelized PixelCNN that allows more efficient inference by modeling certain pixel groups as conditionally independent. Our new PixelCNN model achieves competitive density estimation and orders of magnitude speedup - O(log N) sampling instead of O(N) - enabling the practical generation of 512x512 images. We evaluate the model on class-conditional image generation, text-to-image synthesis, and action-conditional video generation, showing that our model achieves the best results among non-pixel-autoregressive density models that allow efficient sampling.

 

 

DeepMindの論文投稿速度は凄まじい。それでもなおGoogleには余力がありそうなのが恐ろしい。彼らは私たちがDeepLearningをLuarで実装している時にTensorflow使って研究していたのだから、差がつくのも宜なるかな。

 

以下が論文内にある結果

・4×4から鳥の画像を生成

f:id:latebloom:20170319102254p:plain

 

・テキストから画像の生成(Captionsが与えたText、Samplesが4×4から256×256で生成したもの

f:id:latebloom:20170319104557p:plain

 

 

 

20年近くAIと働いてきたBradfordによる、2017年のAIスタートアップの行く先予測【生き残るのは?】

面白い記事があったのでまとめました。

  1. Botは崩壊
  2. Deep Learningはコモディティ化
  3. AIはVCにとって新たなcleanTech (アメリカで盛大に盛り上がり散った)
  4. MLaaS(Machine Learning as a Service)はまた死ぬ
  5. フルスタックな垂直型(業界を絞った)AIスタートアップだけが実質的に機能する

簡単にまとめると、以上ですね。

www.bradfordcross.com

 

それぞれでBradford Crossが述べていることを見ていきます。

  • 1, Botは崩壊する
  • 2, Deep Learningはコモディティ化
  • 3, AIはVCにとって新たなcleanTech
  • 4, MLaaS(Machine Learning as a Service)はまた死ぬ
  • 5, フルスタックな垂直型(業界を絞った)AIスタートアップだけが実質的に機能する
  • 私たちについて

 

続きを読む