アルゴリズム

ソフトウェアを記述する上で、いろいろなアルゴリズムを知っておくと自身の実現できるプログラムに自由度が広がります。早くするアルゴリズム、学習するアルゴリズム、近似するアルゴリズム等様々な目的を達成するためのアルゴリズムがあり、それらの得手不得手を知って使いこなすことが必要になります。

2017.9.3

553

Views
2

Watch
173

Knows

パソコンに多種多様な仕事を行ってもらうために人間が全てを用意するのは大変で、教えることが難しいことも多いのが実情です。機械学習によってある程度指針を人間で示しながら自動でパソコンに賢くなってもらい、ときには人間を凌駕するような性能を発揮してもらいます。

データの中から目的のデータを見つけ出すことを探索といいます.ここではそのような探索をデータに応じて効率的に行う探索アルゴリズムについてまとめています. 幅優先探索アルゴリズムや深さ優先探索アルゴリズム、線形探索などを含みます.

データをある基準で大小を決めてその大きさの順番になるように並べることをソートという。データの並び方や並び替え後のデータの状態等でソートのアルゴリズムを分類することができる。各ソートに得手、不得手があるため最も良いソートを選ぶことは難しい

特定の値を算出したり、特定の式の解を特定のアルゴリズムによって近似して求めたりする技術等についてまとめています.

主にソフトウェアで実現される圧縮アルゴリズムについてまとめているページです.与えられるデータによって何を生のデータから欠落させてもデータ全体として意味を持たせられるかが異なるため、画像用の圧縮は画像に特化した、動画用の圧縮には動画用に特化した圧縮アルゴリズムがあります.

画像を入力に特定の効果を得るための処理についてまとめます。近年はDeepLearningによる画像処理などがよく目立ちますが、簡単な処理、高速な処理は既存の技術を使います。画像を加工するだけだったり、画像内にあるものを数えたり、画像内にあるものを検出、画像から文字を読み出すものなどを含みます。

データ処理

特定の目的でデータを変換や処理を行うアルゴリズムや手法についてまとめているページです.

データ構造

ここではアルゴリズムにおいても重要視されるデータ構造に関するものについてまとめます.どのような値を保持するかはアルゴリズムの考え方と密接に関係します.

アルゴリズムのうち、信号関連を主に扱っているアルゴリズムに関してここのページにてまとめます.

深度センサによって取得されたような3次元点群に対して特定の目的のために点群を処理する方法についてまとめているページです.点群から抽象度の高い情報を取り出す方法や点群から点を探索する方法など様々な手法についてまとめています.

アルゴリズムの新規投稿

隠れマルコフモデル

隠れマルコフモデル(HMM, Hidden Markov Model)は、内部の観測できない状態を外部で観測できる状態から推定する技術. 内部の状態は確率でどれかの状態に遷移し、遷移した先で決まった確率で観測される状態を出力する.ビタビアルゴリズムで内部の最も考えられる状態遷移を予測し、Forward-Barckwardアルゴリズムで各時刻、各状態の確率を算出し、BaumWelchアルゴリズムでそもそもモデルのパラメータを推定する.

高速フーリエ変換FFT

高速フーリエ変換(FFT, Fast Fourier Transform)は与えられた時系列データから離散フーリエ変換を高速に処理する方法です. N個の離散的な時系列データからN個の離散的な周波数データへ変換します.

Stable Diffusion

Stable DiffusionはDiffusion Modelをベースとして潜在変数を主に処理しながらユーザのテキスト入力に沿った新しい画像を生成する技術. Stable Diffusionの仕組みを簡単に紹介する.

DBSCAN(Density-based spatial clustering of applications with noise)は主に密度の高い箇所と低い箇所の違いでどんなクラス数でどんな形状でもクラスタリング可能な手法. k-meansと違い予めクラスタ数は不要で線形分離できないクラスタリングも可能.

単純ベイズ分類器

単純ベイズ分類器(ナイーブベイズ)は、特徴間は全て独立という強引な前提を置き、ベイズの定理を使用することで、特徴量を入力にクラスを分類する分類器.単純で実装も容易ではあるが、一部のアプリケーションで十分に働く.メールのスパム分類で使用されたことで有名.

パーティクルフィルタ

パーティクルフィルタ(粒子フィルタ、モンテカルロフィルタ)は、複数の粒子にノイズをくわえながら観測データとモデルを元に内部状態を推定しく手法.非線形なモデルに対しても適用でき、粒子の数だけ精度はよくなるが、計算量もその分増える.実装が簡単で様々な分野で適用することができるのが特徴.

Bairstow法による求根

Bairstow法は、1次元多項式に対して効率的に全ての解を求める求根アルゴリズム.二次式の解を求めて関数を割るのを低次の式になるまで繰り返す手法.数値的な性質はよくなく桁落ちしやすいとされる.

Broyden法による求根

Broyden法(ブライデン法)は複数の方程式から得られる多次元の解を求める数値計算手法で、セカント法を一般化した手法.セカントが傾きで微分を近似したように、計算が複雑なヤコビ行列を一つ前のヤコビ行列の更新で実現.

セカント法による求根

セカント法(割線法)は、関数が0になる変数の値を求めることができる球根アルゴリズムで、ニュートン法では微分できることが必要でしたが、その必要はなく一つ前の解との差分から傾きを計算する手法です.ここでは一次元のみ紹介します.セカント法はニュートン法と異なり二次収束しないため、ニュートン法ほどの収束の速さは保証されませんが関数によっては早くなります.

ニュートン法による求根

求根アルゴリズムとして有名である頻繁に使用されるニュートン法(1次元の場合)について紹介します.ニュートン法によって関数の値がゼロになる値等を算出します.探索する初期値に依存し、解は一つしか見つけられませんが、比較的高速です.導関数が適切に得られる必要があります.

Burrows–Wheeler変換

Burrows–Wheeler変換(ブロックソート圧縮)は、情報を一切失うことなく文字列の順番を変えることで後工程で圧縮を行いやすくするデータ圧縮の前処理.繰り返し表現が増えたりするため、MTF変換や連長圧縮などと組み合わせてさらに圧縮しやすくします.もちろん可逆圧縮の処理になります.

算術符号は、与えられたデータを0~1の有理数に割り当てることで符号化する.頻度に応じて有理数のとれる幅を変更することで、頻出するものほど短い表現を、滅多に現れないものほど長い表現になるようにできている.テキスト圧縮や画像圧縮において用いられている.

PR曲線(Precision-Recall Curve)は、2クラスの分類の評価指標を与える曲線で、精度(Precision)と再現率(Recall)を軸にプロットしたグラフ.理想的な状態は右上に曲線が張り付く状態.大方ROC曲線と同じだが、ROC曲線より注目データに偏りがあって少ないデータしかないクラスがあるときに有用.

ハフマン符号

ハフマン符号は、よく頻出するものの符号長を短くしてあまり現れないものに対する符号長を長くすることでデータ全体を小さくすることができる符号化.

可逆圧縮と非可逆圧縮

可逆圧縮と非可逆圧縮について解説しているページになります.難しいことはなく、可逆圧縮は圧縮したものを再度元に戻す時に完全に復元できる圧縮、非可逆圧縮は一度圧縮すると元に完全には戻せない圧縮のことをさします.

交差検証法

データが少ない時には学習器の推定精度を適切に評価しにくいため、工夫が必要となります.交差検証法(Cross Validation法)は、一部を訓練データとして他をテストデータとした評価を何度か行い、どのデータもテストデータとも訓練データとも使用して評価をすることで予測誤差、推定精度をより正確にする手法です.

ROC曲線(受信者操作特性, Receiver Operating Characteristic)は、2クラスの分類の評価指標を与える曲線.もともとは信号処理の分野において用いられていたものだが、他分野でも使用されている.ある閾値を変えていく過程で再現率を縦軸、偽陽性率を横軸にプロットしたグラフ.曲線の下側の面積をAUC(Area Under Curve)と呼び、1に近いほどよく、曲線は左上に張り付いている方がよい.

Convolutionの誤差逆伝播

畳み込み層(Convolution層)の誤差逆伝播の計算についてのみまとめているページです.Convolutionの誤差逆伝播では、後続層からの入力と180度回転したConvolution層のパラメータ、順伝播の入力値を使って計算します.

One Hot ベクトル

One Hot ベクトル(One Hot Vector , One-of-K表記法)は、ベクトルの全要素のうち一つだけ1で他は0になっているベクトルをさす.

ICP(Iterative closest point)とは、2つの点群同士の位置合わせを繰り返し計算によって実現する手法.位置合わせを行う二つの点群は初期位置が大方あっている必要があります.大きな処理の流れは対応する点同士を見つけその誤差を最小にするように繰り返し変換を行います.

動的計画法はメモ化をするプログラム全てを指すということでいいのでしょうか

物体の一部にオクリュージョンがあるときにも画像から物体を検出させるには

焼きなまし法や山登り法で実際問題どれを使うのがよいのでしょうか?

PointCloudでテーブルの上にある物体を分離する方法

曖昧な単語による探索はどのようにして実現できますか？

どうやったら時間軸データを学習させることができますか?

Deconvolution はUnpoolingやUpsamplingとは違いますか？

ある物体をトラッキングしたいです。

最も早いソートは？

Deep Learningの最適化関数選定に関して

ベイジアンネットワークの使い方がわからない

Kaggleに参加するにはどういった分野の勉強が必要なのでしょうか?

"この商品を購入したひとはこれも"を実装したい

人工知能は現在どこまでできているのでしょうか?

人気のページのランキングを作りたいのですが、どのように作るべきですか?

ニューラルネットで二つの画像を入力にすることや途中でニューラルネットを混ぜることはできますか?

ニューラルネットで二つの画像を入力にすることや途中でニューラルネットを混ぜることはできますか?

簡単に画像を与えて分類することをやりたいです。

三次元点群から法線を出す方法について

画像のエッジを強調したい

文字認識、OCRするベストな方法は？

kdtreeとoctreeの違いを知りたい

データマイニングのためのプログラミング言語

機械学習のpythonライブラリお薦め

ニューラルネットワークの翻訳への適用のしかたが分からない

おすすめのDeepLearningのネットワークはどれですか？

アルゴリズム人気知識・質問

パーティクルフィルタ

パーティクルフィルタ(粒子フィルタ、モンテカルロフィルタ)は、複数の粒子にノイズをくわえながら観測データとモデルを元に内部状態を推定しく手法.非線形なモデルに対しても適用でき、粒子の数だけ精度はよくなるが、計算量もその分増える.実装が簡単で様々な分野で適用することができるのが特徴.

CTC損失関数

CTC Loss(損失関数) (Connectionist Temporal Classification)は、音声認識や時系列データにおいてよく用いられる損失関数で、最終層で出力される値から正解のデータ列になりうる確率を元に計算する損失関数.LSTMやRNNなどの出力を受けて正解文字列の確率を計算する.HMMのように前向き後ろ向きアルゴリズム、動的計画法を元に計算、微分可能であり誤差逆伝播が可能.

勾配に注目したオプティカルフロー

勾配に注目したオプティカルフローでは、複数あるオプティカルフローの算出方法のうち、画像の時間的空間的勾配に注目した算出方法.

Lucas Kanade法

Lucas Kanade法は、金田らによって提案されたオプティカルフローの実現手段として代表的な手法の一つ.

オプティカルフローとは

オプティカルフロー(Optical Flow)とは、二枚以上の画像を用いてその画像内で共通して写っている部分などをヒントに写っている部分の動作の推定や全体の動きを推定してベクトルにしたものです.二次元ベクトルに限らず三次元ベクトルの推定も行われます.

Attention機構

Attention機構(注意機構)とは、主に機械翻訳や画像処理等を目的としたEncoder-Decoderモデルに導入される要素ごとの関係性、注意箇所を学習する機構.機械翻訳において翻訳対象の単語間の関係性や全体のコンテキストを考慮させるために考案されたものだが、画像処理などにおいても応用されている.

ICP(Iterative closest point)とは、2つの点群同士の位置合わせを繰り返し計算によって実現する手法.位置合わせを行う二つの点群は初期位置が大方あっている必要があります.大きな処理の流れは対応する点同士を見つけその誤差を最小にするように繰り返し変換を行います.

反復深化探索

反復深化探索(反復深化深さ優先探索, ID, Iterative deepening depth-first search)は深さを制限した深さ優先探索を最大深さ0から次第に大きくしながら目的のデータが見つかるまで繰り返す探索.深さ優先のメモリの効率性と幅優先探索の完全性、最適性を備え持っているため、深さ優先探索や幅優先探索よりも理論上優れていることが多い.

セカント法による求根

セカント法(割線法)は、関数が0になる変数の値を求めることができる球根アルゴリズムで、ニュートン法では微分できることが必要でしたが、その必要はなく一つ前の解との差分から傾きを計算する手法です.ここでは一次元のみ紹介します.セカント法はニュートン法と異なり二次収束しないため、ニュートン法ほどの収束の速さは保証されませんが関数によっては早くなります.

ドロネーの三角形分割

ドロネーの三角形分割は、いかなる三角形の外接円も他の点を内包しない性質を持つ分割の仕方である.どの隣接する三角形を統合してもその外周は凸包となる.また、三角形の3つの角度の最小値が最大になるような分割を行う.

PR曲線(Precision-Recall Curve)は、2クラスの分類の評価指標を与える曲線で、精度(Precision)と再現率(Recall)を軸にプロットしたグラフ.理想的な状態は右上に曲線が張り付く状態.大方ROC曲線と同じだが、ROC曲線より注目データに偏りがあって少ないデータしかないクラスがあるときに有用.

大津の方法による二値化フィルタ

大津の方法による二値化フィルタは、画像内に明るい画像部位と暗い部位の二つのクラスがあると想定して最もクラスの分離度が高くなるように閾値を自動決定する二値化フィルタ.人間が事前に決める値はない.

Global Average Pooling層

Global Average Pooling層によって最後の層において直接平均してクラスを作り出す。

Relu活性化関数

最も現在使われることの多い活性化関数。 xが負のとき0それ以外は恒等関数. シグモイドなどより計算が早いことが特徴.

ニュートン法による求根

求根アルゴリズムとして有名である頻繁に使用されるニュートン法(1次元の場合)について紹介します.ニュートン法によって関数の値がゼロになる値等を算出します.探索する初期値に依存し、解は一つしか見つけられませんが、比較的高速です.導関数が適切に得られる必要があります.

Pタイル法による二値化フィルタ

Pタイル法による二値化フィルタは、閾値を前景と背景の比率に基づいて決めるフィルタです.明るさの変化を受けにくいですが、どのような比率にするかを人手で決める必要はまだあります.

適応的二値化フィルタ

通常の二値化フィルタでは画像全体で共通の閾値を使っているが、適当的二値化フィルタ(Adaptive Thresholding)では局所的に閾値を決定して処理を行なう二値化フィルタ.背景と前景が判断できるようにある程度考慮するサイズは大きい必要がある.

シャムネットワーク

シャムネットワークは(Siamese Network)二つの画像の似ている似ていないという指標となる距離を学習するCNNを利用したニューラルネットワーク.二つのCNNは重みが共有されていてそれらの出力を距離を計算するネットワークに入力する.

LeakyRelu活性化関数

Reluでxが負の場合を改良したLeakyRelu活性化関数.

ROC曲線(受信者操作特性, Receiver Operating Characteristic)は、2クラスの分類の評価指標を与える曲線.もともとは信号処理の分野において用いられていたものだが、他分野でも使用されている.ある閾値を変えていく過程で再現率を縦軸、偽陽性率を横軸にプロットしたグラフ.曲線の下側の面積をAUC(Area Under Curve)と呼び、1に近いほどよく、曲線は左上に張り付いている方がよい.

動的計画法はメモ化をするプログラム全てを指すということでいいのでしょうか

どうやったら時間軸データを学習させることができますか?

物体の一部にオクリュージョンがあるときにも画像から物体を検出させるには

焼きなまし法や山登り法で実際問題どれを使うのがよいのでしょうか?

PointCloudでテーブルの上にある物体を分離する方法

Deconvolution はUnpoolingやUpsamplingとは違いますか？

曖昧な単語による探索はどのようにして実現できますか？

ニューラルネットで二つの画像を入力にすることや途中でニューラルネットを混ぜることはできますか?

人工知能は現在どこまでできているのでしょうか?

最も早いソートは？

ニューラルネットワークの翻訳への適用のしかたが分からない

画像のエッジを強調したい

ある物体をトラッキングしたいです。

機械学習のpythonライブラリお薦め

人気のページのランキングを作りたいのですが、どのように作るべきですか?

"この商品を購入したひとはこれも"を実装したい

ベイジアンネットワークの使い方がわからない

Deep Learningの最適化関数選定に関して

おすすめのDeepLearningのネットワークはどれですか？

kdtreeとoctreeの違いを知りたい

ニューラルネットで二つの画像を入力にすることや途中でニューラルネットを混ぜることはできますか?

文字認識、OCRするベストな方法は？

簡単に画像を与えて分類することをやりたいです。

データマイニングのためのプログラミング言語

Kaggleに参加するにはどういった分野の勉強が必要なのでしょうか?

三次元点群から法線を出す方法について