機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
平方根のアルゴリズム
平方根である。sqrtである。私の数学知識は非常に乏しく、かろうじて平方根の何たるかを解するばかりであるが、ふと、平方根を計算するアルゴリズムが知りたくなった。理由は、constexprなsqrtを実装してみたくなったからだ。 日本語では、いい情報がWeb上に存在しないので、ここに書いておく次第。この説明は、私のように数学の知識を持たない人間にも理解できるはずである。 ここで使うのは、バビロニア人の方法（Babylonian method）と呼ばれている、歴史あるアルゴリズムである。この方法は、手動でも、プログラミングでも、非常に簡単に計算できる、大変便利で汎用的なアルゴリズムである。しかも、速度もそれほど遅くない。 √Sに対して、 任意の正の整数を初期値X0と定める（できるだけ平方根に近い値が望ましい） Xn+1を、Xnと S / Xnの平均値とする（平均値は相加平均で求める） 必要な精
Amit’s Game Programming Information
FAQHow do I get started?[1] (for everyone)10 Mostly Easy Steps To Become An Indie Dev[2]How do I make games?[3] (for programmers)How can I write my own (more complex) game?[4]How much fun is game programming?[5]What do I need to learn once I know how to program?[6]What do I do after school?[7]What are the key concepts to start with?[8]How do I actually finish a game?[9]Do I want to do this for a l
画像処理におけるアルゴリズム
ここでは各画像処理におけるアルゴリズムを簡単に解説する。 2値化 明るさ調整 色成分の抽出 色反転 コントラスト調整 切り出し ガンマ補正 グレイスケール化 増色 画像枠付加 鏡像反転 ノイズ除去 輪郭抽出 輪郭追跡 拡大縮小 任意角回転 セピア調化 ぼかし 2値化 指定画像を白と黒の2階調の画像に変換する処理であり、本研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。 次にそれぞれのアルゴリズムについて解説する。 単一手動閾値方式 指定された色深度を基準として、その値より入力画素の色深度値が明るければ白、暗ければ黒色として2値化する。下の式を用いている。 このとき、出力画像は初期状態で黒色となるので、入力画像の画素値が閾値以
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
広く知られているinsertion sortのコードは駄目すぎる - やねうらお−よっちゃんイカを食べながら年収1億円稼げる(かも知れない)仕事術
insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 ) ■ 日本語版 Wikipediaの日本語のページのコードを引用すると次のようになっている。 for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味に
超連射68K 開発日記 -弾幕世代以前の90年代 STG のこと-
FINAL FANTASY XVにおけるPhoton利用事例 - Photon運営事務局 GTMF 2018 OSAKA / TOKYOGame Tools & Middleware Forum
広く知られているinsertion sortのコードは駄目すぎる？ by Inquisitor
やねうらおさんによると、「広く知られているinsertion sortのコードは駄目すぎる」らしい。Wikipediaに載っているコード(2009.08.06版)を、 どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。 というのだから穏やかではない。 私の座右の書『コルメン』も、 一連の劣悪なコードはこいつが犯人かも知れない。 と非難されてしまっている。 実際のところ、どのくらいの性能差になるのか、実験してみた。 こんな感じ(codepad)。 C++の標準ライブラリ(std)のsortとWikipedia版、やねうらお版の比較。単位は秒。挿入ソートの2つ（つまりWikipedia版とやねうらお版）は、実行時間の比も計算した（1より小さい値はやねうらお版が速いことを意味する）。 size repetition std wik
Perlin Noise
Many people have used random number generators in their programs to create unpredictability, make the motion and behavior of objects appear more natural, or generate textures. Random number generators certainly have their uses, but at times their output can be too harsh to appear natural. This article will present a function which has a very wide range of uses, more than I can think of, but bas
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
コンピューターに絵画を描かせる | fladdict
コンピューターによる写真の絵画変換ってのは、photoshopにもついてるんだけど、あれってダサい。 なんかヌタッとしてて、全体がのっぺりしている・・・というか、主題と背景とかそういうのが考慮されずに一律に変換されているのがキモイ。 で、最近ごぞんじのように、写真のフラクタル分割をずっと趣味で研究してたんだけど、ようやく自分が納得できる精度でフラクタル分割する方法を思いついた。↓の画像がその処理結果なんだけど、だいぶいい感じに分割できてると思う。 アルゴリズムはQuasimondoのFITCの発表を聞いてる最中に思いついたもの。 まず画面のピクセルを走査し輝度の標準偏差を取る。標準偏差が閾値以上の場合、その領域は十分に複雑であると判断され、分割される。あとはそれを繰り返して二分木あるいは四分木で分割していけばいい。輝度を基準にするってのはJPEGの圧縮からアイデアを頂きました。 ちなみにQ
Amazon Elastic MapReduceを使ってみた - moratorium
Amazon Elastic MapReduceを使ってみた 2009-04-03 (Fri) 3:06 Amazon EC2 連日のEC2ネタです。本日、AmazonからElastic MapReduceというサービスがリリースされました。大規模データ処理技術が一気に民間の手に下りてくる、まさに革命的なサービスだと思います。 Amazon Elastic MapReduce Amazon ElasticMapReduce 紹介ビデオ With Hadoop, Amazon Adds A Web-Scale Data Processing Engine To Its Cloud Computer by techcrunch.com Elastic MapReduceは、Googleの基盤技術の一つであるMapReduceを時間単位課金で実行できるサービスです。MapReduceについては以
最強最速アルゴリズマー養成講座：あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 はじめに はじめまして。高橋直大です。本連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。 なお、本稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問
微分方程式を解こう！ | _level0 - KAYAC Front Engineer Blog
どうも。こんにちは。梅雨明けも宣言されたそうで、いよいよ暑くなりますね。今回は単振動方程式方程式を用いた最適化のお話です。 高校物理でも登場するバネの方程式、単振動方程式 を簡単な四則計算に分解する方法を紹介します。 まず色々な数学的背景を押しやって、イメージだけ説明すると、物体の位置x、速度v、加速度aの関係は となるので、asの式で考えると、 v += a; x += v; という風になります。ここで単振動の微分方程式から、 a = -K * x; であるから、あわせると、 v -= K * x; x += v; という風になります。下がサンプルで、初期値(_v, _y)やKなんかを変えて挙動が変わることが分かります。 ここでのポイントはvに対して最初の式で破壊的な操作を行っていることです。 v_temp = v; v -= K * x; x += v_temp; 等とすると、ずれてし
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
Standard Template Library プログラミング on the Web
1985年、AT&TのBjarne StroustrupがC++をこの世に送り出しました。その後C++は様々な拡張を繰り返しながら進化してきました。 1991年、ISOはC++の国際標準(standard C++)を定める作業を開始しました。標準C++の最終草案は1997年にISO C++標準化委員会に承認されました。 標準C++が規定するのは言語仕様だけなく、C++標準ライブラリも規格の中で明確に定められています。それまでC++のライブラリといえばiostreamぐらいのものでしたし、それもあくまで"事実上の標準"でしかありませんでした。 そしてそのC++標準ライブラリの一部として組み入れられたのがSTL(Standard Template Library)です。すなわちSTLは標準C++の仕様の一部ということです。 僕がSTLを知ったのは1995年、いくつかのコンパイラがtemplat
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Electronic Textbook on Computer Graphics
ほぼ日刊イトイ新聞 -マッチ箱の脳（WEB）篇