Hilbert maps: Scalable continuous occupancy mapping with stochastic gradient descent
http://web.it.usyd.edu.au/~framos/Publications_files/HilbertMapsIJRR16Final.pdf
Abstract
今日の膨大な量のデータロボットは、ロボットが動作する空間をモデル化するための高速でスケーラブルな統計的ツールの開発を動機付けています。側面：（１）世界をグリッドセルに先験的に区別することを想定していないため、任意の解像度で地図を提供することができる。 （２）測定値間の空間的関係を自然に捉えるので、外れ値に対してよりロバストであり、より良い汎化性能を有する。ヒルベルトマップと呼ばれるこの手法は、ロジスティック回帰分類器が学習されるヒルベルト空間でデータを射影する高速カーネル近似の計算に基づいています。我々はこのアプローチが各測定がオンラインの方法で学習中に一度だけ処理される効率的な確率的勾配最適化を可能にすることを示す。 3種類の近似で結果を示します。 Nyström;そして新しいスパース射影。また、センサーや位置の誤差によるレーザースキャンの位置の不確かさなど、確率分布を入力として受け入れるようにアプローチを拡張します。この拡張バージョンでは、一般的なベンチマークデータセットを使用して、2次元と3次元で実験が行われました。さらに、同時位置確認およびマッピング中のループ閉鎖前後の軌跡更新など、データの大きな変化を処理するための技術の適応能力の分析も含まれる。
1. Introduction
3次元（3D）空間の物理的性質を表現することは、操作や握りから自律的なナビゲーションまで、ロボット工学の中心です。環境を特徴付ける多くの物理的性質の中で、ロボットが相互作用する必要がある固体物体によって特定の点が占められる可能性は確かに最も重要なものの1つです。占有率のマップを作成する従来の技術は、一定のサイズのセルへの領域の識別に依存し、センサー・モデルまたは尤度関数を適用してセンサー・データ、たとえばレーザースキャンなどの占有データを推定します。あるいはソナー（Elfes、1987、1989）。そのような技術の主な制限の１つは、グリッド内の各セルが互いに独立しており、マップ全体に対する事後計算が各セルに対して別々に実行されるという仮定である。この仮定は、セル間の重要な空間的関係を無視し、セル間に一連の「ギャップ」があるマップにつながります。たとえば、観測されていないセルは、占有される可能性が高いセルの隣にある場合でも、占有される可能性は0.5です。同じ解像度で環境を表現するのに必要なセルの数が、必要な観測の数と同様に指数関数的に増加する3Dマップでは、問題はより深刻になります。マッピングされる領域が比較的小さく、観測の密度が大きい屋内環境では、占有グリッドは一般的に高速でコンパクトな表現を提供するのに十分です。しかしながら、まばらな観測で広い3D屋外領域を表現することは、依然として挑戦的です。 これらの問題のいくつかを解決するための試みとして、Gaussianプロセス占有マップ（GPOM）（O’Callaghan and Ramos、2012; O’Callaghan et al。、2009）が提案されました。アイデアは、位置を占有クラスにマッピングする関数の空間よりも先にガウス過程を使用することです。この方法は連続的であり、すなわち空間の事前の識別を必要とせず、そしてノンパラメトリックである。表現の複雑さは、データポイントの数とともに増大します。最終的なガウス過程分類子モデルは、パラメータ化共分散関数を通して空間的関係を直接捉え、過程の不確実性を自然にコード化する原理的確率的後写像を生成するので、空間表現において得たい多くの利点を有する。主な欠点は、データをより小さな集合に近似または分割することなく、データのサイズに比例して拡大縮小するという計算上の複雑さです。
本稿では、連続稼働率マッピングのより簡単で高速なアプローチを提案します。最近の最適化の進歩（Zhang、2004）と効率的なカーネル近似を利用して、観測を再生カーネルHilbert空間（RKHS）に投影する高次元特徴ベクトルに作用する線形識別モデルで世界の占有特性を表します（ Scholkopf and Smola、2001）。モデルを訓練するための目的関数はパラメータにおいて凸であり、したがって大域的最適値を見つけることができる。さらに、確率的勾配降下法（ＳＧＤ）を用いてモデルを訓練および更新して、計算を観測数とは理論的に無関係にすることができる。我々のアプローチの鍵は、そのドット積が周知の動径基底関数カーネル（ＲＢＦ）に近似する多数の特徴を迅速に生成することである（Scholkopf and Smola、2001）。 RBFカーネルは、物理的世界の複雑さを漸近的に表すことができる無限次元空間への特徴マッピングと見なすことができます。カーネルを近似するための3つの解決策を提示します。 （1）最初のものは最近提案されたRKS（Random Kitchen Sinks）に基づいている（Rahimi and Recht、2008、2009）。 （2）2つ目は、カーネルマシンで非常に人気のあるNystrom近似に基づいています（Williams and Seeger、2000b）。 （3）最後に、疎な特徴を生成し、局所的な情報をよりよく捉える、新しい特徴マッピングを紹介します。また、これらの機能を一般化して、確率分布を入力として受け入れることで、位置確認エラーやセンサーノイズを処理するためのより堅牢な方法を示します。 GPOMとは対照的に、私たちの方法は線形時間で更新することができ、大量のデータでうまくスケーリングできます。それはロボット工学におけるいくつかのタスク、例えば握ることや経路計画などに対処するために使うことができます。このモデルは、環境の占有特性を表す関数を提供します。したがって、把握するための表面の勾配の計算が可能になります。さらに、経路計画の最適化手順にシームレスに統合して、衝突の可能性を最小限に抑えることができます。論文1の技術的貢献は次のとおりです。
局所情報をより良く保存し、より速いＳＧＤ反復をもたらす、新規のスパースヒルベルト空間の特徴３。
原理的な方法で、測定位置の不確実性に対処するための入力として確率分布を受け取る方法の一般化。
この論文は以下のように構成されています。 SGDによるオンライン学習のための目的関数と最適化については3章で紹介する。ヒルベルトマップ、GPOMの関係と最近の関連学習に関連する機械学習の結果について議論する。 セクション4でこのテクニックの重要な局面。ベンチマークデータセットと比較に関する実験はセクション5に提示されます、そして、将来の仕事のための考えとの結論はセクション6にあります。
2. Hilbert maps
3. Online learning
4. Relationship to other methods
SVMs: 機械学習の文献には、これまでに説明した方法に似たいくつかの分類子があり、それぞれ長所と短所があります。特に、Pegasos（Singer and Srebro、2007）は、高価な2次計画法の最適化が主問題に適用されるSGDに置き換えられた、別のSVM定式化です。著者らは、この方法が強い収束特性を持つトレーニングポイントの数に応じてはるかに優れたスケールになることを示しています。しかしながら、Pegasosは、我々の方法が異なった損失関数を使用していたので、カーネル特徴近似について訓練されていなかった。 SVMと同様に最大マージン損失やヒンジ損失を使用せず、ロジスティック回帰式を選択した主な理由は、ロジスティック回帰で自然に得られた結果の確率論的解釈に関連しています。例を図1に示します。ここでは、2つの方法で作成された同じ連続稼働率マップを示しています。 SVMは確率論的解釈を直接生成しないので、人工確率論的出力は一般にPlatt（1999）の方法を用いて得られる。しかし、図が示すように、これは問題を引き起こします。探検されていない領域、官能的な情報がない状態では、高い確信をもって占有領域または非占有領域に分類されます。逆に、ロジスティック回帰式では、未調査領域は予想どおり50％の確率で占有されます。
GPOM: この作品はまた、GPOM（O'Callaghan and Ramos、2012; O'Callaghan et al。、2009）からのアイデアを借用しています。両方とも連続的に空間を表現しようとしています。どちらも占有率の確率論的解釈を行い、どちらもカーネルを利用して高次元空間のデータポイントを表します。ただし、大きな違いもあります。 GPOMはノンパラメトリックです。すなわち、モデルの複雑さはデータ点の数と共に増大する。近似値がないと、潜在的に大きいグラム行列を反転する必要があるため、GPOMにはO（n3）のコストがかかります。ここで、nはデータポイントの数です。 ＧＰＯＭは、関数空間マッピング入力に先行してガウスプロセスを仮定する。分類出力（事後）を取得するには、シグモイド型の尤度を事前確率と組み合わせて、近似が必要な難解な積分を含む式を作成します。 GPOMは、ガウス過程の予測平均を中心とした点推定値で尤度優先周辺化を解決しますが、これは事後確率の不正確な確率推定値をもたらす可能性があります。 GPOMでは、ベイズ法として、周辺尤度を最大化することでモデルの（ハイパー）パラメータを自動的に取得できます。 GPOMとは対照的に、Hilbertマップはロジスティック回帰分類器に基づいて、はるかに単純な判別モデルに基づいて構築されています。正確な補間を提供することにおける方法の能力の大部分は、ヒルベルト空間埋め込みをＳＧＤの速度で近似する特徴の組み合わせによるものである。ヒルベルト写像はパラメトリックモデルであり、学習と推論の両方の複雑さはデータ点の数とは無関係ですが、むしろ特徴の数mに依存します。現在の形式ではヒルベルト写像は頻繁に使われる手法であり、そのため正則化パラメータの指定が必要です。しかし、実験では、正則化パラメータとカーネルパラメータを簡単に調整でき、値が環境によって大きく変わる必要がないことがわかりました。ヒルベルト写像は、妥当なコストでGPOMに比べて著しい計算上の利点を提供します。ヒルベルト空間近似のためにわずかに劣った補間力。ヒルベルト写像は将来の研究で論じられるように変分ベイズロジスティック回帰式に拡張することができることにも注意してください。表1は、GPOMとHilbertマップの主な違いをまとめたものです。
RKS: ＲＫＳに基づくが、高次元データに対するより優れたスケーラビリティ特性を有する別の種類のカーネル近似が、Ｌｅ ｅｔ ａｌ。 （2013）。著者らは、特徴の計算コストをO（nmd）からO（nm log d）にどのように改善するかを示します。ここで、mは特徴の数、nはサンプルの数、dは入力の次元です。この方法は、式（７）のランダム行列ｓを生成するための高速因数分解スキームに基づいている。この拡張は、コンピュータビジョンなどの高次元データに関する問題では興味深いものですが、3Dの場合、データの次元が多くても3になるため、占有マッピング問題では効果が少なくなります。いくつかの回帰と分類の問題についてRKSとNystromの特徴を比較した興味深い研究がYang et al。に発表されました。 （2012）。著者らは、式（8）の固有スペクトルD ˆの間に大きなギャップがある場合、Nystrom法が印象的な結果を生み出し、RKSを凌駕することを示しています。実験で見るように、これは、Nystrom法が同様の精度を達成するためにはるかに小さな特徴のセットを必要とした占有率マッピング問題で観察されました。ただし、Nystrom法はデータに依存するため、RKSのようにフィーチャを事前計算することはできません。
Additive kernels: コンピュータビジョンでは、いくつかのカーネルは、各次元に独立して適用されるカーネル関数の合計として書くことができる：ｋ（ｘ、ｘ）＝ Ｄ ｄ ＝ １ ｋ（ｘ ｄ、ｘ ｄ）。 これらのカーネルの例には、インターセクション、C、Hellinger、Jensenのいずれかのカーネルが含まれます。 このクラスのカーネルに対して、VedaldiとZisserman（2012）は、カーネルのスペクトル表現が合計で近似されるBochnerの定理の離散版に基づく異なる近似を提案しました。 それらの近似は、物体認識や歩行者認識などの一般的なコンピュータビジョンタスクを同様の精度で大幅にスピードアップしました。 RKSとLe et al。のFastfood近似と同じように。 （2013）、ヒルベルト写像はまた加法的な核で実行されることができます。 しかしながら、そのような近似の主な利点は高次元の問題に取り組むことにあり、それゆえこれらの特徴が占有率の表現のような低次元の問題にもたらす利点は不明である。
5. Experiments
6. Conclusion and future work
この論文は新しい占有マッピング技術、ヒルベルトマップを紹介した。この手法はいくつかの点で占有グリッドマップを改善しますが、特に、空間の離散化、任意の解像度でのマップのレンダリングを必要としません。観測の絶対位置がSLAM手順の一部として部分的に知られているか、または推定される場合に対処するために、我々は観測の空間的位置にわたる確率分布を埋め込むための方法を提案する。この技術は、各データポイントが学習中に一度だけ訪問されるときでさえ強い収束保証が存在するＳＧＤによる効率的な学習を可能にするために、カーネルマシンにおける最近の進歩、特にカーネル近似を探求する。実験結果は、作成されたマップが外れ値の影響を受けにくく、根本的な不確実性を表現する上でより正確であることを示す非常に有望なものです。最良の結果は、Nyströmとスパース機能で達成されました。どちらも誘導点の指定が必要です。これらの誘導点は、グリッド上に配置することも、k-meansなどのクラスタリング手順を使用して自動的に取得することもできます。より多くの観測が捕捉されるにつれてより多くの特徴を追加的に追加すること、またはより高い精度が必要とされる地図の領域内の特徴の数を増加させることは両方ともモデルの適応性を改善するための興味深い将来の方向である。 SGDに基づくオンライントレーニング戦略の重要な利点は、ループクロージャなどのナビゲーション中に大きな軌道修正が行われた後にマップを更新できる速度に関連しています。ループが閉じると、収束するまで更新されたデータに対してSGDを実行して、新しい更新されたマップを作成できます。 この手順を機械学習問題で使用して、シーケンシャルデータ内の非定常性の問題に対処できます（「共分散シフト」としても知られています（Sugiyama et al。、2007））。ヒルベルトマップの利点は、SGDは非常に高速で安価に実行できるため、再トレーニングを効率的に実行できることです。ヒルベルトマップは、ロボットシステム内の連続的な占有表現として多くの用途があります。例えば、それらは能動的な視覚的セグメンテーションおよび触覚的探査を用いて握るための表現を生成するために使用され得る（Bohg et al。、2010）。ヒルベルトマップによって提供される確率論的出力は、追加の観測が必要とされるより高い不確実性を持つ地域に情報を提供することによって探査を導くことができます。経路計画はまた、Ｙａｎｇ ｅｔ ａｌ。 （2013）。 ランダムツリーの高速探索などの一般的な計画アルゴリズムは、占有特性とそれに関連する不確実性を使用して、環境内の安全境界について推論することができます。これは、無人航空機による雑然とした自然環境での計画のために実証されています。ヒルベルト写像上の軌道の機能的最適化に基づく経路計画戦略の開発の可能性もある。連続表現として、ヒルベルト写像はより安全な軌道を見つけようとする最適化アルゴリズム内で直接利用することができる。空間座標に関する占有関数の勾配もまた最適化プロセスをスピードアップするために容易に得ることができる。最後に、最近の結果は、連続占有率マップがモンテカルロ局在化に利用でき、グリッドマップと同等の定式化よりも優れた結果を達成できることを示唆している（Hata et al。、2016）。ヒルベルトマップの連続表現を直接活用する適切な尤度モデルを使用すると、特に不確実性のレベルが高い場合、ローカライズをより堅牢にすることができます。 将来の作業にはいくつかの道があります。まず、占有グリッドマップとオクトマップの両方が特定の機能を備えたヒルベルトマップの特定のケースであることを示すのは簡単です。グリッドの場合、入力点の位置が正方形または立方体のどちらにあるかに応じてフィーチャが0または1として定義されていると、Hilbertマップはgridmaps / Octomapsと同様の出力を生成します。これは、この方法の柔軟性を強調し、より多くの機能開発または非常に異なる特性を有する機能の組み合わせに対する展望を開く。第二に、この方法は、頻度論的手法として定式化され、カーネルと正則化パラメータの手動調整を必要とします。ベイジアン最適化などの最近の技術をこの目的のために使用することができるとしても（Snoek et al。、2012）、もっと原理的な解決策はベイジアン学習課題として問題を定式化することである。残念なことに、これは事後的手法に対する非分析的な解決策につながり、変分法などの近似手法を適用する必要があります。また、目的関数は凸ではなくなり、この場合のSGD収束保証はあまり開発されていません。それにもかかわらず、これはさらなる調査のための興味深い分野のままです。最後に、占有マッピングは、この手法を適用できる他の多くの問題のほんの一例です。オンラインで効率的な方法で移動ロボットによって捕捉されたデータのストリームに基づいて確率的予測を提供することであるアルゴリズムの基本的な考えは、他にも多くの用途がある。例えば、このアルゴリズムは、強化学習において最適な方針を学習するために、またはオンライン物体認識を実行するために使用することができる。
