制約なし最適化問題に対する準ニュートン法 （非線形計画法） 製作者：向 譲治 制約なし最適化問題は次のように表す。 この問題の解法としてニュートン法、準ニュートン法などがある。 ニュートン法 ニュートン法は反復法の一種である。反復法とは、適当な初期点 から出発して、 によって次の点列を生成し、最終的に最適解に収束するものである。ここでを探索方向という。 ニュートン法では、各反復において、関数 f を でテイラー展開して得られる２次関数
準ニュートン法アプレット（非線形計画法）
制約なし最適化問題に対する準ニュートン法 （非線形計画法） 製作者：向 譲治 制約なし最適化問題は次のように表す。 この問題の解法としてニュートン法、準ニュートン法などがある。 ニュートン法 ニュートン法は反復法の一種である。反復法とは、適当な初期点 から出発して、 によって次の点列を生成し、最終的に最適解に収束するものである。ここでを探索方向という。 ニュートン法では、各反復において、関数 f を でテイラー展開して得られる２次関数
きまぐれ日記: キーワード抽出: tf-idf の意味づけ
単語の重み付けの古典的な方法に tf-idf があります。文書中の各単語の tf-idf 値計算し、値でソートすると、その文書に特徴的な単語リストを得ることができます。 http://nais.to/~yto/clog/2005-10-12-1.html tf-idf は、単なるヒューリスティックスだと考えられていましたが、最近言語モデルに基づく情報検索手法がさかんに研究されるようになり、tf*idf の解釈が明らかになってきました。言語モデルに基づく手法は、ヒューリスティックスばりばりの手法と同性能にもかかわらず、文書のランキングに理論的で合理的な説明を与えることができます。 情報検索は、クエリ q に対し、もっとも適合する文書 d_opt を求めるタスクです。つまり、q が与えられたとき、文書 d が出現する確率 p(d|q) の最大化問題と解釈できます。 d_opt = argmax
mean-shiftを実装してみた - tsubosakaの日記
次回のCVIM勉強会でmean-shiftについて話すことになってしまったので、理解のためにmean-shiftアルゴリズムを実装してみた。 カーネルは一番簡単なフラットカーネルを利用し、また画像もグレイスケール画像のみを扱うためピクセルの値は[0,256]の一次元データとみなす。 またナイーブな実装だと512*512ぐらいの画像でもすごい時間がかかるので二分探索とFenwickTree(動的に更新する必要はないので別に使う必要なかった、累積和を保存した配列に変更)を使ってグレイスケール画像かつフラットカーネルであることを利用して高速化した関数meanShiftLoopFastを用意した。 元画像は下のようになっている。 bandWidth=10のときは下のようになり、肌の部分が同じ値に収束していることがわかる。 bandWidth=20のときは以下のようになり、やや平滑化されすぎているこ
特徴点検出器を作ってライブラリに追加した - デー
前々からアニメ顔類似検索のbag of featuresで使っている特徴点の決め方がイラストにあまり合っていない気がしていたけど、実装がすごく面倒くさそうだったのでやらなかった。しかし、最近SURFに特許があることが発覚して、SURFを使っている意味は特にないなーと思ったので、満足のいくものをつくろう思ったのであった。（ただ特許は気にせずにやる） ということで、こんなのができた(クリックで拡大)。 結構速いし、スケールの変化、回転、ある程度のゆがみには大体対応できている。対応点の決定は、点の特徴ベクトルが一番近い点と二番目に近い点を取って、ふたつの特徴ベクトルの距離の差を確信度として、確信度が高いもののみマッチングしたことにして表示している。 SIFTやSURFに比べると点多すぎだろ（なぜ渦巻きに…）と思うかもしれないけど、これは僕なりにイラストの特性とかbag of featuresで使
lsh p-stable
1. The document is a complex arrangement of symbols and text in an unknown language or script. 2. There are repeating symbols that appear throughout, most notably "ÔÃ�à ̃". 3. While the overall meaning cannot be understood, it discusses various topics denoted by different symbols and arrangements of text.
画像処理 (3) 顕著性マップ
人は、目から得られるたくさんの情報を常に処理し、それに対して判断を行っています。目に映るモノ全てに対してそれが何かを一々判断していたのでは、特に瞬時の判断が必要な場合は生死に関わることになる可能性もあります。車の運転中、前の車が急停車したという情報を処理するときは、目の前に近づいてきた車やそのブレーキランプを見て判断すれば充分なのに、周囲の景色や道路標識なども常に処理されていては判断が間に合わなくなります。そのため、本当に注目すべきモノだけに無意識に注意を引くような仕組みが人には備わっています。これは、人に限らず他の動物にもあり、天敵などの危険から逃げたり、逆に獲物を追う時に逃げる対象の動きを瞬時にとらえるなど、常に視覚情報から注意を引く部分を抽出して、それ以外の情報はカットしてしまう機能が必要になる機会は人よりも多いことが想像できます。 今回は、注意を引く対象を見つけるための仕組みとして
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
Image Processing Basics
基本的な画像処理手法について 画像のディジタル化(カラー・モノクロ) このページで使用するサンプル画像について 輝度値ヒストグラム カラー画像の画像処理 色の変換(RGB->YUVへの変換) 色の変換(鮮やかさを上げる・下げる) 明るさの調整（γ補正） グレイスケール(モノクロ)画像の画像処理(階調に関する) 明るさの調整（γ補正） 階調値の部分拡大強調 階調イコライゼーション(ヒストグラム均一化) 2値化 グレイスケール(モノクロ)画像の画像処理(フィルタ処理) シャープ化とぼかし ノイズ除去(メディアンフィルタ) 1次微分(差分)によるエッジ検出 2次微分(差分)によるエッジ検出 実際に体験してみる(学内限定) グレイスケール画像の画像処理 カラー画像の画像処理 画像圧縮 一般データの圧縮 画像の圧縮（その１：ランレングス,GIF） 画像の圧縮（その２：JPEG） 参考文献 谷口慶治編
ALGORITHM NOTE 動的計画法
n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。 これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。
フィルタ処理 画像処理ソリューション
これまで紹介してきた内容の総集編的なサンプルプログラムを作成してみました。 これから画像処理を学ぶ人にも使ってもらえると幸いです。 でも、これ以上の内容は本職の仕事にも差し支えそうなので、これがギリかも。 （ちなみに本職では画像処理ツールや画像処理アルゴリズムの開発やってます。） 基本的な機能としては ●拡大縮小表示（10,25,50,75,100,150,200,500,750,1000,5000,10000%） ●内挿補間表示（NearestNeighbor, Bilinear, Bicubic, HighQualityBilinear, HighQualityBicubic） ●カラーモノクロ変換(ＲＧＢ平均、YUVのＹ) ●二値化処理（しきい値設定可） ●ファイルフォーマット変換(bmp,jpg,png,tifファイルの読み込み、保存) 画像処理ではモノクロ８Ｂｉｔでの画像処理が多
スペル訂正エンジンを作ってみた - nokunoの日記
紫蘇カンファレンス2010というイベントでLTをしました。紫蘇カンファレンス 2010 - しソ部Togetter - 「紫蘇カンファレンス 2010」内容は、StaKKのスペル訂正機能についての解説です。統計的自然言語処理エンジンStaKK - nokunoの日記shisoconf 2010 Spelling CorrectionView more presentations from nokuno. 他の人は画像会話用の画像検索エンジン「tiqav（ちくわぶ）」や、Flickrのお気に入りをふぁぼったー的に表示してくれる「flistr」など、幅広いサービスや技術やネタが満載の楽しいイベントでした。tiqav / ちくわぶFlistr - View Flickr Photos Favorited by Your ContactsWWSみんなが頑張っているのを見ると刺激になりますし、今の環
EMアルゴリズムによるスペル訂正エンジン - nokunoの日記
以下の論文が面白かったので紹介したいと思います。Learning a Spelling Error Model from Search Query Logs Noisy Channel Modelによるスペル訂正エンジンスペル訂正には標準的なNoisy Channel Modelを使うことができます（最近は識別モデルも流行りのようです）。A Spelling Correction Program Based on a Noisy Channel ModelNoisy Channel Modelでは、入力が与えられたときの訂正候補の確率を以下のようにモデル化します。言語モデル はコーパスやクエリログから単語N-gram、文字N-gramなどを推定し、スムージングして利用することが一般的です。エラーモデル は入力と出力候補の編集距離をもとに計算することが多いです（他に共起頻度やクリックログを利
Scalaで集合知プログラミング まとめ - Reinvention of the Wheel
Scalaで集合知プログラミングのまとめです PythonとScalaのお勉強を兼ねつつもゆる〜い感じで進めていきますデス 目次 1章 集合知への招待 Scalaで集合知プログラミング その1 2章 推薦を行う 嗜好データの定義 Scalaで集合知プログラミング その2 ユークリッド距離を使った類似度 Scalaで集合知プログラミング その3 ピアソン相関係数を使った類似度と類似度ランキング Scalaで集合知プログラミング その4 アイテムを推薦する Scalaで集合知プログラミング その5 アイテム間の類似を計算する - 嗜好値データの変換 - Scalaで集合知プログラミング その6 deli.cio.us APIの利用準備 Scalaで集合知プログラミング その7 deli.cio.us APIを利用した推薦 Scalaで集合知プログラミング その8 アイテムベースのフィルタリング
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
微分積分
Numerial Computation
はてなブログ | 無料ブログを作成しよう
はてなブログ | 無料ブログを作成しよう
画像処理アルゴリズムSIFTの勉強始めました | Love澤's Room
LSH その1 -LSHの種類-｜JAVAでデータマイング！
アルゴリズムイントロダクション15章 動的計画法
