レコメンドアルゴリズム入門：基礎から応用まで実装に必要な知識を解説 - Qiita
1: 購入 0: 閲覧(したが購入してない) -: 未観測 ユーザーベース型 ユーザー同士の類似度を計算 「あなたと購入履歴の似たユーザーはこんな商品を買っています」 行を各ユーザーのベクトルとみなして、似たユーザーを見つける（上位N人） 似たユーザーが購入しているアイテムを推薦する（N人の平均値などで購入しそうな順に提示） アイテムベース型 アイテム同士の類似度を計算 「この商品を買ったユーザーはこんな商品も買ってます」 列を各アイテムのベクトルとみなして、類似度の高いアイテムを推薦する（上位M件） 類似度計算には、コサイン類似度やJaccard類似度が使われる。 類似度を計算する際に、未観測「-」は適当な値（0, 0.5など）で埋めるか、無視をする。 ログデータを使うため、情報の少ない新規アイテム/新規ユーザーに弱いコールドスタート問題がある。 コンテンツベースフィルタリング アイテム
『Winny』の金子勇さんの失われたED法を求めて - Qiita
普段は「通知が迷惑かなー」と思ってブックマークしていただいている方に通知せず記事を編集しているのですが、この記事をブクマしていただいている方は続きが気になっている方だと思いますので通知させていただきます。 結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです！ 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何
グリコレーティング - Wikipedia
グリコレーティング (Glicko rating) は、チェスや囲碁のようなゲームにおいてプレイヤーの強さを評価（レーティング）するためのアルゴリズムである。マーク・グリックマンによりイロレーティングを改善するべく発明されたもので、当初はチェスのランキングに用いることが意図されていた。レーティングの定義や基準はイロレーティングと同様である。グリコレーティングの最大の特徴は、レーティング計算時にレーティング偏差 (ratings deviation, RD) と呼ばれるレーティングの信頼性を図る手法が導入されたことである。 グリコレーティング並びに後述のグリコ2レーティングはパブリックドメインとして公開されており、多くのオンライン上のゲームサーバーにおいて用いられている（例、Lichess, Free Internet Chess Server, Chess.com, Counter-Str
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
DeepMind、AIで人間考案のものより優秀なソートアルゴリズムを発見 最大70％高速化
米Google傘下のAI企業Google DeepMindは6月7日（現地時間）、アルゴリズムを開発するAI「AlphaDev」が、人間が考えたものより高速なソートアルゴリズムを発見したと発表した。 ソートアルゴリズムは、入力されたデータを一定のルールに基づいて並べ替えるもの。ネット検索結果の並べ替えやランキング制作などIT技術の根幹を担う技術の一つ。今回AlphaDevが考案したアルゴリズムは既存のものに比べて、少量のデータなら最大70％、数十万規模の大量のデータなら約1.7％速く処理できた。 DeepMindはAlphaDevに新しいアルゴリズムを発見させるため、ソートの作業を「組み立てゲーム」としてプレイさせた。「正確にソートできる」「既存のアルゴリズムより高速である」という2点を満たせばクリアとした。 関連記事 OpenAIやDeepMindのCEOやトップ研究者ら、「AIによる人
レーベンシュタイン距離 - Wikipedia
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 実際的な距離の求め方を例示すれば、「kitten」を「s
ランダムを楽しもう / Algorithm with Randomness
本スライドでは、以下の２つの内容を紹介します。 １．乱択アルゴリズム（乱数を使って問題を解くアルゴリズム） ２．ランダムな入力に対するアルゴリズム
高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
分散合意アルゴリズム Raft を理解する - Qiita
Raft は Byzantine 障害に対する耐性がなく、論文を一見して恒久的なリーダーの乗っ取りからのログの改ざん、リーダー選挙の妨害などが可能であるところを見ても、P2P ではなく完全に管理されたネットワーク向けの合意アルゴリズム (CFT; Crash Fault-Tolerance) です。Byzantine 障害耐性が必要であれば Raft ではなくパフォーマンスを犠牲にして pBFT などを使う必要があるでしょう。 論文では Crash-Recovery より深刻な障害耐性には言及していないが (論説の範囲を外れるため当然だが)、もし実際に Raft を実装するなら現実的に想定される障害に対して工夫できる余地もいくつか存在します。例えば「テスト環境で使用していたノードの 1 つが事故で本番クラスタに『も』参加してしまった」といったような運用事故で起きうる障害は (大抵そのような
アルゴリズム1000本ノック #3. Longest common subsequence - Qiita
文字列S1とS2の最長共通部分を求めよ. 最長共通部分とは, S1とS2の要素から順番を保ったまま任意の数の文字を選択した場合に 同一となる文字列のうち, 最長のものを指す. たとえば, "1224533324" と "69283746" の最長共通部分は "234"である. Solution これも有名なDPの問題の1つです. 個人的にはめちゃくちゃ難しいと思います…. Longest Common Substringと似ていますが, 必ずしも要素同士は隣り合っている必要がないという点が異なります. 問題の例について考えてみます. 与えられた２つの文字列を縦と横に置いて, 下の図のようなテーブルを考えます. 例えばオレンジ色のセル Table[4][2] は S1.subString(0, 5) = "12245" と S2.subString(0, 3) = "692"の最長共通部分の
【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とは - ミエルカAI は、自然言語処理技術を中心とした、RPA開発・サイト改善・流入改
ミエルカAI TOP > メディア > 技術解説 > 自然言語処理 > 【技術解説】似ている文字列がわかる！レーベンシュタイン距離とジャロ・ウィンクラー距離の計算方法とは 執筆：金子冴 人はだれしも間違いを犯すものである．徹夜で仕上げた報告書を提出した後，よく見直してみると誤字脱字が山ほど見つかった経験が読者にもあるだろう(もしかすると私だけかもしれないが)．そういう時，もし自動で間違っている単語を見つけてくれるプログラムがあったら…と考える人もいるかもしれない．そこで今回は，文字列同士の似ている度合いを計算する2つの手法を紹介しよう． ●レーベンシュタイン距離(Levenshtein Distance) ●ジャロ・ウィンクラー距離(Jaro-winkler Distance) 目次 文字列の類似度，距離 編集処理(挿入，削除，置換) レーベンシュタイン距離(Levenshtein Dis
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
プルーフ・オブ・ステーク - Wikipedia
プルーフ・オブ・ステーク（Proof-of-stake、PoS）は暗号通貨のブロックチェーンネットワークによる分散型コンセンサスの達成を目的とするアルゴリズムの一種。PoSベースの暗号通貨では次のブロックの作成者はランダム選択と資産または年齢（例：ステーク〈掛け金〉）の様々な組み合わせを通して選ばれる。対照的にプルーフ・オブ・ワーク（PoW）ベースの暗号通貨（ビットコインなど）のアルゴリズムはトランザクションの検証と新たなブロックを作成（例：マイニング）するために複雑な暗号パズルを解読した参加者に報酬を与える。 ブロック選択方法の種類[編集] プルーフ・オブ・ステークはブロックチェーンの次の有効なブロックを定義する方法が必要となる。アカウント残高による選択は最もリッチなメンバー1人が恒久的なアドバンテージを得ることから、望ましくない集権化をもたらす。その代わりにいくつかの異なる選択方法が考
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
確率的データ構造を使って巨大な集合を定数メモリで近似しよう
巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。 本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。
Diffie-Hellman鍵交換入門 - Qiita
鍵交換とは 例えば、zipを作成するときにはパスワードを設定しますね。これは、zip作成者がパスワードを知っている人だけが中身を読めるようにするためのものです。 我々がふだん使っているセキュアな通信(TLS, SSHなど)は、送信側と受信側が同じ「鍵」を共有することで行います。実際には鍵は一定の長さのビット列(256ビットがよくありますが、暗号アルゴリズムとその設定でまちまちです)なのですが、送信者と受信者だけが鍵を知っていて、他の人は知らないというのがポイントです。 では、通信を開始するとき、送信者と受信者はどのように鍵を取り決めるのでしょうか？ 通信を傍受している悪者がいたとすると、「これからこの鍵で暗号化して通信するよー！」と鍵をそのままネットワークに流しては鍵が悪者にばれてしまい、その後の通信も盗み見ることができてしまいます。しかし通信開始時には暗号化された通信経路は存在しないので
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Pairwise summation - Wikipedia