Kuromojiは何で研究にあまり使われないのか？

今回は（現在の所は）日本語形態素解析器であるKuromojiについて気になったことに関しまして少し独り言みたいに考察します。Kuromojiは中の人を知っているので少し贔屓目に見ている部分もあると思いますが、一応ステマではないつもりです。

今回ふと思った疑問：何故Kuromojiが研究で使用されている場面が少ないのでしょうか？

Kuromojiは僕が前にお世話になっておりましたアティリカ社の開発したプロダクトの内の一つです。SolrやElastic SearchといったJavaベースの検索システムの形態素解析器として広く使われております。

この形態素解析器はNLPでも多くの研究がなされ、研究コミュニティにおいてはJUMAN、Cabocha、MeCab、Kyteaといった形態素解析器が多く発表されています。これらとKuromojiとの違いは「Research-drivenかEngineer（Business?）-driven」かが大きく影響していると思います。

形態素解析器そのもの解説と歴史は

等の別の資料に譲ります。

このKuromoji、僕がざっと検索した限りではNLPのトップカンファレンスの一つであるEMNLP2013に出たGender Inference of Twitter Users in Non-English Contextsぐらいしか有名所会議の論文では使用されていませんでした。（僕のサーベイ不足でしたら申し訳ございません。あとはIJCNLP2013のワークショップに出た論文がありますが、、、）

MeCabのページに各種日本語形態素解析器の比較表ありますが、この表に沿いましてKuromojiを評価されている方がいらっしゃいましたのでリンクを貼らせて頂きます。
Kuromojiを調べてみた | @johtani の日記
ただ2011年と少し古い記事ですので更新されている部分もあるかと思います。

そこでもう少し検索し、LuceneにおけるKuromojiのIssueを見てみますと、「Kyotoコーパスを学習に使っているよー」といった趣旨のコメントがありました。ということはコスト推定においてきちんと機械学習でコストを学習しているように思えます。

ただGithubで公開されているレポジトリに学習方法のコードが付属していません（MeCab0.996ではLBFGS法のコードが付属しています）。おそらくデモで公開されているのは何らかの学習方法を用いて学習し公開されたものなのでしょうが少なくともわかりやすい形でオープンになっていないみたいです。

数時間ググってコード以外で中身の情報が出てきたのはこんな感じでした。あとはコードが公開されているのですが、一人でハックするのには結構時間がかかると思います。。。ここから自分が感じた結果、「中身具体的にどうなっているかはコードをハックするか、開発者に聞かないとわからないじゃん！」ということです。

これはやはりリサーチコミュニティとしては「具体的な中身や背景までわかって、既存手法との比較がないと比較も考察もできない」ということに対し、オープンソースコミュニティでは「性能が良さそうで、SolrやElastic Searchとの親和性が高いからいいじゃん！わからなければ開発者に聞けばいいしね！」という意識の差もしくは作られた目的が違うが故の差なのでしょうか？もしくはビジネスの関係で評価データを公開しないことでしょうか？

僕自身、研究コミュニティにおいてもオープンソースコミュニティにおいても、大きな流れをつかめていないので結論ははっきりとだせないのですが、文化の違いなのかな、というのが漠然とした自分の中での今の結論です。どうなんでしょうか？

【論文紹介】A joint source-channel model for machine transliteration, ACL 2004

前にスペル修正、翻字（Transliteration)周りのサーベイを書いた時に、DOMという手法をあまり詳しく調べなかったので、今回調べた結果面白そうな手法でしたので少し紹介します。ちなみに紹介する論文は中国語と英語間の手法として提案しています。これはカタカナと違って中国語はphoneticではなくideographicだよ！と主張しているのでカタカナには適用できないかもしれませんが個人的に面白かったので紹介します。

Li et al. A joint source-channel model for machine transliteration, ACL 2004

まず僕が理解している限りの背景としてtransliterationに関する基本的な方針は（少なくとも2004年までは）以下の2つです：
１．編集距離の拡張であるBrillらの手法を利用
２．Direct Orthogonal Mappingを利用

１．と２．の手法の大きな違いは２．ではphonemeを経由せずに、直接文字列と文字列の対応を取ることをしています。
例えば１．の手法を使うとしたら、
グーグル -> guuguru -> google
と一回ローマ字読みを挟む必要があるのに対し、２．では
グーグル -> google
と直接割り出します。

実際論文中にもPhonemeに変換すると約8%精度が落ちるよ！DOMの方が性能がいいよ！というのが報告されています。DOMを実現する上では様々な手法が考えられるのですが、この論文では単純なngramモデルを提案しています。

モデル化する上で提案しているのはJoint Source Channel Modelであり、中国語と英語の文字列ペアを同時に生成する、すなわち結合確率（Joint Distribution）を算出するモデルです。これはとは別にNoisy channel modelというのがありますが、僕が理解している限りではを直接モデル化するか、ベイズ則を用いて としてモデル化するかの違いだと思っています。
ここで問題になるのが、「アライメントをどうするか？」です。例えばの英語、カタカナペアには
g ->グ, oo -> ー, g -> グ, le -> ル
go ->グ, o -> ー, gl -> グ, e -> ル
などと言った複数のアライメントが考えられます。別にどれが正解か、というよりはより確率が高い文字レベルのTransliterationペアはどれか？というのが求めたいことです。

論文の提案手法の手順：

１．学習データとして対訳辞書を用意。論文では中国語と英語の対訳人名辞書を使用。
２．min(中国語の漢字数, 英語表記の長さ)だけ、対に当たる英語をランダムに振り分ける（<-ここの部分は論文に明記されていなかったので自分が例から汲み取って想像した部分です。）
３．ngramモデルを計算する
４．３．で計算したngramを元に最もらしいngramペア列を計算
５．３．と４．がngramペア列の変化がなくなるまで繰り返す。

Table10で他の手法との比較結果が書いてあります。ピンインレベルではなく文字レベルでのマッピングではPhonemeを利用した手法より論文で提案しているngramを利用したDOMの方がエラーレートが低いことが伺えます。少し気になったのが、正解文字マッピングは一意に決まるものなのでしょうか？グーグル, googleペアの例でも正確なマッピングかどうかを考察するのは自明でないと思います。

2004年と9年前の手法だからかもしれませんが、非常にシンプルで難しい数式がゴリゴリ出てくる訳でもなく、非常にお気に入りの論文です。

Conditional Random Fields（CRF）入門その3 -CRFの新しい論文とViterbiアルゴリズムについて-

Conditional Random Fields（CRF）入門その2 -ブログ資料と勾配について-の続きです。少し手抜きになっていますがご了承ください。
感動の最終章です。間違っている場合は訂正して頂けますと助かります。

Viterbiアルゴリズムは動的計画法です。直前の状態からどの遷移の確率が一番高いかを計算します。それだけです。

例えば赤い線の遷移の対象としているノードへの一番高い確率を計算すると、直前の状態としてあり得るノードからの確率を計算します。以下の例だと0.5の遷移確率が一番高いので対象としているノードまでの経路の確率は0.5となります。

あとCRFについて重要な補足ですが、CRFは「最大エントロピー法（対数線形モデル）を系列ラベリングに適用したモデル」です。最大エントロピー法の利点の一つは「互いに依存している素性も素性として入れられる」ことにあります。Linear-Chain CRFの場合、素性関数の引数として直前の状態と現在の状態が入っているので系列となっていることがわかります。

注意点としましてはどこかで読んだ資料でViterbiアルゴリズムは局所最適解に陥りやすい、と読んだ覚えがあります。まあ前のノードしか見てないのでそうなりますね。。。
2014年3月30日訂正：
linear chain CRFの目的関数は凹関数なので、局所最適解は存在しません。ただ素性の設計次第で大域的最適解がViterbiアルゴリズムによる求まらない可能性はあります。

最後に最近僕が面白そうだなと思うCRFの一種を紹介します。
DCRFと呼ばれる複数の系列を同時に推定するCRFです。これはパイプラインを通さずに同時にできる、というParsingの分野でやられていたDual Decomposition？（自信ないです。。。）と似たような考え方、と僕は捉えております。

Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data
Mining Informal Language from Chinese Microtext:Joint Word Recognition and Segmentation

２番目の論文で提案されたFactorial CRFは１番目の論文にて提案されたDCRFの一種で中国語の崩れ検出と単語分割を同時にやっています。１番目の論文曰く、DCRFはLinear-chain CRFと比べて同じ性能を発揮するまでに必要な学習データが少ないみたいです。

あとSHDCRFというのもあるみたいですね。今知りました。

CRFは約10年前に提案された手法ですが未だに現役の手法＝ブレイクスルーがないと言えるんでしょうか？今後も系列ラベリングモデルの変遷には注目しいきます

スペル修正、翻字（Transliteration)周りのサーベイ

　最近自分の分野と比較的近い、スペル修正、翻字（Transliteration）の分野の論文を読んでいます。カタカナーローマ字間の翻字はストーリーがあると思いましたので、テキトー紹介したく思います。かなりざっくりしていますのでご了承ください。主に検索クエリ周りの論文を収集しています。検索クエリ＝企業の独壇場！なイメージですね。

０．Knight and Graehl, Machine Transliteration, Computational Linguistics 1998
全ての始まりです。カタカナのローマ字表記と英語表記は似てるよねー、編集距離とればいいんじゃない？という話。

１．Brill et al. An Improved Error Model for Noisy Channel Spelling Correction, ACL 2000
　この論文が編集距離における統計的手法の始まりです。編集距離の問題として、例えばスペル修正のタスクにそのまま適用しようとすると、閾値が全ての文字列間において一意に決めにくい問題があります（と今日考えました）。
　例えばis->amの編集距離は2ですが、vaccumとvacuummの編集距離も2になります。文字列長でNormalizeする方法も考えられますが、この論文では単純に「2文字以上の編集を許す」ことにし、「どの編集が適用される確率が高いか」を学習データから学習しています。上の例から行きますと、is->amはスペルミスではないと考えられるので学習データには含まれていないはずです。一方vacuumm->vaccumに訂正する学習データがあれば、「is->amにするよりuu->cuにする方が起こりやすい」とモデルが解る訳です。
　ちなみに補足としてこの論文で二文字以上の編集を許す場合は「編集が起きている場合」に限っています。vacuummとvaccumの例で行きますと、v/v, a/a, c/c, u/c, u/u, m/ε, m/m, にアラインされます（εは空列を意味します）。この場合「編集が起きている」＝「編集前後の文字が異なる（空列を含める）」とし、u/cとm/εの前後の編集をn文字許します。n=1の場合は、cu/cc, uu/cu, um/uε, mm/mεが編集として許されます。論文中ではεが暗黙の内にドロップされていた上、|α|やらnやらで編集を許すサイズが定義されていたので（ちなみに|α|=|β|とすると、|α|=n+1です。|α|≠|β|の場合のnの対応はまだ理解していません）、僕が論文を読んでいる時に理解するまでに時間がかかりました。（おまけに同じ著者の別の論文で例に間違いがあるので余計時間かかりました）

　全てはこの論文を根として、木を描いているイメージです。一言でいいますと「編集距離を利用して文字列間のアライメントを取り、最も確からしいアライメントを取ろう！」という話。

ここからストーリーは３つ（以上）に分かれます。

A. カタカナー英語間の翻字

  • Brill et al., Automatically harvesting katakana-english term pairs from search engine query logs, NLRS 2001

　１．の手法をカタカナと英語間の翻字を認識するタスクに使用してやったぜ！という話です。論文中にある例でntex->ntekが抜けているので注意してください。

  • Hagiwara and Suzuki, Japanese query alternation based on semantic similarity, ACL 2008

　Distributionalな素性は使えそうだけどSparseになりやすいからKernelを使って文字列間の近似を取ったよ！という話です。
　Distributionalな素性とは何か？ですが、検索エンジンにクエリを投げる時にスペースを空けて入れるもう一つのキーワードとそのパターンのPointwise Mutual Informationを取っています。例えば「JAL」が「日本航空」の書き換え候補となりうるか？という問いに答えるため、「JAL 航空券」というクエリと「日本航空 航空券」があったら文脈ベクトルとして{PMI(後ろに「航空券」が続く, 日本航空)}と、{PMI(後ろに「航空券」が続く, JAL)}の２つのCosine類似度を測ります。この手法は後述するLiらがadventuraがadventureのスペルミスでないことを示すために考えた手法からインスパイアされています。
　気になった部分としてテストデータ構築の際に短い時間でユーザがタイプしたクエリは書き換え候補になりやすい、という仮定の元でコロケーション検出で用いられるLog-likliehood testの閾値以上の値を抽出している部分です。これである程度は高いAccuracyを出すのでは？と疑問でしたが、約10000ペア中約6500ペアしか書き換え候補ペアを抽出できていないので提案手法のAccuracy約80％を考えるとベースライン程度の役割しかなっていなかったことが伺えました。
　この論文も１．の手法を素性の一つとして用いてますが、編集の確率を学習するデータとして英語と日本語の記事のタイトルペアを用いたみたいです。別の論文でもWikipediaを使って編集の確率を計算する手段を見ましたが、アカデミアでもよくある手法みたいですね。
　Kernel部分は詳しく理解していません。キーワードのパターンを繋げる、程度しか理解していません。

  • Cherry and Suzuki, Discriminative substring decoding for transliteration, EMNLP2009

　機械翻訳の際に翻字が認識できると便利だよねー、という話。理解していません。

  • Yang et al. Jointly optimizing a two-step conditional random field model for machine transliteration and its fast decoding algorithm, ACL 2010, short paper

　Direct Orthogonal Mappingというアルファベット列とカタカナ（や中国語）の対応を取ってしまう手法。例えば「Goo=グー」「gle=グル」と対応を取ってしまう。

  • Hagiwara and Sekine, Latent Class Transliteration based on Source Language Origin, ACL 2011, short paper

　外来語は語源の言語があるからそれを隠れクラスとしてモデルを構築しよう！という話。理解していません。

  • Yoh Okuno, Applying mpaligner to Machine Transliteration with Japanese-Specific Heuristics, Named entity workshop at ACL2012　

　詳しくは読んでいないのですが、少し表の数字が低いことが気になりますかね。（あくまで実用面での意味で。）

  • Hagiwara and Sekine, Accurate Word Segmentation using Transliteration and Language Model Projection, ACL 2013, short paper

　カタカナ文字列は長いと細切れになってしまうからこれを何とかしよう、という話。詳しく読んでないです。

B. スペル修正

  • Li et al. Exploring Distributional Similarity Based Models for Query Spelling Correction, ACL/COLING 2006

　僕が個人的に気に入っている論文です。手法の一つが「今までのString-based（編集距離等）な素性とDistributionalな素性（語の周辺情報）を使用できるよう最大エントロピー法を利用すればいいんじゃない？」という論文。わかりやすく、直感的で実装しやすそうなので好きです。

C. 正規化

  • 斉藤 いつみ et al. 正規-崩れ表記のアライメントに基づく表記崩れパタンの抽出と形態素解析への導入, NL研 2013

　1. のBrillらの手法を参考にSNS上の崩れがどのように変換されたかのアライメントを取りましょう！という話。

　あと略語とかに焦点を当てた論文がいくつかありますので、時間があれば追記しておきます。そして詳しく読んでからもう一回書くかもしれません。

      • -

1月9日：１．の論文とHagiwaraとSuzukiのACL2008の論文で考えたことを追記しておきました。

プログラミングスキルを向上させる上での心がけに関する資料メモ

CRF入門は少しお休みして、表題の件で自分が他の方々から見聞きした話、そして体験を元にまとめてみます。名著は星の数ほどある、と個人的に思っているのでリストはできるだけ絞っています。

１．Teach Yourself Programming in Ten Years
Googleの研究開発トップであるPeter Norvigが書いた記事。名言とも思うフレーズを挙げておきます。
「Bad programming is easy. Idiots can learn it in 21 days, even if they are dummies.」
「do some because it is fun.」
「But you won't change your life, or your real overall expertise as a programmer in 24 hours, days, or even weeks.」

２．How To Become A Hacker
インターネット上の古典的名著。未だに更新されているのがすごい。

３．Cracking the Coding Interview: 150 Programming Questions and Solutions

Cracking the Coding Interview: 150 Programming Questions and Solutions

Cracking the Coding Interview: 150 Programming Questions and Solutions

  • 作者: Gayle Laakmann Mcdowell
  • 出版社/メーカー: Lightning Source Inc
  • 発売日: 2011/05/20
  • メディア: ペーパーバック
  • 購入: 3人 クリック: 16回
  • この商品を含むブログを見る
外資系企業におけるソフトウェアエンジニアの採用試験対策の本。これは読む本というよりは、自分で手を動かして解く問題集です。

４．Coursera
向き不向きはあると思いますがMassive Open Online Courses（MOOCs）は有名な方々が講師を勤めて、Assignmentsもあるので良いと思います。

思い出し次第、追記しながら書いていきます。

Conditional Random Fields（CRF）入門その2 -ブログ資料と勾配について-

CRFが未だに実装かつフルに理解できていないです。CRFは一筋縄ではいかないことがブログ資料の多さからもわかります。ただ（一部の？）構造予測問題においては今流行りの多層Neural NetworkよりF1値が高いことが伺えますので、未だに重要な手法の一つなので、頑張って理解します。IME本に沿って書いており、ただでさえ無い行間を更にしつこく埋めていこう、という試みです。不適切だったら消しますのでご連絡ください。また、間違いがあった場合も指摘して頂けるとありがたいです。

前回（Conditional Random Fields（CRF）入門その1 -主な参考資料と目的関数-）の続きで、今回は勾配gに関してです。

は素性関数の集合、が学習データの一入力系列であり、が学習データの一ラベル系列です。添字がありますが、ここでは一変数ではなく、ベクトルの一例を示しています。添字がないものはベクトルの集合として認識してください。第一項が正解の系列に対して重みを足す、第二項で正解の系列と間違っている系列全ての重みをその系列の現在の確率と掛けあわせてから引きます。

勾配に関しては主に実際に計算（実装）するときにいかに効率良く実装するか、という話がメインです。SGDを用いて最適化する際は、重みの更新回数だけ勾配を計算するので、より効率が良い方がより早く学習が終わります。

HMMでも利用されている前向き後ろ向きアルゴリズムが一番効率が良く勾配を計算できます。効率を重視しなければ他の方法でもできます。勾配のどの部分がそんなにネックになっているんでしょうか？答えはの部分です。の定義をもう一回思い出してみましょう。


ただし、

このZは『すべての経路に対して「その経路で有効になる素性の重みの和に対するexp」』（IME本、p.201）なので、愚直な実装ならラベル列が取り得る全ての経路に関して計算する必要があります。これをできるだけ簡単にする試みが前向き後ろ向きアルゴリズムです。

前向き後ろ向きアルゴリズム

を前向きアルゴリズムによって算出された変数、
を後ろ向きアルゴリズムによって算出された変数とするのが通例みたいです。

前節で出てきた「ある経路で有効になる素性」をここでは「ある経路」＝「ある経路にある一ノード」と読み換えて進めていきます。その為、ここでは（あとIME本では）を「ノードNに対する」と定義します。

ではとはなんでしょう？は「前向きにグラフを辿ってきて、ノードNに行き着く全ての経路のの和」であります。まだ少し曖昧に感じるので、IME本p.202に出てくる

  1. スタートからゴールに進む経路においては積を取る
  2. 合流する経路はそれらの経路に対する確率の和を取る

の２点をポイントととして補足しておきます。

は以上の説明における「前向き」を「後ろ向き」に置き換えたものです。

これらを利用してはノードNに対する素性関数として、


（ or ）

とすれば効率よく勾配が計算できます（途中ちょっと端折りました）。後は更新式が収束するまで重みwを更新していけば学習したモデルが構築できます。

次回はいよいよ学習したモデルを用いて、Viteribiアルゴリズムによる予測について書きます。

雑記

IME本に関するすごい方々の議論で出てきた「生成モデルと識別モデルの比較」に関する論文は面白そうなんで今度読んでみたいですね。

参考資料

IME本

日本語入力を支える技術　?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

日本語入力を支える技術　?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

参考資料（ブログ編）

http://lingpipe-blog.com/2009/06/18/chainconditional-random-fields-implementation-and-design/
http://d.hatena.ne.jp/a_bicky/20100621/1277076531
http://blog.unnono.net/2010/09/logsumexp.html
http://d.hatena.ne.jp/echizen_tm/20110622/1308746693
http://d.hatena.ne.jp/jetbead/20111125/1322236626
http://d.hatena.ne.jp/takeda25/20121106/1352385509

L-BFGSを使う理由（CRFのライブラリの一つであるCRFsuiteでは使っていますね）

http://blog.unnono.net/2011/04/newton-cg.html

Conditional Random Fields（CRF）入門その1 -主な参考資料と目的関数-

Conditional Random Fields（CRF）がわかりません。何それおいしいの？状態ですが、ここから学習をはじめています。前向きアルゴリズム？後ろ向きアルゴリズム？Viterbiアルゴリズム？どこで使うのそれ？状態ですね。その状態を脱出するため日々奮闘中です。なお、この記事では自分の思考に則って書いていますので、綺麗な教科書的ではないこと（構造学習がなんたら等はあまり触れない）を始めに断っておきます。

脱出するために利用している資料は以下の通りです：

1.「日本語入力を支える技術」（以下IME本）：実装する上では一番初心者にやさしい本です。

日本語入力を支える技術　?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

日本語入力を支える技術　?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

2.「Crfと素性テンプレート」：具体例があって非常にわかりやすいです。数学ガール風に言えば、「例示は理解の試金石」なので、重要ですね。

3. An Introduction to Conditional Random Fields for Relational Learning：CRFに関する有名なTutorialです。数式の流れがHMMからの拡張として導出されているのでわかりやすいです。ただし、長い上に数式もかなり出てくるので完全に理解するには数年かかりそうです。

1.と2.は特におすすめです。目的関数の動きのイメージが詳しく書かれているので、わかりやすいです。3.は初心者である自分にとっては詳しすぎる感じがあるので、末永く付き合っていきます。他にもCourseraの授業や、130行で実装されたCRFのPythonコード等があります。しかし、Courseraの授業は確率的トピックモデルからの視点で幅広く説明しており、コードに関しては解説がないので僕には難しいです。

CRFの概要

まず、CRFは機械学習における一つの学習手法です。機械学習の手法は基本的に「重みを目的関数に沿って最適化」しています。では何の重みか？どういう目的関数なのか？というのを順番に見ていきます。

重みに関して

CRFで調整する重みは「素性関数に対する重み」です。ここでは素性（素性関数の引数）としては、１．入力系列、２．直前のラベル、３．ターゲットとしている現在のラベル、４．何番目の状態か（tで表すものとします）。

「例示は理解の試金石」なので、タスクとして、ゲームのタイトルを文字レベルで抽出するタスクを考えます。
入力系列としては以下の文字列、ラベルとしてはB(egin)、I(nside)、O(utside)、として考えましょう。

今日はドラクエとFFをプレイした。

この時、
今：O、日：O、は：O、ド：B、ラ：I、ク：I、エ：I、と：O、F：B、F：I、を：O、プ：O、レ：O、イ：O、し：O、た：O、。：O
が正しいラベル系列であります。１．入力文字ド、２．直前のラベルO、３．現在のラベルB、４．（頭から数えて）4番目の状態になります。素性関数の一例としては、になっています(doは「ド」のことです。日本語が表示できないのでローマ字表記しています)。これらの素性関数一つ一つに重みを割り振っていきます。

目的関数に関して

CRFにおいて、最適化の対象とする目的関数は：

ただし、 です。ここでは素性関数を表し、xは入力系列、yはラベル列を表しています。Zは確率であることを保証している為に用いられています。

この目的関数自体は（前向き後ろ向きアルゴリズム等のキーワードと関連している）直接的なポイントではなく、メインは最適化する際に関係してきます。最適化手法として、ここでは基本的な最適化手法の一つである確率的勾配降下法（Stochastic Gradient Descent, SGD）を使います。これはIME本のp.165にある通り、「すり鉢状になった土地を歩いて...最後にいちばん低いところにたどりつく」「ただし、...自分の近くしか見えない...」というイメージがぴったりだと思います（CourseraのMachine Learningの授業で良いイメージ図があるので、詳しくはそちらを）。蛇足ですが、最急降下法との違いは「必ずしも全学習データを使わない」「一つずつデータを処理するかどうか」の二点です。
（ちなみにIME本にも触れられていますが、IME本で主に使われているFOBOSとSGDの違いは微分不可能な点に対処できるかできないか、です。ただし、2009年の話ですが、L1-SGDなどの手法も提案されているようです。詳しくはL1-SGD等を参照してみてください。またFOBOSに関してはIME本とFOBOSを実装してみた(理論編) - Goto_youthKの徒然日記等を参照してみてください）

以下がSGDによる重みの更新式です：

gは勾配でηは学習率です。

このgを効率良く算出するために、前向き後ろ向きアルゴリズムを用います。また、Viterbiアルゴリズムは実際にCRFモデルを構築した後に、テストケースに関して適用する際に利用します。そこらへんの話はまた今度の記事にて書きます。