入力\(x\)から出力\(y\)への関数を学習する機械学習の中で、出力が構造を有している問題は構造学習（Structured Output Learning）と呼ばれ、自然言語処理をはじめ、検索のランキング学習、画像解析、行動分析など多くの分野でみられます。 今回はその中でも複数の構造情報を組み合わせても効率的に学習・推論ができる双対分解による構造学習について紹介をします。 # 構造学習についてよく知っているという方は双対分解による構造学習のところまで読み飛ばしてください。 構造学習の導入 構造を有した出力の例として、 ラベル列　（品詞、形態素列の推定、時系列におけるアクションの推定、センサ列） 木　　　　（係り受け解析における係り受け木、構文解析木、談話分析、因果分析） グラフ　　（DAG:述語項構造による意味解析　二部グラフマッチング:機械翻訳の単語対応） 順位付集合（検索における順位

昨日開催された「第1回 データ構造と情報検索と言語処理勉強会(DSIRNLP)」に発表者として参加しました。主催者の@overlastさん、発表者の皆さん、ボランティアの皆さん、会場を提供してくださったミクシィさん、そして発表を聞いてくださった皆さん。どうもありがとうございました。 また発表スライドについては@overlastさん、@uchumikさん、@machyさん、@nokunoさんにチェックして頂きました。特に@uchumikさん、@machyさんより頂いた意見のおかげでスライドの質が向上しました。ありがとうございました。 発表スライド： (scribdのembedがうまくいかなかったので暫定的にリンクおいておきます) TRIEにトライ！〜今日からはじめるTRIE入門〜 本記事では質疑応答でフォローしきれなかった部分を中心に、私の発表の補足的なものを書いて行きます。 会のまとめ的な

TokyoNLP 第8回に のこのこ参加。主催者の id:nokuno さん、発表者＆参加者のみなさん、そして会場を提供してくださった EC ナビさん改め VOYAGE GROUP さん＆ @ajiyoshi さん、お疲れ様でした＆ありがとうございました。 今回は「∞-gram を使った短文言語判定」というネタを発表。「短文言語判定」って、要は「このツイートは何語？」ってこと。 こちらが資料。 ∞-gram を使った短文言語判定 View more presentations from Shuyo Nakatani そして実装したプロトタイプ ldig (Language Detection with Infinity-Gram) とモデル(小)はこちらで公開。 https://github.com/shuyo/ldig 言語判定とは「文章が何語で書かれているか」を当てるタスクで、以前一度

動機 前回書いた通り、会社内にデータは全く貯められていない状態です。ですが、将来ログをまともに取得した場合のデータは膨大になることが想定されました。そこで、（時間/空間）計算量を考慮するとオンライン学習アルゴリズムを使うのが最良と判断しました。 （以前のpostも想定しての話を書いています。いろんな意味で残念ですね...orz） 今までオンライン分類器をまともに使った事がなかったため、性能評価も兼ねていくつかの分類器を試してみたというわけです（随分前にですが...）。 オンライン分類器の概要 線形分類器は大体 $w^*:=argmin_wΣ_iL(x^{(i)},y^{(i)},w)+CR(w)$ $L(x^{(i)},y^{(i)},w)$：ロス関数, $R(w)$：正規化項 で表すことができると思います。 オンライン学習では、「データを1つ受け取るたびに逐次的にウェイトを更新する」とい

機械学習では、データがどのクラスに属するかを識別するという問題が基本的です。 この識別問題は線形識別器というモデルを使うことで解くことができます。 この記事では、実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説を行います。 AdaGrad+RDAの詳細な解説は以下の論文を参考にしてください。 http://www.magicbroom.info/Papers/DuchiHaSi10.pdf こちらはAdaGrad+RDAの実装例です。 http://d.hatena.ne.jp/echizen_tm/20140726/1406376207 識別問題は、通常データを2つのクラスに分類します。どうやって分類するかというと、線形識別器が正の値を返したか、負の値を返したかでクラスを分けます。 具体的には、線形識別器は以下の形式をしています。 y = Σ(x_i * w_i) データを表

機械学習×プログラミング勉強会 vol.2 での発表資料です。 ベイズの何が嬉しいか、ノンパラベイズの何が嬉しいかを数式を使わず語ります。

ねこと画像処理。 (みかん – 吉祥寺 きゃりこ) 前回の ねこと画像処理 part 2 – 猫検出 では画像内の猫の顔を検出する方法を紹介しましたが、今回はディープラーニングの技術を用いて猫の品種を識別したいと思います。 学習データ ねこと画像処理 part 1 – 素材集めでは、自分で撮影した写真を学習データとして使うと書いたのですが、都内の猫カフェ等で出会える猫に限ってしまうと品種の偏りが大きくなってしまうので、ここではしぶしぶ研究用のデータセットを使うことにします。。ただ、Shiba Inuがあるのに日本が誇るMike Nekoが含まれていないのでデータセットとしての品質は悪いと思います。 The Oxford-IIIT-Pet dataset オックスフォード大学が公開している動物画像のデータセットです。その内猫画像は2400枚、クラス数は12で1クラスにつき200枚あります。今

米Twitterは8月20日（現地時間）、新スパム対策システム「BotMaker」の導入により、スパムを40％削減できたと発表した。 Twitterはほぼリアルタイムのツイートを表示するというサービスの性格上、スパム遮断が技術的に難しい。また、開発者向けにAPIを公開しているため、スパマーはTwitterのスパム対策の手の内を把握できてしまう。 Twitterはこの2つの問題に対処するために、BotMakerを構築した。このシステムは、ボット（イベントが発生した際にどう対処するかを決めるルール）の集合で成り立っており、1日当たり数十億件のイベントに対処している。プロセスは、リアルタイムツールの「Scarecrow（かかし）」、Scarecrowが見逃したイベントに機械学習技術で対処する「Sniper（狙撃者）」、ユーザーの行動データを分析する周期的なプロセスの3段階ある。 ボットは人間が読

機械学習とは？ 今日は、機械学習をテーマにしてブログを書いてみます。「機械学習」と言えば、Googleなわけですけど、最近Googleがワールドカップの勝敗予想を機械学習で行って「すげー！」っておそらく一部界隈では盛り上がりました。最近では一般にも「機械学習」という言葉は少しづつ普及しつつあるようです。Google Trendで見ても、右肩上がりです。 ただ、機械学習という言葉（Machine Learning）という言葉は情報分野で比較的昔からあるようです。アメリカの科学者はトム・M・ミッチェルはこんな定義を与えています。 コンピュータプログラムがある種のタスクTと評価尺度Pにおいて経験Eから学習するとは、タスクTにおけるその性能をPによって評価した際に、経験Eによってそれが改善されている場合である 簡単にいえば、あるタスクをこなして、それを「評価尺度P」で測ったときに、経験「E」（：デ

2. 目次 • 1. 自己紹介 • 2. 概要：Random Forestとは • 3. 理論編 •  3-1. 決定木 •  3-1. Random Forest • 4. 実践編(プログラミングの流れ) •  4-1. 決定木 •  4-1. Random Forest • 5. デモ • 6. 参考文献

フリークアウトとはてなは8月19日、広告配信先の自動判定（アドベリフィケーション）機能「BrandSafe はてな」を共同開発し、フリークアウトが提供するRTB（リアルタイム入札）対応DSP「FreakOut」において、「BrandSafe はてな for FreakOut」として提供すると発表した。 FreakOutを利用する広告主は同機能を使うことにより、広告配信先から、違法サイトや広告主の指定する不適切なサイトの買付けを自動的に抑制できる。バナー広告だけでなく、動画広告にも対応。国内ではこれまで、広告配信先のホワイトリスト・ブラックリストへの指定は手動で行うのが一般的となっていた。フリークアウトの事業担当者は「必要な機能がやっと備わった」と胸をなで下ろす。 アルゴリズムは、はてながソーシャルブックマークサービス「はてなブックマーク」で培ってきた機械学習のエンジンをもとに開発。はてなブ

はじめに 文書分類マスターを目指して修行の旅に出るために必要そうな知識を、ざっとメモしておく。(かなり雑だけど・・・) 文書分類とは テキスト分類、Text Classification あらかじめ決められたカテゴリ集合に基づき、与えられた文書に適切なカテゴリを付与する事 排他的分類 : 1つのテキストにカテゴリを1つだけ付与される場合 マルチラベル分類 : 1つのテキストに複数のカテゴリ付与を許す場合 基本的には、目的の分類をどのような分類手法に落とし込むか？を考えることになる 主なアプローチとして、以下のような流れで処理する(教師あり分類) 学習データから素性(なんらかの特徴)を抽出し、それらの規則を見つけだす 規則に基づく分類モデルを作成 未知の文書に対して素性を抽出したものにモデルを適用し、分類結果を返す 利用例 内容に関する分類 ニュースジャンル分類 SPAMフィルタ 属性に関す

はじめに G. Tsoumakas, I. Katakis, I. Vlahavas., Mining Multi-label Data http://lpis.csd.auth.gr/paper_details.asp?publicationID=290 マルチラベル分類問題について、メモ。 マルチラベル分類問題 1つの事例が、複数のラベル(ラベルの集合)に同時に分類されうる分類問題 例：「ダビンチコード」の記事のカテゴリ→宗教、映画 マルチラベルの教師あり学習では、主に以下のタスクがある マルチラベルクラス分類(multi label classification) ラベルランキング(label ranking) また、マルチラベル学習の方法は、主に2つのグループに分けられる Problem Transformation Algorithm Adaptation シングルラベル問題へ変

最近にわかにword2vecが流行っています。ので、乗っかってみました的記事です。 理論に関してはあまり詳しくしらないので、印象だけで語っているかもしれません。何かありましたらTwitterかコメント等でご指摘いただけますと幸いです。 ちなみに、失敗した話が多いです。 word2vecと単語のベクトル表現 word2vecは、機械学習の分野で使われる、ニューラルネットというモデルを使ったツール／ライブラリです*1。名前の通り、wordをvectorにします。vectorにする、というのは、ベクトル表現を獲得するということで、意味(みたいなもの)の獲得というか、素性の獲得というか。 単語のベクトル表現の獲得自体は、別にword2vecにしかないわけではありません。言い換えると、昔からあります。LDAを使って単語のトピック分布のようなものを学習したり(vingowでやりました)。余談ですが、こ

サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。

NAVER まとめという、他人のコンテンツを引用しまくってアクセス数を荒稼ぎするサイトに「ディープラーニングってどんなの？」みたいな記事をあげてみました。 GoogleやFacebookが注目するディープラーニング（深層学習）についてまとめてみた - NAVER まとめ まとめにも書いてある通り、変な点があればTwitter(@takeshi0406)に教えていただくか、まとめ作成に参加していただけると嬉しいです。 機械学習の研究や応用って、多くの人に注目されている割に、エンジニアや研究者以外にわかる説明があまりない気がします。というわけで、フツーの人が見るサイトに記事をおいてみたらどうなるか試してみます。 その割に、いきなりニューラルネットワークについて何の説明もなく書いてしまい、多分エンジニアが見たらショボショボで、フツーの人が見たらわけがわからない、ビミョーな感じになってしまった気も

AdaGrad(Adaptive Gradient)というオンライン学習のアルゴリズムを実装しました。 https://github.com/echizentm/AdaGrad 論文: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization(http://www.magicbroom.info/Papers/DuchiHaSi10.pdf) AdaGradはAROWのように重みの更新を適応的に行うことが出来るほか、正則化のアルゴリズムと組み合わせることが出来るという利点があります。 このためFOBOSやRDAなどを用いたL1正則化によって特徴量を疎にすることが出来ます。今回はRDAと組み合わせたAdaGradをperlで実装しました。 RDAを用いた理由は上記論文でFOBOSよりも高性能だった