Academication-AI

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

【研究者向け】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