実務につなげる数理最適化
はじめに はじめまして、2023年10月にシニアリサーチャーとして入社したアドバンスドテクノロジーラボ（ATL）の梅谷俊治です。2023年9月まで、大阪大学大学院情報科学研究科にて数理最適化寄附講座教授を務めていました。 本記事では、リクルートのデータ推進室における数理最適化を活用した問題解決の取り組みをご紹介します。 数理最適化は、与えられた制約条件の下で、目的関数を最小（もしくは最大）にする最適化問題を通じて、現代社会における意思決定や問題解決を実現する数理技術の一つです。 近年では、機械学習によるデータ分析や予測の技術開発が進み次々と実用化されています。数理最適化は、それらのデータ分析や予測の結果を踏まえた上で意思決定や計画策定を実現する問題解決における出口を担当する技術です。例えば、オンライン広告などカスタマーに商品を推薦するレコメンデーションでは、機械学習を活用してカスタマーの商
いろんなバンディットアルゴリズムを理解しよう - Qiita
今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Bandit） 順序を最適化するバンディットを使いたい人（Cascading Bandit） バンディットアルゴリズム バンディットの問題設定を説明します。 スロットマシンN台がある スロットマシンの腕を引くと報酬がもらえる 累積報酬を最大化したい バンディットアル
何でも微分する
IBIS 2023 企画セッション『最適輸送』 https://ibisml.org/ibis2023/os/#os3 で発表した内容です。 講演概要: 最適輸送が機械学習コミュニティーで人気を博している要因として、最適輸送には微分可能な変種が存在することが挙げられる。微分可能な最適輸送は様々な機械学習モデルに構成要素として簡単に組み入れることができる点が便利である。本講演では、最適輸送の微分可能な変種とその求め方であるシンクホーンアルゴリズムを紹介する。また、この考え方を応用し、ソーティングなどの操作や他の最適化問題を微分可能にする方法を紹介するとともに、これらの微分可能な操作が機械学習においてどのように役立つかを議論する。 シンクホーンアルゴリズムのソースコード：https://colab.research.google.com/drive/1RrQhsS52B-Q8ZvBeo57vK
How to shuffle songs? - Spotify Engineering
At Spotify we take user feedback seriously. We noticed some users complaining about our shuffling algorithm playing a few songs from the same artist right after each other. The users were asking “Why isn’t your shuffling random?”. We responded “Hey! Our shuffling is random!” So who was right? As it turns out, both we and the users were right but it’s a bit more complicated than that. It also tells
30 分でわかる！アルゴリズムの基本
このスライドは、2022/4/14 に実施されたイベント『問題解決のための「アルゴリズム × 数学」- Forkwell Library #1』の基調講演を加筆修正したものです。実際の講演（35 分）を見たい方は、以下の URL をご覧ください。 https://www.youtube.com/watch?v=2OrsR37_GdM 【目次】 第一章 アルゴリズムとは（pp. 1～19） 第二章 アルゴリズムの例 A：迷路の探索（pp. 20～79） 第三章 アルゴリズムの例 B：プログラムのデバッグ（pp. 80～126） 第四章 アルゴリズムの例 C：映画鑑賞の最適化（pp. 127～154） 第五章 講演のまとめ（pp. 155～162）
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
はじめての自然言語処理 類似文書検索の手法と精度比較 | オブジェクトの広場
自然言語処理とは、人間が自然に使っている英語や日本語などの言語をコンピュータで処理する技術です。自然言語処理でできることには機械翻訳、要約生成、感情分析などがありますが、今回は比較的シンプルな例として類似文書検索に焦点を当ててみたいと思います。類似文書検索はテーマとしては真新しいものではありませんが、本記事では単語の分散表現を用いる手法や Watson Discovery も含めた各種の類似文書検索手法について、日本語データに対して精度比較試験をした結果を紹介します。複数の手法を同一の日本語データで比較した記事はあまり見ないので面白いのではないでしょうか。 1. 始めに 本記事では類似文書検索の各手法について、単語の分散表現を用いる手法や Watson Discovery も含めて精度比較試験をした結果を紹介します。まず各手法の概要を紹介しますが、ここでは数学的な細かい説明などは省くので概
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
【全方位木DP】明日使える便利な木構造のアルゴリズム - Qiita
この記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ
おしゃれなアルゴリズム
本スライドは某LT用に作成しました．厳密性より，非競プロerに向けて面白さを重視しています． 過去問題の解説です．
FFT（高速フーリエ変換）を完全に理解する話 - Qiita
となります。 この $C_i$ を、$0\leq i\leq 2N$ を満たすすべての $i$ について求めるのが今回の目標です。 それぞれ愚直に求めると、$f,g$ の全項を組み合わせて参照することになるので、 $O(N^2)$ です。これをどうにかして高速化します。 多項式補間 愚直な乗算は難しそうなので、$C_i$ の値を、多項式補間を用いて算出することを考えます。 多項式補間とは、多項式の変数に実際にいくつかの値を代入し、多項式を計算した値から、多項式の係数を決定する手法です。 たとえば、$f(x)=ax+b$ という $1$ 次関数があるとします。 $a$ と $b$ の値は分かりませんが、$f(3)=5,f(7)=-3$ がわかっているものとします。 実際に $3,7$ を代入してみると、 $3a+b=5$ $7a+b=-3$ と、連立方程式が立ち、$a,b$ の値が求められま
セピア調フィルタのうんちく - Qiita
セピア調について 18世紀中頃〜19世紀初頭にかけて様々な感光剤による写真が発明され、多くのモノクロ写真が作られました。 それらは経年劣化で白が黄ばみ黒はくすみ、全体として色材のセピア(イカ墨)を思わせる茶色味がかった色になる傾向があった故に、古い写真の色調を表す代名詞としてセピア調(sepia-tone)の言葉が生まれました。 セピア調に退色した写真 セピアインクを使った図面 セピア色について セピア色という単語は、主に以下の３つの意味で使われているようです。 顔料としてのイカ墨のセピア セピアで書かれた古い絵の退色した様子 (セピア調の元ネタ) 古ぼけた写真の色調としてのセピア (本記事がターゲットとするセピア調) 顔料としてのセピアはイカ墨を乾燥させてインクとするもので歴史は古く、紀元前のまだギリシア文化の残る(Greco-Roman)古代ローマの頃には筆記用に使われていました。それ
アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
【画像処理入門】アルゴリズム＆プログラミング
この記事では、画像処理における基本的なアルゴリズムとその実装例（プログラム）についてまとめました。 【画像処理とは】特徴・応用例 画像処理（Image processing）とは、コンピュータを用いて画像に対して次の処理①②を行うことです。 – 処理内容 応用例
canvas上で群れを表現 - Qiita
前置き プログラミング初心者のため、見苦しいコードが多いです。プログラムを組んで何か作るの好きです！ ※ 2020/10/30追記 Pythonでボイドを利用したゲームを作ってみたので良かったら見てください。 【Tkinter実践】Pythonでオリジナルゲームを作る 生き物に関するプログラミングがしたい！ 小さいころから生き物が好きだった。プログラミングで生物の行動シュミレーションなど出来たら面白そうだ。 調べたらボイドというアルゴリズムを見つけた。 ボイドって？ ボイド(Boids)は、アメリカのアニメーション・プログラマ、クレイグ・レイノルズが考案・作製した人工生命シミュレーションプログラムである。名称は「鳥もどき(bird-oid)」から取られている。 wikipediaからの引用。コンピュータ上に鳥オブジェクトを作成し、それに対して以下の3つのルールを作用させるだけで、鳥の群れを
1987年に手動でディープラーニングをしていた驚異の麻雀ゲームがあった──アキバ通いのパソコン少年がゲーム アーツを創業──宮路洋一氏にゲームAIの核を聞く【聞き手：三宅陽一郎】
じつは1980年代の“国内ゲームAI史”は、これまでまったくの暗黒大陸と化していた。そんなところに発見されたその資料は、驚くべきことに──いまAI研究の最先端にいる開発者から見てもまったく色褪せない歴史的な完成度であるという。 この“早すぎる”麻雀の“ゲームAI”は、はたしてどう生み出されたのだろうか？ この奇跡ともいえる仕様書を作った人物は、ゲームソフト制作会社ゲームアーツを立ち上げ、その後『LUNAR』、『グランディア』シリーズや『機動戦士ガンダム ギレンの野望』のプロデュース、そして『大乱闘スマッシュブラザーズX』の開発プロデュースなども手がけた宮路洋一氏だ。 宮路洋一氏 当時、23歳の若者だった氏が作り上げた“麻雀AI”完成度の高さの舞台裏には──じつに1年半にわたる、途方もない回数のテストプレイの日々があったという。 「いつのまにかAIになっていた」、「いま思うと手動でディープラ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
量子コンピュータの基礎から応用まで/quantum summit 2019