Consistent Hashing を試す
Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
オンライン分類器の比較 - Qiita
動機 前回書いた通り、会社内にデータは全く貯められていない状態です。ですが、将来ログをまともに取得した場合のデータは膨大になることが想定されました。そこで、（時間/空間）計算量を考慮するとオンライン学習アルゴリズムを使うのが最良と判断しました。 （以前のpostも想定しての話を書いています。いろんな意味で残念ですね...orz） 今までオンライン分類器をまともに使った事がなかったため、性能評価も兼ねていくつかの分類器を試してみたというわけです（随分前にですが...）。 オンライン分類器の概要 線形分類器は大体 $w^*:=argmin_wΣ_iL(x^{(i)},y^{(i)},w)+CR(w)$ $L(x^{(i)},y^{(i)},w)$：ロス関数, $R(w)$：正規化項 で表すことができると思います。 オンライン学習では、「データを1つ受け取るたびに逐次的にウェイトを更新する」とい
Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
【オンライン機械学習】 Go で PA, CW, AROW, SCW を書いてみた |
Perceptron (Rosenblatt, 1958) を1年半前に書いてから, だいぶ時間が経ってしまいましたが, 今回はその続きで Go で PA, PA-I, PA-II, CW, AROW, SCW-I, SCW-II を書いてみたのでメモリます。 PA, CW, AROW, SCWの総まとめ的な論文 Exact Soft Confidence-Weighted Learning にアルゴリズムがまとまっています。 PA (Passive-Aggressive) PA (Crammer et al., 2006) [1] は, 損失関数にSVMでも使われているヒンジ損失を用いる。 最適化問題は, ヒンジ損失が 0 となる制約の元でこれまでに得られている重みに近い重みを選択する。ただし, ヒンジ損失が 0 となる制約は強く, 急に重みが変動してしまうので, PA-Iでは罰則項を線
軽量ハッシュアルゴリズム - Qiita
今回はハッシュアルゴリズムについて少し触れてみたいと思います。 既存のハッシュアルゴリズムはどういうものがあるでしょうか？ SHA-1, MD5等が浮かんだ方も多いと思います。 「じゃあそれでいいじゃん」 ・・・ちょっと待ってください。 SHA-1, MD5というものは、暗号化のためのハッシュアルゴリズムです。 もし用途が単純なファイル比較等であれば、ここまで大げさなハッシュは冗長で高負荷低速であると言えます。 適切なアルゴリズムは状況によって適切に選びたいところです。 そこで今回は単純なファイル比較等に使用できる、簡単＆軽量なハッシュアルゴリズムの FNV-1 というアルゴリズムを紹介します。 詳細はこちらへどうぞ http://wowdev.jp/?p=873 ソースはこちらです。 # include <stdio.h> # include <stdint.h> /** * FNV C
アルゴリズム — Jubatus
Overview¶ 回帰問題は，入力 \(x\) に対応する特徴ベクトル \(\phi(x) \in R^m\) に対して，実数値の出力 \(y \in R\) を当てる問題である． 今回実装したのは，線形回帰モデルである． 線形回帰モデルでは，パラメータ \(w \in R^m\) を利用して，入力 \(x\) に対して \(\hat{y} = w^T \phi(x) \in R\) で予測する． 学習時には，分類問題同様，正解データセット \(\{(x_i, y_i)\}\) を利用して，正解データに対して正しく予測できるように重みベクトルを推定する． 典型的には1800年代に，予測値と実測値との自乗和を最小化させる最小二乗法が提案されている． この方法はバッチ処理になるため，今回の調査ではオンライン学習させる方法を利用した． Passive Aggressive¶ Passive A
Paxos
PostgreSQLをKubernetes上で活用するためのOperator紹介！（Cloud Native Database Meetup #3 発表資料）
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Expected behavior for updates between MIX · Issue #840 · jubatus/jubatus