人工知能（AI）というと機械学習や深層学習が注目されがちだが、実はそれはAIの半分にすぎない。あとの半分、いわば「アナザーAI」は企業の生産計画や物流などで重要な役割を果たす「最適化AI」だ。最適化AIを実現するための技術が、「焼きなまし法」や「ビームサーチ」などの「ヒューリスティックアルゴリズム（メタヒューリスティクス）」である。この連載では、競技プログラミングサービスを提供しているAtCoderの高橋直大社長が、アルゴリズムに対する深い知識を生かし、最適化AIを活用している企業を訪ねて取り組みを探っていく。 今回は、飲食や美容などさまざまな領域で消費者向けや企業向けのサービスを提供しているリクルートを訪問した。データ関連技術を統括する同社プロダクト統括本部 プロダクト開発統括室 データ推進室 データテクノロジーユニットの阿部直之ユニット長に、最適化AIを使ったサービスの取り組みを聞いた
はじめに ビームサーチ（Beam Search）は貪欲法の高速性と全探索の正確性にトレードオフを持たせたヒューリスティック探索手法としてよく知られています。主に文章生成や機械翻訳の分野で活躍している他、私の所属する競技プログラミングの界隈においてもヒューリスティック系コンテストでよく利用されます。一方で、探索アルゴリズムの研究分野においては、ビームサーチの探索方法を変換してより高性能な探索アルゴリズムを生み出そうとする動きも見られます。本記事では、ビームサーチを変換したアルゴリズムの1つであるビームスタックサーチ（Beam-Stack Search）を解説します。ビームスタックサーチとは何者かを簡単に言うとビームサーチを最適解の発見を保証できる形に変換したものと言えます。以下では、まずビームサーチの提案論文を紹介し、当論文を読んでの私見を述べ、最後にビームスタックサーチのアルゴリズムを解説
大幅な加筆改訂を加えた最新版はこちらです： https://speakerdeck.com/eumesy/optimal-transport-for-natural-language-processing --- 最適輸送の使い方 〜最適輸送の直感的理解のための単語埋込入門 兼 最適輸送入門〜 【これは何？】 自然言語処理を中心に多くの利用例を挙げながら、最適輸送の直感的な理解を目指すスライドです。 「こんな風に使うことができるんだ… 面白い道具じゃん」「こういう使い方をしたかったらこういうキーワードで調べれば良いのね」と知識にアンカーを張ることが目的です。より深く知りたい人のための参考文献もできるだけ潤沢に加えました。 また、例として頻繁に活用する自然言語処理に馴染みがないかたのために、最初に単語埋め込みのチュートリアルをつけてあります。 【コンテンツ】 1. 単語埋込入門 … 「分布仮
パーティクルフィルタ(Particle Filter, 粒子フィルタ、モンテカルロフィルタ)は、複数の粒子にノイズをくわえながら観測データとモデルを元に内部状態を推定しく手法.非線形なモデルに対しても適用でき、粒子の数だけ精度はよくなるが、計算量もその分増え、粒子数がNのときに時間計算量はO(N)となる. 実装が簡単で様々な分野で適用することができるのが特徴. パーティクルフィルタでは、任意の分布を粒子の分布の密度で近似できるため、 非線形のモデルにも適用できている. 以下の絵がパーティクルフィルタの処理の流れの概要です. 上図のワンセットを繰り返していくことで、モデルの状態を推定し続けます. この場合推定しているのはもちろん\(x_n\)です. 左上に描いているように確率分布で確率が高いところにはたくさんの粒子をばら撒くことでその粒子の偏り方(濃度)で分布を近似しています. 変数 \(x
北海道大学(北大)とAmoeba Energyは12月2日、アメーバ生物である真性粘菌の探索行動から着想を得た新型アナログコンピュータを開発し、代表的な組み合わせ最適化問題「巡回セールスマン問題」を解くことに成功したと共同で発表した。 同成果は、北大 量子集積エレクトロニクス研究センターの葛西誠也教授と、Amoeba Energyとの共同研究チームによるもの。詳細は、英オンライン総合学術誌「Scientific Reports」に掲載された。 巡回セールスマン問題とは、セールスマンが決められた数の都市をそれぞれ一度だけ訪問して出発都市に戻るという巡回経路のうち、移動距離が最短となる(もっとも効率のいい)ルートを導くという問題だ。計算複雑性理論において「NP困難問題」に分類され、多項式時間(実用的時間)内で最適解を導く手法が知られていない複雑な組み合わせ最適化問題として有名である。 なお組み
はじめに 凸最適化問題に使われている主双対内点法の解説を目標に、凸最適化の概要を説明します。二次計画がメインターゲットです。 この記事は ソルバーは使ったことあるけど、もう少しアルゴリズムの中身が知りたい 凸最適を学びたいけど、最適化の章までの道のりが長すぎてつらい な方が対象です。いまどき1から凸最適アルゴリズム実装しようなんて物好きは稀だと思いますが、この記事の目的は主双対内点法を実装するための知識を全体的にふわっと理解することです。 二次計画でよく使われる 主双対内点法 と 有効制約法 を以下に可視化しました。解の求め方が全く異なることが分かります。コードはpythonです。 主双対内点法（primal dual interpoint） 内点法の系譜（有効領域の内部を進む） 徐々に相補性残差を減少させて最適解を得る 線形計画、二次計画、非線形計画まで幅広く対応可能 高次元の問題が得意
最適化問題へのモデル化と、基本的なアルゴリズムを俯瞰し、最適化という考え方の基礎をしっかりと固める。大事なことは、いつの時代も変わらない。イメージしやすい具体的な例や、理解の定着にかかせない演習問題も充実！ 【推薦の言葉】 数理最適化は、問題解決のための数学である。今では、その成果を実装したソルバーが簡単に手に入るようになった。直面する問題を解決するには、まずそれをモデル化し、適切な最適化手法を適用するという手順を踏む。 本書は、豊富な実例を通して、モデル化の勘どころを説明し、さらに広範な最適化手法それぞれを、基本から分かりやすく解説している。この分野全般を知るための「最適解」として推薦したい。 ――茨木俊秀(京都情報大学院大学学長) 【サポートページ】 https://sites.google.com/view/introduction-to-optimization/main 【主な内
本記事は、当社オウンドメディア「Doors」に移転しました。 約5秒後に自動的にリダイレクトします。 数理最適化技術は、「データ活用の促進を通じて持続可能な未来をつくる」を企業ミッションとするブレインパッドにとって、必須の注力技術の1つです。 2020年10月1日、大阪大学に、ブレインパッドほかから寄付を受けた「大阪大学数理最適化寄附講座」が開設されました。同講座の教授を務められるのは、数理最適化技術の研究で大変著名な梅谷 俊治先生です。 これを機に、ブレインパッドも数理最適化技術に関するナレッジをさらに＆どんどん高めていこうということで、この公式ブログでも数理最適化に関する連載をスタートします！ こんにちは。CDTO（Chief Data Technology Officer） の太田です。 大阪大学にブレインパッドが寄付を実施し、「大阪大学数理最適化寄附講座」が開設されました。 それを
こんにちは。TIG DXチーム 2の辻です。 先日開催された Go Conference 2019 Autumn に参加/登壇したので、その内容をレポートします。 The Gopher character is based on the Go mascot designed by Renée French. きっかけマネージャーとの面談で、勉強会やカンファレンスで登壇して貢献していきたいと話していたところ Go Conference 2019 Autumn の CfP を募集を見かけたので応募しました。 アイデアの種Go の goroutine や channel を用いることで並行処理をシンプルに書くことができます。基本的な計算をマルチスレッドで高速化する試みは、私が Qiita に書いた Golangを用いた様々な計算の高速化 の記事が詳しいです。 もちろん同じアルゴリズムを用いて G
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
今日のスライド資料です． 「組合せ最適化による問題解決の実践的なアプローチ」 https://t.co/d84vOyD9Xg #opt_night
はじめに：Optunaとは 使い方 インストール 最適化問題の例 問題設定 最適化 最適化の結果 ニューラルネットワークのハイパーパラメータチューニング 問題設定 実装 ハイパーパラメータを引数に取り、ニューラルネットワークを構成する関数 ハイパーパラメータを引数にとり、最適化手法を返す関数 ハイパーパラメータを引数に取り、学習済のモデルを返す関数 ハイパーパラメータを引数に取り、最小化したい値を返す目的関数 いざ最適化 はじめに：Optunaとは OptunaとはPFNが世に送り出した最適化枝刈りライブラリです。 Pythonのコードとして機械学習のコードのどこにでも入れることができ、非常に使いやすいAPIとなっています。大体、結構丁寧なサンプル・解説が公式ドキュメントに既にあるので、分かる方は此方を読むのが一番早いでしょう。 Welcome to Optuna’s documentat
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
