DeepMind、AIで人間考案のものより優秀なソートアルゴリズムを発見 最大70％高速化
米Google傘下のAI企業Google DeepMindは6月7日（現地時間）、アルゴリズムを開発するAI「AlphaDev」が、人間が考えたものより高速なソートアルゴリズムを発見したと発表した。 ソートアルゴリズムは、入力されたデータを一定のルールに基づいて並べ替えるもの。ネット検索結果の並べ替えやランキング制作などIT技術の根幹を担う技術の一つ。今回AlphaDevが考案したアルゴリズムは既存のものに比べて、少量のデータなら最大70％、数十万規模の大量のデータなら約1.7％速く処理できた。 DeepMindはAlphaDevに新しいアルゴリズムを発見させるため、ソートの作業を「組み立てゲーム」としてプレイさせた。「正確にソートできる」「既存のアルゴリズムより高速である」という2点を満たせばクリアとした。 関連記事 OpenAIやDeepMindのCEOやトップ研究者ら、「AIによる人
楕円曲線暗号アルゴリズムを理解する｜TechRacho by BPS株式会社
お久しぶりです。yoshiです。みなさん、夏を満喫していますか？ 私は溶けそうです。日本の夏はとってもあつい。 覚えている方がいるかどうかは分かりませんが、以前私はRSA公開鍵暗号アルゴリズムを理解するという記事を書きました。今回はその続編（？）です。 楕円曲線について 楕円曲線、という言葉を事前知識無しで見ると、 多分こんな画像が脳裏に浮かぶと思います。違います。 楕円曲線の楕円は楕円積分から現れた言葉で、楕円積分は文字通り楕円の弧長などを求める方法なので全くの無関係とは言えませんが、少なくとも楕円曲線と楕円は別の図形です。楕円のことは忘れましょう。 実際の楕円曲線は、例を示すと以下のような曲線です。 一般化すると (ただし または ) という式で表されるこのような曲線をワイエルシュトラス型楕円曲線と呼びます。ワイエルシュトラス型、と付いているのは他のパターンもあるからで、 こんな形の楕
「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」がGoogleに怒られた話｜群青ちきん
「そらとぶあざらしさん」を遊んで頂くと、大体の温度感がご理解いただけるかと思います。 制限がされたページ今年の1月10日に、noteタイトルにもある「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」というページを公開しました。 内容はタイトルの通りです。 ランダムに生成された2枚の画像から「エッチ」な方を選んでいくと、アルゴリズム学習によってだんだんとエッチな画像になっていくというものです。 遺伝的アルゴリズムで最高にエッチな画像を作ろう！ (エッチな画像が見れるとは言っていない) より このページには、筆者のささやかな収入源として、GoogleAdSenseの広告を貼っていました。 GoogleAdSenseとは、大企業であるGoogleが運営している個人クリエイター向けの広告プログラムです。 AdSenseのポリシーとして、「性的に露骨なコンテンツ」(Sexually explici
類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
私たちはいかにして環状線で”悪さをする列車”を捕まえたか | プログラミング | POSTD
文：Daniel Sim 分析：Lee Shangqian、Daniel Sim、Clarence Ng ここ数ヶ月、シンガポールのMRT環状線では列車が何度も止まるものの、その原因が分からないため、通勤客の大きな混乱や心配の種となっていました。 私も多くの同僚と同じように環状線を使ってワンノースのオフィスに通っています。そのため、11月5日に列車が止まる原因を調査する依頼がチームに来た時は、ためらうことなく業務に携わることを志願しました。 鉄道運営会社SMRTと陸上交通庁（LTA）による事前調査から、いくつかの電車の信号を消失させる信号の干渉があり、それがインシデントを引き起こすことが既に分かっていました。信号が消失すると列車の安全機能である緊急ブレーキが作動するため、不規則に電車が止まる原因となります。 しかし8月に初めて発生した今回のインシデントは、不規則に起こっているように見えるた
おむつとビール（おむつとびーる）
「おむつを買った人はビールを買う傾向がある」という米国におけるマーケットバスケット分析（注1）の事例。1990年代半ばから2000年代初めにかけてメディアや講演などでよく語られ、データマイニング（注2）という言葉と概念を一躍有名にした。 一般に「米国の大手スーパーマーケット・チェーンで販売データを分析した結果、顧客はおむつとビールを一緒に買う傾向があることが分かった。調査の結果、子供のいる家庭では母親はかさばる紙おむつを買うように父親に頼み、店に来た父親はついでに缶ビールを購入していた。そこでこの2つを並べて陳列したところ、売り上げが上昇した」という内容で知られる。 直接的には、1992年12月23日の「ウォールストリートジャーナル」に掲載された「Supercomputer Manage Holiday Stock」という記事が発端だとされる。この記事では「米国中西部の都市でこの店は、ある
多腕バンディット問題とUCB解説
以下は登場する数式を(なるべく)直感的に(厳密性をけっこう犠牲にして)解釈したもの。数式多め。簡単のため台は２個とします（K=2）。 補足１ 収入をxとして、期待値がベストな台の収入の確率分布を、ベストでない適当な台iの収入の確率分布をとします。 このとき分布をもつベストな台があたかもベストでない台であるかのような振舞いを示す確率というのは漸近的に で与えられるという理論があります（大偏差原理。Dは相互情報量で、分布から見た分布の「遠さ」を表す）。 さて現状で平均収入がベストだったのが台0だったとして、そのプレイ回数を、(理論的な)期待値をとします。また、もう一方の台1のプレイ回数を、期待値をとします(基本的には平均収入が多い台をプレイしていくため)。ここで「台1が実はベスト」ということの「確率」はどれくらいか？ということを考えてみます。 台１に比べて台０は十分試行回数が大きいため、台０は
『【DiGRA公開講座】モンテカルロ木探索とは何か？』
将棋と比べて囲碁の評価関数を難しくしているのは、 ・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。 ・リバーシにおける角のように、明らかな特徴を持った場所が少ない。 ・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。 ・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。 などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。 ・石の厚い薄い 石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。 ・形の良し悪し 複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。 「代表的な悪い形」 ┼┼┼┼┼┼ ┼┼●┼┼┼ ┼┼●●┼┼ アキ三角 ┼┼┼┼┼┼ ┼┼●
DextroII先生のロマサガ閃きシステムのアルゴリズム講座
つしま（あなたの原稿はどこから） @chartreuse37 @DextroII 先生ッ！ サガシリーズの閃きシステムの概念ってどうなってるんですか！？ って弟が言ってました よかったらちらっと教えてください 2011-11-13 18:26:54
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路をZDDとして表したら、すっきりと経路情報が扱えました。 http://d.hatena.ne.jp/nowokay/20121018#1350528607 あとは、このZDDを効率よく構築できれば、おねえさんを救えそうです。このZDDの構築には、クヌース先生の開発したSimpathアルゴリズムを使うと非常に効率よく構築できます。 前回生成したZDDを見ると、同じノードにまとまっているものがいくつかあることがわかります。特に後半になるとどんどん同じパターンになるものがまとめられていきます。 つまり、この経路問題のZDDを構築するときには、いかに同じパターンになるものをまとめるかが鍵になるということです。 Simpathでは、辺の端だけに注目して、同じパターンになっていればそれ以降のノードを使いまわすという考え方で、ノードをまとめていきます。 つ
高層ビルのエレベーターホールには、なぜ階数表示がないのか - 本当は怖いHPC
以前に高橋幸雄先生の授業で聞いて非常に面白いと思ったこと。 オフィスビルとかホテルとか、エレベーターが何基も設置されているビルの場合、エレベーターホールに階数表示が無いことが多い。エレベーターホールで画像検索してみればわかると思う。 これはなぜだろうか。 その理由は、「客がいても、その階を通過することができるようにするため」だ。 基本的に、多数のエレベーターを効率よく動かすのは難しい。工夫された高度なアルゴリズムが使われていることが多い。目標は「客の平均待ち時間を短くする」ことだ。ある階でボタンが押された場合、どのエレベーターがその客を迎えに行くか、という判断が平均待ち時間に大きな影響を与える。難しいアルゴリズムの中で、この点がもっとも重要なところだ。 高層ビルの場合、エレベーターはかなりの速度で走っている。既に客を乗せて走っているエレベーターが他の客を乗せるために停止すると、減速→停止→
Timsort - Wikipedia
Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Quick, Draw!
Man Combines Random People’s Photos Using Neural Networks And The Results Are Amazing
Block Nested Loop Join／Batched Key Access Join
適時開示情報の文字に反応するアルゴリズムがラクオリア創薬のIRで作動か : 市況かぶ全力２階建
コンピュータ囲碁におけるモンテカルロ法 ~理論編~ 美添一樹
プログラミング体験ゲーム：アルゴロジック ｜ JEITA