新規記事の投稿を行うことで、非表示にすることが可能です。
2021年04月02日
グーグルリサーチ： アルゴリズムの基礎と理論 2021年1月12日⑭
グーグルリサーチ： アルゴリズムの基礎と理論 2021年1月12日⑭
2020年は、アルゴリズムの基礎と理論に関する私達の研究にとって、いくつかのインパクトのある研究発表や注目すべき結果が得られ、実り多い年となりました。最適化の分野では、エッジ・ウェイト・オンライン二者択一マッチングに関する論文で、オンライン競争アルゴリズムのための新しい手法を開発し、効率的なオンライン広告割当に応用できるエッジ・ウェイト・バリアントの30年来の未解決問題を解決しました。このオンライン・アロケーションの研究と並行して、多様性や公平性の制約が追加された様々なモデルに一般化するデュアルミラー降下法を開発し、オンライン・スケジューリング、オンライン学習、オンライン線形最適化における機械学習アドバイスを含むオンライン最適化のトピックに関する一連の論文を発表しました。また、別の研究成果では、密なグラフにおける古典的な二部構成のマッチングを50年ぶりに改善しました。最後に、別の論文では、凸体をオンラインで追いかけるという長年の未解決問題を、『The Book』のアルゴリズムを使って解決しました。
私達はまた、スケーラブルなグラフ・マイニングとグラフ・ベースの学習に関する研究も継続して行い、NeurIPS'20では、Graph Mining & Learning at Scale Workshopを開催し、グラフ・クラスタリング、グラフ・エンベッディング、因果推論、グラフ・ニューラル・ネットワークなど、スケーラブルなグラフ・アルゴリズムに関する研究を紹介しました。このワークショップの一環として、私達は、MapReduceのような標準的な同期計算フレームワークをBigTableのような分散ハッシュ・テーブルで補強することにより、いくつかの基本的なグラフ問題を理論的にも実際的にもより速く解決する方法を示しました。私達の広範な実証研究は、階層型クラスタリングと連結成分の大規模並列アルゴリズムにおける分散ハッシュ・テーブルの使用にヒントを得たAMPCモデルの実用的な妥当性を検証し、理論的な結果は、これらの問題の多くを一定の分散ラウンドで解く方法を示し、私達の以前の結果を大幅に改善しました。また、PageRankやランダムウォークの計算においても、指数関数的な高速化を達成しました。グラフ・ベースの学習の面では、機械学習で使用するグラフを設計するためのフレームワークであるGraleを発表しました。さらに、よりスケーラブルなグラフ・ニューラル・ネットワーク・モデルに関する研究を紹介し、PageRankを使ってGNNでの推論を大幅に高速化できることを示しました。
コンピュータ・サイエンスと経済学が交差する分野であるマーケット・アルゴリズムでは、広告オークションのインセンティブ特性の測定、両面市場、広告選択における注文統計の最適化など、私達はより良いオンライン市場を設計するための研究を続けています。繰り返しオークションの分野では、現在の市場や将来の市場の予測や推定の誤りに対して動的メカニズムが頑健になるようなフレームワークを開発し、証明可能なほどタイトで低後悔の動的メカニズムを実現しました。また、幾何学的な基準を用いて、どのような場合に漸近的に最適な目的を達成できるのかを明らかにしました。また、実際に使用されている様々な予算管理戦略の均衡結果を比較し、収益と買い手の効用の間のトレードオフへの影響を示し、そのインセンティブ特性に光を当てました。さらに、最適なオークション・パラメータの学習に関する研究を継続し、収益損失を伴うバッチ・ラーニングの複雑さを解決しました。また、最適な後悔を設計し、文脈に沿ったオークション価格設定のための組み合わせ最適化を研究し、オークションのための新しい能動学習フレームワークを開発し、公示価格オークションの近似値を改善しました。最後に、広告オークションにおけるインセンティブの重要性に触発され、広告主がオークションにおけるインセンティブの影響を研究するのに役立つことを期待して、メカニズムがインセンティブの互換性からどれだけ逸脱しているかを定量化するデータ駆動型の指標を紹介します。
英語原文はこちら
https://ai.googleblog.com/2021/01/google-research-looking-back-at-2020.html
2020年は、アルゴリズムの基礎と理論に関する私達の研究にとって、いくつかのインパクトのある研究発表や注目すべき結果が得られ、実り多い年となりました。最適化の分野では、エッジ・ウェイト・オンライン二者択一マッチングに関する論文で、オンライン競争アルゴリズムのための新しい手法を開発し、効率的なオンライン広告割当に応用できるエッジ・ウェイト・バリアントの30年来の未解決問題を解決しました。このオンライン・アロケーションの研究と並行して、多様性や公平性の制約が追加された様々なモデルに一般化するデュアルミラー降下法を開発し、オンライン・スケジューリング、オンライン学習、オンライン線形最適化における機械学習アドバイスを含むオンライン最適化のトピックに関する一連の論文を発表しました。また、別の研究成果では、密なグラフにおける古典的な二部構成のマッチングを50年ぶりに改善しました。最後に、別の論文では、凸体をオンラインで追いかけるという長年の未解決問題を、『The Book』のアルゴリズムを使って解決しました。
私達はまた、スケーラブルなグラフ・マイニングとグラフ・ベースの学習に関する研究も継続して行い、NeurIPS'20では、Graph Mining & Learning at Scale Workshopを開催し、グラフ・クラスタリング、グラフ・エンベッディング、因果推論、グラフ・ニューラル・ネットワークなど、スケーラブルなグラフ・アルゴリズムに関する研究を紹介しました。このワークショップの一環として、私達は、MapReduceのような標準的な同期計算フレームワークをBigTableのような分散ハッシュ・テーブルで補強することにより、いくつかの基本的なグラフ問題を理論的にも実際的にもより速く解決する方法を示しました。私達の広範な実証研究は、階層型クラスタリングと連結成分の大規模並列アルゴリズムにおける分散ハッシュ・テーブルの使用にヒントを得たAMPCモデルの実用的な妥当性を検証し、理論的な結果は、これらの問題の多くを一定の分散ラウンドで解く方法を示し、私達の以前の結果を大幅に改善しました。また、PageRankやランダムウォークの計算においても、指数関数的な高速化を達成しました。グラフ・ベースの学習の面では、機械学習で使用するグラフを設計するためのフレームワークであるGraleを発表しました。さらに、よりスケーラブルなグラフ・ニューラル・ネットワーク・モデルに関する研究を紹介し、PageRankを使ってGNNでの推論を大幅に高速化できることを示しました。
コンピュータ・サイエンスと経済学が交差する分野であるマーケット・アルゴリズムでは、広告オークションのインセンティブ特性の測定、両面市場、広告選択における注文統計の最適化など、私達はより良いオンライン市場を設計するための研究を続けています。繰り返しオークションの分野では、現在の市場や将来の市場の予測や推定の誤りに対して動的メカニズムが頑健になるようなフレームワークを開発し、証明可能なほどタイトで低後悔の動的メカニズムを実現しました。また、幾何学的な基準を用いて、どのような場合に漸近的に最適な目的を達成できるのかを明らかにしました。また、実際に使用されている様々な予算管理戦略の均衡結果を比較し、収益と買い手の効用の間のトレードオフへの影響を示し、そのインセンティブ特性に光を当てました。さらに、最適なオークション・パラメータの学習に関する研究を継続し、収益損失を伴うバッチ・ラーニングの複雑さを解決しました。また、最適な後悔を設計し、文脈に沿ったオークション価格設定のための組み合わせ最適化を研究し、オークションのための新しい能動学習フレームワークを開発し、公示価格オークションの近似値を改善しました。最後に、広告オークションにおけるインセンティブの重要性に触発され、広告主がオークションにおけるインセンティブの影響を研究するのに役立つことを期待して、メカニズムがインセンティブの互換性からどれだけ逸脱しているかを定量化するデータ駆動型の指標を紹介します。
英語原文はこちら
https://ai.googleblog.com/2021/01/google-research-looking-back-at-2020.html