東大・情報理工の「創造情報学」専攻，院試の問題と解答まとめ（大学院入試の対策用） - 主に言語とシステム開発に関して
院試の解答の目次へ 東京大学の大学院・情報理工学系研究科で，創造情報学専攻の院試対策まとめ。 修士の試験問題と解答へのリンク。 とくに専門科目。 創造情報学の過去問と解答（年度別） 2011年の過去問と解答： 試験問題 http://i-web.i.u-tokyo.ac.jp/edu/cour... 解答 創造情報学専攻入試メモ 2011-8 第1問 (1-1) 分枝限定法 創造情報学専攻入試メモ 2011-8 第1問 (1-2) 探索木 創造情報学専攻入試メモ 2011-8 第1問 (2-1) (2-2) 創造情報学専攻入試メモ 2011-8 第3問 (1) 創造情報学専攻入試メモ 2011-8 第3問 (2) 創造情報学専攻入試メモ 2011-8 第3問 (3) 創造情報学専攻入試メモ 2011-8 第3問 (4) 創造情報学専攻入試メモ 2011-8 第3問 (5) 創造情報学専攻入
ユーザインターフェースのアルゴリズム - ワザノバ | wazanova
https://www.youtube.com/watch?v=90NsjKvz9Ns 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約4時間前 (注)参照しているビデオは、矢印キーで前のページに移動した後に、再び矢印キーで指定しているページに戻ってこないと、うまく再生機能が起動しないようです。面倒ですが、済みません。 Mark DiMarcoのJSConf 2014での講演です。アルゴリズムがどのように適用されているかを、数式でなく、映像で説明してくれているのが、とてもわかりやすいです。 Amazonのプルダウンメニューの工夫の話は聞いたことがありましたが、元をたどればAppleが発明したものだけどOS Xに移行するときに使われなくなった（コピーし忘れた？）テクニックなのですね。知りませんでした。 1) 画面
プログラマのための文書推薦入門 (社内勉強会の発表資料) - y_uti のブログ
勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基本的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。
機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
高次元データの外れ値検出 - sfchaos's blog
高次元データの外れ値検出についてのメモ． 高次元データと次元の呪い 次元が大きくなるほど，点の間の距離は均一になっていく． 例として，2000個の点の各座標を一様乱数で発生させて，次元を変えながら点の間の距離の平均値，最大値，最小値，平均値±1σ，平均値±2σをみてみよう． library(ggplot2) set.seed(123) # 次元のリスト dims <- c(1:9, 10*(1:9), 100*(1:10)) # 算出する統計量 stats <- c("min", "mean-sd", "mean", "mean+sd", "max") # 発生させる点の個数 N <- 2000 # 各次元に対して算出した統計量を格納する行列 ans <- matrix(NA, length(dims), length(stats), dimnames=list(dims, stats))
word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method
About About Department of Computer Science Department Roles Faculty Positions Visitor Information Contact Us People People Research Faculty Teaching Faculty Graduate Students & Postdocs Administrative Staff Technical Staff Research Research Areas All Research Areas Theory of Computer Science AI, Machine Learning and Data Science Computer Systems, Communication and Software Engineering Vision, Grap
AtCoder Beginner Contest 009 解説
2018/10/31 勉強会 (文字が見えない方は、ダウンロードするかフルスクリーンにしてご覧ください)
darts-clone の Java 移植 - アスペ日記
矢田さんのdarts-cloneをJavaに単純に移植したので、GitHubに上げました。 https://github.com/hiroshi-manabe/darts-clone-java darts-clone については、矢田さんの日記に詳しい解説があります。 これを移植したときは、仕事で使えるかと思ってやってみたのですが、結局そのときは容量の小ささを重視して takawitter さんのtrie4jを改造して使うことになりました。 せっかくなので置いておきます。 これはいろいろな事情があり、かなり Java 的でないものになっています。 その背景には、上記の trie4j の存在もあります。 trie4j はダブル配列も含むため、通常であればそちらを使うのが簡単でいいと思いますが、darts-clone はいろいろと変態的な工夫（1ノードあたり 4 バイトしか消費しないとか、値が
2010-03-01
Darts clone は，ダブル配列（Double-array）の有名なライブラリである Darts のクローンとして開発したライブラリです．Darts clone 0.32g は，TAIL を用いないという点が Darts と共通しているものの，ダブル配列の各要素を 4 bytes で表現したり，トライ（Trie）の代わりに Directed Acyclic Word Graph (DAWG) を採用したりという違いがあります．Darts clone と Darts の性能を比べると，辞書のサイズについては Darts clone の方が優れています．検索時間については，状況によって逆転することがあり，どちらか一方が常に優秀ということはありません． Darts Darts: Double ARray Trie System Darts clone Google Code Archive
ブロックチェーンをもう一段深く理解する - ワザノバ | wazanova
http://www.igvita.com/2014/05/05/minimum-viable-block-chain/ 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 39分前 このブログでGoogleのIlya Grigorikが言及している、 （ビットコインの）デジタル貨幣という側面より、もっと興味深く大きな意味をもつイノベーションは、その土台となっているブロックチェーンのテクノロジー。 という考え方は、いまやベイエリアの中心的な論調。ですので、ビットコインの貨幣的側面の規制を当局が検討したり、それがメディアで報じられても、まったくひるまずに、昨年後半あたりはブロックチェーン周辺のスタートアップにかなり投資がされています。 それらのスタートアップのサービスがこれから世の中に順次でてくるので、ブロックチェーン
ナップサック問題として複数文書要約を解くを試す - Negative/Positive Thinking
はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf 上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。 (論文で提案されている手法ではないことに注意) コード #include <iostream> #include <vector> #include <map> #include <sstream> class KPSummary { // T[i][k] := 文iまでで最大要約長がkのときの最適解値 // U[i][k] := 経路復元用(文iを利用したかどうか) std::vector< std::vector<int
文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った - EchizenBlog-Zwei
@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。 文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使った。 https://github.com/echizentm/GCFID 作ってみて感じたメリット・デメリットをメモしておく。 簡単に言うと、rank、selectがO(1)でないという欠点があるものの理解のしやすさ、実装のしやすさを考えると利点が大きいように感じた。 文法圧縮を用いて完備辞書を作るメリット ビット列が変換規則(X1 => X2, X3みたいなの)の集合で表現できるのでpopcountとかのややこしいビット演算が不要 ビット演算が不要なのでperl,python
協調フィルタリングについてまとめてみた。 - Analyze IT.
A Survey of Collaborative Filtering Techniques(Xiaoyuan Su and Taghi M. Khoshgoftaar, 2009,Advances in Artificial Intelligence) 仕事で協調フィルタリングについて調べる必要が出てきたのだが、あまりよい日本語の文献を見つけられなかったため（後にしましま先生の文献を見つけた）やむなく英語の論文を検索したところ、 上記のよいサーベイ論文を見つけた。というわけでこのサーベイ論文に書かれていることに自分なりに調べたことを加えて、自分用にまとめておく。 また、一部の人達の間ではとても有名なしましま先生の論文（ドラフト版）があるので、英語が苦手な人はそちらをご覧になるとよいと思われる。 協調フィルタリングは、一言で言えばユーザとアイテムのマトリックスを用いた顧客への商品のレコメン
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
配列のランダマイズ、出来ますか？（後編）
前回のエントリ、配列のランダマイズ、出来ますか？（前編）の続きです。 前回のエントリの最後では、次のようなコードを提示し、どこが問題なのかの疑問を提起しました。 // 配列の初期化 var a = []; for(var i = 0; i < 1000; i++) { a[i] = i; } function swap(s, d) { var t = a[s]; a[s] = a[d]; a[d] = t; } // ランダマイズ、その2 for(var i = 0; i < a.length; i++) { swap(i, (Math.random() * a.length) | 0); } ランダマイズのコードの厄介なところは、1回2回実行したところで問題がわからない点で、このプログラムもぱっと見た感じではきちんとランダマイズされているように見えます。ではどうやって問題があるかを判断す
配列のランダマイズ、出来ますか？（前編）
先日、When Random Isn't Random Enough: Lessons from an Online Poker Exploit（英文注意）という記事がタイムラインに流れてきて、同僚と少し配列ランダマイズの話になったので備忘録として書いておきます。 配列のランダマイズというのは、たとえば上の記事にあるようなトランプのシャッフルであるとか、音楽プレイヤーの再生リストのランダム再生とかで実装しますね。ゲームを作るときなどには実装することが多いでしょうが、記事を読む前に、自分だったらどのように実装するか是非少し考えてみてください。 自分が中学生の頃に書いた記憶のあるコードは、たしか次のようなものでした。 // 配列の初期化 var a = []; for(var i = 0; i < 1000; i++) { a[i] = i; } function swap(s, d) { v
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
2013年度の文法圧縮の進展 - Yasuo Tabeiの日記
年が明けて2014年の１月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には２つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://spheresofa.net/blog/?p=1044