サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
世界禁煙デー
www.chokkan.org
C言語を勉強するとき,文法や標準関数をマスターすることに並ぶくらい重要なのが,デバッガを使いこなせるようになることです.C言語を習いたての頃は,書いたコードが予期せぬ動作をしたり,ポインタの使い方を間違えてプロセスを落とすこと(セグメンテーション違反)なんてザラです.そういう失敗をたくさん経験して,自分の書いたコードの間違いに気づき,修正していくことでコーディング力が養われていきます.しかし,自分の書いたプログラムの何処が悪いのか,皆目見当もつかないような状況に陥ってしまうと,プログラミングが嫌いになってしまいます. デバッガを文字通りに解釈すると「バグを取る」ためのツールで,プログラマにとってはコードの間違いを発見するための検証手段として欠かせません.これに加えて,正しいコードをデバッガ上で動かしてみることも,C言語の理解促進のために重要であると私は考えています.ループや条件分岐でプログ
言語処理学会第19回年次大会 (NLP2013) チュートリアル資料(岡崎担当分) 岡崎 直観 東北大学大学院情報科学研究科 okazaki at ecei.tohoku.ac.jp http://www.chokkan.org/ @chokkanorg 研究者流 コーディングの極意 1 研究におけるコーディングの極意? • 今回のチュートリアルをきっかけにサーベイ – ソフトウェアエンジニア向けの指南書は存在 – でも,研究者向けの資料は数少ない • 自分が修士課程の頃は完全に我流だった – 複数文書自動要約のプログラムをすべてC++で実装 – *NIXを使うスキルはなく,すべてWindows上で実行 – 今から考えると,無駄だらけの実験作法だった • ほとんどの大学では実験の講義があるが… – 研究のためのコーディング作法は教えてくれない 2 繰り返される残念な光景 • 論文の締切前日
Classification (分類) Information Communication Theory (情報伝達学) 1 Naoaki Okazaki okazaki at ecei.tohoku.ac.jp http://www.chokkan.org/ http://twitter.com/#!/chokkanorg #nlptohoku http://www.cl.ecei.tohoku.ac.jp/index.php?InformationCommunicationT heory 2011-10-11 Spam mail Information Communication Theory (情報伝達学) 22011-10-11 How many spams do you get (per day)? • My office address: okazaki at ecei.to
ポインタの裏話 岡﨑 直観 okazaki at ecei.tohoku.ac.jp http://www.chokkan.org/ @chokkanorg ポインタの裏話 プログラミング演習A 1 このような説明を 覚えていますか? 知らなくても全く問題ありません ポインタの裏話 プログラミング演習A 2 int x = 0; &xは変数xの「アドレス」 「番地」「住所」を返す 変数x 0 &x メモリ空間, 記憶空間 変数xのアド レス(住所) ポインタの裏話 プログラミング演習A 3 ____ / \ 何言ってたんだこいつ? / ⌒ ⌒\ 番地 アドレス ぬるぽ / (●) (●) \ \ / | 、“ ゙)(__人__)" ) __________ \ 。` ⌒゚:j´ ,/ j゙~~| | | | __/ \ |__| | | | || / , \n||
. . PRML (4.3) (4.4) (4.5) 2009-03-16 ( ) PRML 2009-03-16 1 / 56 1 2 BIC 3 4 ( ) PRML 2009-03-16 2 / 56 . . p(Ck|x) x p(x|Ck) p(Ck) p(Ck|x) p(x|Ck) p(Ck) ( ) PRML 2009-03-16 3 / 56 x ϕ(x) ϕ(x) x ϕ(x) = x ϕ0(x) = 1 w0 x C1 C2 x ϕ(x) 4.12 ( ) PRML 2009-03-16 4 / 56 ϕ = ϕ(x) C1 C2 Support Vector Machine (SVM) P(C1|ϕ) P(C2|ϕ) [LLAN06, LWK07] ( ) PRML 2009-03-16 5 / 56 C1 C2 . . p(C1|ϕ) = y(ϕ) = σ(wT ϕ
Constituency parsing (句構造解析) Information Communication Theory (情報伝達学) 1 Naoaki Okazaki okazaki at ecei.tohoku.ac.jp http://www.chokkan.org/ http://twitter.com/#!/chokkanorg 2011-10-25 Acknowledgements • Portions of this material are from: • D. Jurafsky and J. H. Martin (2009). Speech and Language Processing, Pearson. • J. Nivre and S. Kübler (2006). Dependency Parsing. Tutorial at Coling-ACL 2006
Part of speech tagging (品詞タグ付け) Information Communication Theory (情報伝達学) 1 Naoaki Okazaki okazaki at ecei.tohoku.ac.jp http://www.chokkan.org/ http://twitter.com/#!/chokkanorg #nlptohoku http://www.cl.ecei.tohoku.ac.jp/~inui/lectures/2011/SC/03nlp.pdf 2011-10-18 Today’s topic • What are part-of-speeches? • Part-of-speech tagging as sequential labeling problem • Hidden Markov Model (HMM) • Structu
昨日プレスリリースの通り,JST戦略的創造研究推進事業「さきがけ」の研究領域「情報環境と人」に,自分が申請していた研究課題が採択されました.研究課題名は「知識の自動獲得・構造化に基づく情報の論理構造とリスクの分析」です.研究の概要は次の通りです. ウェブやソーシャルメディアなどの新しい情報環境により、情報の流通が加速する一方、偏った情報やデマなどの拡散による社会の混乱や不安が増大しています。本研究では、ネット上で言及されている物・事態に関する知識を計算機がロバストに獲得・活用する言語処理技術を基盤として、流通している情報の背後にある論理構造を解析し、その整合性を分析することで、安全・危険に関する多角的な判断材料を人や社会に提供します。 研究総括の石田亨先生の総評にもありますが,この研究は東日本大震災を強く意識したものになっています.世の中の状況に左右されず,研究者は自身の研究に邁進すべきと
CRFsuite 0.12のリリースに合わせて,チャンキングタスクによるベンチマークを更新しました.見所は,0.11→0.12でどのくらい速くなったのか,高速だと謳っているWapitiがどのくらい速いかです.その他,各学習アルゴリズムによる性能(学習速度,精度)差も,興味深い点かと思います.比較したツールは, CRFsuite 0.12 CRFsuite 0.11 (1つ前のバージョン) sgd 1.3 CRF++ 0.54 Wapiti v1.1.3 MALLET 2.0.6 実験では,L2正則化(C=1),L-BFGSの終了条件は直近10回の反復で目的関数の改善率が1e-5を下回ったとき,平均化パーセプトロンの反復回数は50に固定,という条件にしました. まず,CRFsuite 0.12で実装された平均化パーセプトロン(AP)は,非常に高速でありながら,L-BFGSやSGDに迫るタグ付
CRFsuiteのバージョン0.12をリリースしました.このバージョンは変更点がてんこ盛りです.張り切りすぎたせいで,ドキュメントの更新に手間取り,コードが出来てからリリースまで1年くらい経過してしまいました.変更点はChangeLogの通りですが,このブログではいくつか補足しながら紹介します. ソースコードの大がかりな再構成を行いました.特に,グラフィカルモデルの処理に関する部分(対数尤度や勾配の計算など)と,学習アルゴリズムに関する部分を分離しました.今回のソースコードの再構成により,新しい学習アルゴリズムの追加や,異なる形状のグラフィカルモデル(例えば属性とラベルバイグラムに対する素性や二次マルコフ素性)を追加しやすくしました.ソースコードの再構成をやるモチベーションは前々からあったのですが,@yuutatさんの「Fast Newton-CG Method for Batch Lea
Windows環境の場合は,配布されている実行ファイルを利用するのが最も簡単です.ただし,配布されている実行ファイルを利用するには,システムにVisual C++ 2008 SP1 再頒布可能パッケージ (x86)がインストールされている必要があります. Linux環境の場合は,ソースコードからビルドしてください. ビルド方法は,こちらを参照してください. Classiasは二値分類(binary classification),多クラス分類(multi-class classification),候補選択(candidate classification)の3つのタスクをサポートします. 二値分類は,与えられた事例の素性(属性)に基づいて,事例を正例(+1)もしくは負例(-1)に分類するタスクです. 事例のラベルには,"+1", "1", もしくは"-1"を用いることができ,ラベルにコロ
本日、東北大学で辞令交付式があり、情報科学研究科の准教授に任命されました。今後は、乾健太郎さん、研究室の学生・スタッフさんと一緒に、自然言語処理や知識処理の研究を進めていきます。 この日を迎えられたのも、諸先生・先輩・同僚・学生・友人の皆様のお陰です。全員挙げるとキリがないくらい、いろいろな方にお世話になりました。これから約10年間が、自分にとって本当に大切な時期だと考えていて、これまで以上に研究と教育に打ち込んで行こうと思いますので、ご指導・ご支援をよろしくお願い致します。
ロジスティック回帰やCRFなどの対数線形モデルの学習でよく出てくるのが,expの計算です.これをSSE2を使って高速化するのが,今回のテーマです.まずは,背景の理論を説明します. まず,指数関数を2の指数関数に変換することを考えます(なぜ2の指数関数かはいずれ分かります). 両辺の自然対数をとり,について解くと,.IEEE754など,2を基数とした指数部を採用している浮動小数点形式では,整数に対してを容易に構築できるので,上式の実数解の代わりに整数, を用い,の大まかな値を計算することを考えます.ただし,はを超えない最大の整数を表します. さて,をで近似したときの誤差の範囲は,.誤差にを乗じたものを,と定義すると, 上式の両辺の指数をとると, ここで,はを超えない最大の整数なので,の値域は,. これらのことから,は以下のステップで計算出来ることが分かります. を計算する. を計算する. を
最後に,の計算がどのくらい高速化できたのか,実験してみました.アルゴリズムとして,以下のものを比較しました. libcのexp関数 パデ近似を用いたもの(cephesの実装に近いです) 5次~13次でテーラー展開を0を中心として行ったもの 5次~13次の最良多項式近似をの範囲で行ったもの 5次~13次の最良多項式近似をの範囲で行ったもの 5次~11次の最良多項式近似をの範囲で行ったものをSSE2で実装したもの SSE2の実装で11次で打ち止めしているのは,11次と13次で演算精度の差が殆どないことが分かり,単に実装するのが面倒くさかったからだけです.0を中心としたテーラー展開や,最良多項式をの範囲で構成する手法は,の値を切り下げではなく,四捨五入(つまり0.5を足してから切り下げる)で求めます(Wapitiやsse_mathfun.hのexp計算ルーチンは四捨五入を使っています). 実験で
Company Logo 乱択アルゴリズムと自然言語処理: Locality Sensitive Hashing を用いた 高速な名詞クラスタリング Randomized Algorithms and NLP: Using Locality Sensitive Hash Functions for High Speed Noun Clustering D. Ravichandran, P. Pantel, and E. Hovy (ACL 2005) 読み⼿: 岡崎直観 Company Logo この論文について ⼿法とその背景理論がすごく興味深い – 他にもいろいろ使えそう 乱択アルゴリズムの雰囲気が味わえる – ランダムが織りなす不思議な世界 すぐれた実装⽅法を⽰している – 誰でも簡単に実装できる 2005年の研究だが,いまだに⾊褪せてはいない – 画像類似検索でLo
SimStringは,類似文字列検索のための高速かつシンプルなライブラリです. 類似文字列検索とは,文字列集合(データベース)の中から,クエリ文字列との類似度が閾値以上のものを,見つけ出す操作です. クエリ文字列と完全に一致しなくても,データベース中の似ている文字列を検索することができるので,スペル訂正,あいまい計算,柔軟な辞書マッチング,重複レコード検出,データベース統合など,様々なアプリケーションを構築できます. SimStringは,類似度関数として,コサイン係数,ジャッカード係数,ダイス係数,オーバーラップ係数に対応しています. 文字列の類似度を計算するための特徴量としては,文字nグラムをサポートしています. SimStringには,次のような特徴があります. 高速な類似文字列検索アルゴリズム.Google Web1T の英語単語(13,588,391文字列)から,コサイン類似度が
CRFsuite: a fast implementation of Conditional Random Fields (CRFs) CRFSuiteは,条件付き確率場(CRF: Conditional Random Fields)に基づく系列ラベリングの実装です. このソフトウェアの最大の目標は,メモリ使用量やソースコードの汎用性を犠牲にする代わりに,CRF確率モデルの訓練とタグ付けをできるだけ高速化することです. その結果,CRFsuiteはC++を用いた既存の実装と比べ,5.4倍から61.8倍のスピードで確率モデルの訓練を行うことができるようになりました. CRFsuiteは,Orthant-Wise Limited-memory Quasi-Newton (OW-LQN) 法に基づくL1正則化(ラプラシアン事前分布),Limited-memory BFGS (L-BFGS) 法に
A fast and simple algorithm for approximate string matching/retrieval SimString is a simple library for fast approximate string retrieval. Approximate string retrieval finds strings in a database whose similarity with a query string is no smaller than a threshold. Finding not only identical but similar strings, approximate string retrieval has various applications including spelling correction, fl
SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました.類似文字列検索とは,文字列集合(データベース)の中から,クエリ文字列と似ているものを見つけ出す処理です.コンピュータは,正確に一致する文字列を探すのは得意ですが,表記揺れに出くわすと,途端に対応できなくなります.例えば,「スパゲティ」に対して,レストラン情報などを返すサービスにおいて,「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると,通常のデータベースでは情報を提示することが出来ません.類似文字列検索を用いると,表記揺れが検索クエリに与えられても,「スパゲティ」という既知語を代替クエリとして提案したり,「スパゲティ」の情報をダイレクトに引き出すことができるようになります. 似てる語を探す技術って,文字列処理の基本中の基本で,自然言語処理では当たり前のように使われていてもおかしくな
先週まで論文執筆モードだったので,ご報告が遅れましたが,娘の名前は心優(みゆ)にしました.この名前を聞いて「当て字っぽくて読めねー」と感じるか,「ありがちな名前」と感じるかで,最近の子供の名前に対する精通度が分かります.人気の名前はあまり付けたくなかったのですが,2009年の名前のランキングに普通に出てきます.文字通り「心優しい」ですが,「優」を漢語林で引くと,「上品で美しい」「みやびやか」「おだやか」「しとやか」「情深い」「のびやか」「ゆるやか」など,女の子にはうってつけの多義が並べられています. 名前を決めるのは本当に大変でした.考えれば考えるほど,自分の探索空間が足りているのか不安になりました.結局は,コンピュータが生成した6,084個(読みで数えた数)の名前の候補から,私と嫁で一つ一つチェックしながら結論を出しました. 名前の候補を生成する流れは,次の通りです. 名前辞典などを見な
A collection of machine-learning algorithms for classification Classias is a collection of machine-learning algorithms for classification. Currently, it supports the following formalizations: L1/L2-regularized logistic regression (aka. Maximum Entropy) L1/L2-regularized L1-loss linear-kernel Support Vector Machine (SVM) Averaged perceptron
Static Double Array Trie (DASTrie) Introduction Trie is a data structure of ordered tree that implements an associative array. Looking up a record key (usually a string) is very efficient, which takes O(1) with respect to the number of stored records n. Trie is also known for efficient prefix matching, where the retrieved key strings are the prefixes of a given query string. Double-array trie, whi
私が昔所属していたNaCTeMで公開している,略語辞書サービスAcromineをひっそりと更新しました.以前のバージョンからの変更点は,以下の通りです. 2009年版Medlineのアブストラクトで略語抽出をやり直した 略語の完全形のクラスタリング方法を改良した 略語の完全形の異表記を表示できるインタフェースにするため,辞書検索結果の表示を表形式からツリービューに変更した 辞書引きサービスのAPIを,SOAPからREST/JSONに変更した 単に辞書の中身を新しくするだけではつまらないので,ツリービューをウェブブラウザ上で実装するときに,YUI Libraryを初めて使ってみました.ノード・ラベルの遅延ロードを行うツリービューが簡単に実装できて,便利ですね. 辞書引きサービスのAPIを使うには,登録手続きが必要になるようです(残念ながら私のコントロール範囲外).アカデミックな人たちは問題無
Averaged perceptron Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) [Nocedal80] Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) [Andrew07] Primal Estimated sub-GrAdient SOlver (Pegasos) [Shalev-Shwartz07] Truncated Gradient [Langford09], これはL1正則化に特殊化したFOrward LOoking Subgradient (FOLOS) [Duchi09]としても知られています
Classiasという分類のための機械学習アルゴリズムの実装を公開しました.今のところ,L1/L2正則化ロジスティック回帰(最大エントロピー法),L1/L2正則化L1損失線形カーネルサポートベクトルマシン(SVM),平均化パーセプトロンをサポートしています.学習アルゴリズムとしては,平均化パーセプトロン,L-BFGS法,OWL-QN法,Pegasos,Truncated Gradient(L1-FOLOS)を実装してあります.カーネルは使えませんが,線形識別モデルを高速に学習できるようになっています.二値分類,多クラス分類,候補選択(明示的に与えられた候補の中からスコア最大のものを選ぶタスク)をサポートしています(SVMは今のところ二値分類のみ). このツールはもともと,最大エントロピー法を自分で使うために実装したもので,作り始めてからもう2年くらい経過しています.去年のColingやEM
ベクトル x に対し,スカラーを返す凸関数 f(x) とその偏微分が与えられるときに, f(x) の値を最小にするような x を求める強力な手法として,準ニュートン法の一種であるL-BFGS 法が有名です.自然言語処理の分野では,L-BFGSは最大エントロピー法 (Maximum Entropy) や条件付き確率場 (CRF) など,log-linearモデルのパラメータを効率的に求めるための常套手段となっています.log-linearモデルは,目的関数 f(x) として確率モデルにおける学習データの対数尤度(の符号を反転したもの),偏微分として各素性の学習モデルにおける出現頻度と確率モデルにおける出現頻度(期待値)の差とおいて,パラメータ(素性の重み)をL-BFGS 法で簡単に導出します.「L-」が付かないBFGS法の詳細については,こちらが分かりやすいです.L-BFGSは,BFGS法の
C++ implementation of Constant Database (CDB++) Introduction Constant Database PlusPlus (CDB++) is a C++ implementation of hash database specialized for serialization and retrieval of static associations between keys and their values. The database provides several features: Fast look-ups. This library implements the data structure of the Constant Database proposed by Daniel J. Bernstein.Low footpr
CDB++という,静的ハッシュデータベースライブラリをリリースしました.ライセンスは修正BSDです. 静的ハッシュデータベースなので,いったんデータベースを構築したら,要素の追加や削除は行えません.その代わり,コンパクトなデータベース,高速な構築,高速な検索ができるようになっています.データ構造は,Constant Databaseを採用しています.Constant Databaseの実装はいくつかありますが,クロスプラットフォームでお手軽に使えるものがなかったので,作ってみました.また,このライブラリはcdbpp.hというインクルードファイルのみで構成されているので,このファイルをインクルードするだけでアプリケーションに組み込めます. ハッシュデータベースには,Oracle DBやTokyo Cabinetなど,優れた実装がたくさんあります.しかし,単にキーと値のペアをファイルに書き出し
次のページ
このページを最初にブックマークしてみませんか?
『Naoaki Okazaki - Home』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く