株式会社ブレインパッドの2025年新卒研修資料です。数理最適化について扱っています ※ 本資料の公開は、ブレインパッドをもっとオープンにする取り組みOpenBPの活動です。 [OpenBrainPad Project] https://brainpad.github.io/OpenBrainPad/
皆さんはベイズ最適化という言葉を聞いたことがありますか? 機械学習やAIの世界では非常に重要な概念ですが、初めて耳にする方には少し難しく感じるかもしれません。 この記事では、ベイズ最適化の基本から応用まで、専門知識がなくても理解できるよう解説していきます💡 AIや機械学習の効率を大幅に向上させるこの技術について、一緒に学んでいきましょう。 ベイズ最適化とはベイズ最適化とは、形や特性がよくわからない関数(ブラックボックス関数と呼ばれます)の最適値を効率的に見つけるための手法です。簡単に言えば、「試行回数を最小限に抑えながら、最良の結果を得るための方法」と言えるでしょう。 たとえば、あるケーキのレシピで「どれくらいの砂糖を入れれば最も美味しくなるか」を考えてみましょう。全ての量を試すのは時間と材料の無駄です。ベイズ最適化を使えば、少ない試行回数で最適な砂糖の量を見つけることができます。 この
※本記事には解法のネタバレが大いに含まれます。閲覧にはご注意ください。 はじめに こんにちは!AtCoder Heuristic Contest楽しんでいますでしょうか? 先日はAtCoderさん主催のAHC初心者向けオンサイトイベント「AtCoder Heuristic First-step Vol.1」の講師役として解説をさせて頂きました。 私の貪欲法解説スライドやtakumi152さんの焼きなまし法解説スライドもありますので、是非ご覧ください! atcoder.jp さて、こうやって各手法を学んだ初心者の方が次に直面する壁は「原理は分かったけど、実際の問題にどうやって適用すればいいのか分からない」だと思います。ABCの各種アルゴリズムも同じですよね。「アルゴリズムを知っている」と「そのアルゴリズムを使いこなせる」の間には大きな壁が存在します。 そこで実際の問題で練習を重ねていく必要が
NTTは2月19日、計算機科学の未解決問題を解決したと発表した。同社が解決したのは、著名なデータ構造として知られる「二分決定グラフ」に関する未解決問題。今回示した理論は、計算機科学の著名な教科書にあった記述の誤りを指摘しており、研究チームの修正案が承諾され、内容が改訂されるという。 二分決定グラフとは、集合のあつまりである「集合族」を表現するデータ構造だ。例えば、集合{1, 2}と集合{2, 3}からなる集合族は、{{1, 2},{2, 3}}と表現できる。集合族は汎用性が高く、さまざまなデータ構造を表現する際に使われる。その例には、ある地点から別の地点までの移動経路の組合せや、同時に利用可能なクーポンの組合せなどがある。 ネットワークの通信パターンを表現する集合族、二分決定グラフの例 図では16個の通信パターンを16個の集合からなる集合族で表現し、それを11個のノード(節点)を結ぶ線から
はじめに AutoSamplerは、状況に応じてOptunaに実装されているものの中からSamplerを自動で選択し、解の探索を行います。ユーザは、下記のコード例のようにAutoSamplerを使用するだけで、最適化アルゴリズムの使い分けを意識することなく、Optunaのデフォルトと比較して同等かそれ以上の最適化パフォーマンスを得ることができます。 study = optuna.create_study( sampler=optunahub.load_module( "samplers/auto_sampler" ).AutoSampler() # 内部でアルゴリズムを自動選択 ) 本記事では、OptunaHubに10月31日に公開されたAutoSamplerについて、「なぜ最適化アルゴリズムの使い分けが必要なのか」といった背景やSamplerの自動選択ルールの設計方針について共有し、その
import math import random import numpy as np class PSO(): def __init__(self, particle_max, inertia=0.9, global_acceleration=0.9, personal_acceleration=0.9, ): self.particle_max = particle_max self.inertia = inertia self.global_acceleration = global_acceleration self.personal_acceleration = personal_acceleration def init(self, problem): self.problem = problem # 初期粒子群を生成 self.global_best = None self
更新履歴 最適解と探索範囲を追記しました。 2016/11/29 @fimbulさん 編集リクエストありがとうございました。修正しました。 2017/7/10 @tomochiiiさん 編集リクエストありがとうございました。Easom functionを引用元の数式に修正、Schaffer function N. 2とN. 4の数式の修正 2018/5/9 @applicative62045 さん 編集リクエストありがとうございました(編集リクエストの確認遅くなりました。2019/12/31記載) Griek functionを修正 2019/12/31 @okamoto6496 さん 指摘ありがとうございました。Five-well potential functionの数式を修正。 2020/01/20 @higedura さん 指摘ありがとうございます。Bukin function N
はじめに 最適化アルゴリズムにおけるメタヒューリスティクスアルゴリズムを主に実装していきます。 メタヒューリスティクスは、問題に依存しないで解を得られることが最大の利点ですが、 実際の問題に対してどうアプローチしていいかがいまいち分かりにくかったのでまとめてみました。 やりたいことは、 できる限りわかりやすく一般化して、問題に対する共通のインターフェースをつくる 各アルゴリズムを比較 です。 また、各アルゴリズムについては別記事にして少しずつ上げていく予定です。 (記事を上げたらリンクをつけていきます) コードはgithubにあります。 対象アルゴリズム 遺伝的アルゴリズム(Genetic Algorithm: GA) 実数型遺伝的アルゴリズム 人口蜂コロニーアルゴリズム(Artificial Bee Colony: ABC) 粒子群最適化(Particle Swarm Optimizat
こんにちは。駅メモエンジニアの id:dorapon2000 です。 約半年前の 6 月 1 日にステーションメモリーズ!(駅メモ!)10 周年を記念してタイムラインと地図の切替機能をリリースしました。大変好評を頂いておりとても嬉しいです。 今回は、その機能の中で毎秒最寄り駅を計算するロジックをどのように実現しているのかについてお話します。様々なスペックの端末で遊ばれているため、可能な限りリソースを節約するような工夫をしました。堅い言い方をすれば、過去の計算情報を使った最近傍探索アルゴリズムを実装しました。 記事中のサンプルコードは TypeScript で記述しています。 2024/11/22 追記: はてなブックマークでのご指摘ありがとうございます。 ご指摘をいただいた「事前計算の時間計算量」と「基準点と現在地の距離が近すぎるとき」の説明部分を修正しております。 誤:事前計算を O(N
はじめに 7月からOptunaHubという新しいOptuna向け機能共有プラットフォームのベータ版を提供中です。今回は新たに導入されたImplicit Natural Gradient Optimization (INGO) [1]という自然勾配法ベースの最適化アルゴリズムについて紹介します。INGOは進化計算における強力な手法である CMA-ES (共分散行列適応進化戦略) に近いアルゴリズムで、本記事の実験ではCMA-ESよりも良い性能を示しました。 OptunaHubに登録されたINGOアルゴリズム この節ではOptunaHubに登録したINGOのSamplerを実際に実行してみます。今回の実装はYuhei Otomoさんに協力して頂きました。実装はこちらで見ることができます。 このSamplerの実装にあたり、簡単な単体テストでの動作確認やベンチマーキング結果が論文の主張と整合して
はじめまして、ZOZO研究所福岡の家富です。画像検索システムのインフラ、機械学習まわりを担当しています。 今回は画像検索システムでお世話になっているAnnoyについてじっくり紹介したいと思います。 目次 目次 Annoyについて 近傍探索について Annoyのソースコードを読むときのポイント AnnoyIndexというクラスのインスタンスを作る インストール過程について PythonのC/C++拡張 Annoyの実装 1. add_item 2. build 3. get_nns_by_vector 4. build再考 他に問題となる点について CPU依存部分 ディスクかメモリか まとめ さいごに Annoyについて Annoyは、SpotifyによるPython近傍探索ライブラリです。 github.com 弊社のテックブログでも以前に取り上げています。 techblog.zozo.c
すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。 Othello is Solved : https://arxiv.org/abs/2310.19387 「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と本記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。 今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。 弱解決と強解決とでは、
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
The game of Othello is one of the world's most complex and popular games that has yet to be computationally solved. Othello has roughly ten octodecillion (10 to the 58th power) possible game records and ten octillion (10 to the 28th power) possible game positions. The challenge of solving Othello, determining the outcome of a game with no mistake made by either player, has long been a grand challe
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く