motacaplaのめう

日頃得られた知見と気付きをdumpするところ

分散合意プロトコル(Distributed Consensus Protocol)についてまとめてみる 第1章 概要と背景知識について

この記事は何?

分散環境下において合意を取るためのプロトコルがいくつか存在するので、それらを簡単にまとめることとする。

※分散システムの勉強を兼ねて書いておりますので、間違い等ありましたらご指摘頂けると幸いです。

利用用途

分散合意プロトコルは、以下のようなシチュエーションで使われている:

  • リーダ選出 (Leader election)

例. master-slaveモデルの分散システムにおいてmasterがダウンした際に、master eligible nodesから次なるmasterを選出する

  • ログ複製の管理 (Replicated state machine)

例. masterが正しいログを保持し、複製を他のnodesに配る

そもそも合意って何?

"The distributed consensus problem deals with reaching agreement among a group of processes connected by an unreliable communications network"

プロセス系全体として一つの値を決定すること、だと解釈している。

例えば5人の人間A,B,C,D,Eが存在し、お昼ご飯について合意を取るとする。

A,B,Cがラーメンを食べる、Dがカレーを食べる、Eが寿司を食べるとなった時、多数決を取り「ラーメンを食べる」で系として合意を得るイメージ?

分散合意プロトコルの話に入る前に、前提となる背景知識について述べる。

背景知識

Byzantine Generals Problem (1982)

Byzantine Generals Problem(ビザンチン将軍問題)は "相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題" である。 (Wikipediaより)

例え話として、通信など無縁な時代において、小国A, B, C, D, Eの軍隊らが協力し、大国Fを攻めようと画策している状況を考える。

当然A-E単独で攻め込んだところで返り討ちに合うことは目に見えているため、協力して大国Fを攻め落とそうという話になった。

しかし、A-Eは地理的に離れているため、協力するためには攻撃の日を "合意" することで決定する必要がある。

ある小国ともう一方の小国における "通信" 手段は連絡兵を送り合うことのみであるが、小国間には危険な地域があるため、連絡兵がもう一方の小国へ無事に辿り着けない可能性がある。

さらには、A-Eのどれかの国が裏切りを図る可能性もある。

このような状況下でA-E全体として正しい合意を得られるか?を問う問題である。

同期システムの場合、特に弱ビザンチン将軍問題において 3t < n (n: ノード数, t: 障害数) であれば、合意をとることができる (逆にいうと the oral-messages model において3t ≧ n の場合に解決できないことが示されている)

the oral-messages modelは以下参照。

www.blockchainengineer.tokyo

一方、非同期システムの場合、障害が発生した場合において有限時間内に合意を取る方法はない https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf ということがMichael J. Fischer, Nancy Lynch, and Mike Patersonらによって示されている。これをFLP impossibilityと呼び、後述する。

ビザンチン将軍問題 - Wikipedia

Two general's Problem

Byzantine Generals ProblemはTwo General's Problemを一般化したものである。

つまり、例え話のA-EがA,Bの2つになった問題と解釈してよい。(雑)

FLP impossibility (1985)

Byzantine Generals Problemで触れたFLP impossibilityの話。

非同期システムにおける分散合意の不可能性を説いた論文で、要約すると、

"どのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。"

つまり「落ちたか遅延しているかが不明なプロセスが発生した場合、有限時間内で合意に至るアルゴリズムはない」 とのこと。 (論文はまた後日読む)

※ただし前提条件として、故障検知が不可・プログラムが決定的を仮定している。

ちなみに同期システムにおける同問題はByzantine Generals Problemで、合意を取る方法は既にある。

A Brief Tour of FLP Impossibility

論文翻訳: Impossibility of Distributed Consensus with One Faulty Process - MOXBOX / HazMat

分散合意プロトコル

ここでは分散合意プロトコルの種類についてのみ述べる。

個々の内容に関しては非常にボリュームがあるため、次回以降まとめることとする。

  • 2相コミット(2 Phase-Commit, 2PC)

PrepareフェーズとCommitフェーズという2段階のフェーズに分かれてトランザクションを実施する。

ブロッキングプロトコル

2相コミット - Wikipedia

  • 3相コミット(3 Phase-Commit, 3PC)

Voteフェーズ、Prepareフェーズ、Commitフェーズという3段階のフェーズに分かれてトランザクションを実施する。

ノンブロッキングプロトコル

3相コミット - Wikipedia

  • Paxos

今日の様々な分散システムの合意をとるために使われているプロトコル

亜種が非常に多い、難しいことで有名?

Paxosの派生は沢山ある (というか元々のものを忠実に再現することが難しい) らしく、例えばChubbyやApache Zookeeper で採用されている(Zab)は派生の一例である。

  • Raft

Diego Ongaro et al.,によって提案されたプロトコル

Paxosよりも学習者にとって分かりやすいという点を売りにしている。

Paxosよりも制約が多いが、実用上は問題ないとのこと。

特徴として、強力なリーダ選出がある。

  • Viewstamped Replication

Paxosに非常に似た手法らしい、あまり情報がなかったので論文を読みたい。

  • Mencius

あんまり情報出てこなかった...

それぞれReferencesに参考文献を載せた

(余談) ブロックチェーン?

  • Practical Byzantine Fault Tolerance (PBFT)
  • Proof of Work (PoW) <- Bitcoinで使われてるやつ
  • Proof of Stake (PoS)

次回

2PCからまとめていきます〜!

References

全般

sharply.hatenablog.com

https://www.usenix.org/sites/default/files/conference/protected-files/srecon15europe_slides_nolan.pdf

分散システムの限界について知ろう

Paxos

今度こそ絶対あなたに理解させるPaxos - Qiita

ざっくり理解するPaxos - 小野マトペの納豆ペペロンチーノ日記

Paxos, Raftなど分散合意プロトコルを概観する(1) - 備忘録 blog

Raft

Raft Consensus Algorithm

Raft(分散合意アルゴリズム)について · GitHub

Raft 論文抄訳 - kandamotohiro

Viewstamped Replication

Viewstamped Replication

Mencius

Mencius: Building Efficient Replicated State Machines for WANs

ABC130に参加して冷えた話

はじめに

更新をサボり気味なので、これから毎週コンテスト後の感想を綴っていこうと思います。

2完しか出来ずに氷河期を迎えた(茶パフォ)、前回稼いだレートは消えました。

Contest Result - AtCoder

A問題

お決まりのif文知ってますか問題、変数の名前は問題のと異なってます

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n,x;
  string s;
  cin >> n >> x;

  if(n < x) cout << 0 << endl;
  else cout << 10 << endl;  
  
  return 0;
}

B問題

累積和作れば良かったのだと思うのですけど、n番目を考慮漏れして1WAしてしまった

深く考えずにvectorへ突っ込んだ後、上記に気づいてAC

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n,x;
  string s;
  cin >> n >> x;
  vector<ll> L(n+1);
  vector<ll> D(n+1);
  REP(i, n) cin >> L[i];
  ll cnt = 1;
  D[0] = 0;
  vector<ll> vec;
  FOR(i,1,n+1) {
    D[i] = D[i-1] + L[i-1];
    vec.push_back(D[i]);
  }
  sort(vec.begin(), vec.end());

  for(auto &e: vec){
    if(e <= x){
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

C問題

何故か問題を読んだ時から格子状での解法を考えていた。。。

よくよく考えると線の傾きに制限はないので、四角形の中心を通る切り方が最適であると分かる

よって、座標(x, y)が中心に与えられた場合は切り方として無限パターン存在する

その他の場合は1パターンしかない

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  ll w, h, x, y;
  cin >> w >> h >> x >> y;
  
  cout << fixed << setprecision(20);
  cout << double(w) * double(h) /2 << " " << (x+x == w && y+y == h) << endl;
  //所与の点が中心である ... (w/2, h/2) = (x, y)
  
  return 0;
}

D問題

解法は合っていたが、TLEして終了した

原因は個数を数える際にleft = 0を代入して、逐一計算していたこと

あと途中まで単調増加か否かを無視してしゃくとり法走ってたのも良くなかった...

sumがkの値を以上ならば以降の(n-r+1)の要素についても sum >= kが成立するため、これをansに足し合わせる方針で解けば良い

↑自分の考えと逆の足し方だったので、ちゃんと覚える

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];

  ll ans = 0LL, sum = 0LL;

  int r = 0;
  REP(l, n){
    while(sum < k){
      if(r == n) break;
      else{
    sum += a[r];
    r++;
      }      
    }
    if(sum < k) break;
    ans += n-r+1;
    sum -= a[l];
  }

  cout << ans << endl;
  
  return 0;
}

E以降

解いてないので、また今度やります

所感

くっそ冷えて萎えましたが、最近精進できてなかったので致し方ないです

なので今週は、しゃくとり法をそらで高速に書けるよう精進します!

覚えること: 「〜以降は条件を満たす」場合は、後ろから差分を引いてansに加える

忙しい人のためのRedisチュートリアル

この記事は何?

RedisConf19参加にあたり, Redisのdocsをしっかり読み込んだことがなかったため実施した. 量が多いため, 途中から要約だけ載せる.(疲れたので)

https://redis.io/

なお, 現時点でのlatest stableはRedis v5.0.4である.

commands

データ型はstring, bit, hash, list, set, sorted set, hyperloglog, streamと多種揃っている. 呼び出せるコマンドについては全てココにあるため, 今回は割愛する. 日本語のドキュメントだと, v2.0.3までの関数は以下にある. コマンドリファレンス — redis 2.0.3 documentation

stream type

v5.0.0から stream型エントリ のデータ管理方法が実装された. stream型は名前のとおり, 時系列データを扱うためのデータ型である. XADDやXRANGE, XDEL, XTRIMといった先頭にXのつくコマンドがstream用のコマンドとなっている. 例. XADDのdoc XADD – Redis

例えばXADDは, 同一keyに対して複数valuesを与える形で記述できる.

redis> XADD mystream * name Sara surname OConnor
"1553778517432-0"
redis> XRANGE mystream - +
1) 1) "1553778517432-0"
   2) 1) "name"
      2) "Sara"
      3) "surname"
      4) "OConnor"
redis> XADD mystream * field1 value1 field2 value2 field3 value3
redis> XRANGE mystream - +
1) 1) "1553778517432-0"
   2) 1) "name"
      2) "Sara"
      3) "surname"
      4) "OConnor"
2) 1) "1553778517433-0"
   2) 1) "field1"
      2) "value1"
      3) "field2"
      4) "value2"
      5) "field3"
      6) "value3"

value登録時に発行される文字列をstream IDと呼ぶ. 例えば上記の例では"1553778517432-0"が該当する. ご覧の通り, stream IDは[unix msecのタイムスタンプ]-[シーケンス番号]と構成される.

以下参考.

qiita.com qiita.com streamのintroduction (とは思えない程の分量と内容) Redis Pub/Subを先に読むことを推奨 Introduction to Redis Streams – Redis

Pipelining

https://redis.io/topics/pipelining

TL;DR

ClientがRequestを発行してからServerがResponseし, Clientへ結果が戻るまでの時間をRoundTripTimeと呼ぶ. Server側がRequestを受信する度にResponseを返すのではなく, まとめて返事することで(server側の)system callsの実行回数が減り, レイテンシ低減する. それだけでなく, 時間辺りに実行できるクエリ数も増加する. できるだけpipeliningを使おう!←結論

Pub/Sub

https://redis.io/topics/pubsub

Apache Kafkaとか有名なやつ, メッセージングパターン.

TL;DR

例えばclientがsubscribeしたいとする. この時, clientはチャンネルをSUBSCRIBEコマンドで指定する. そしてチャンネルにpushされたメッセージは, それをsubscribeしている全clientに送信される. pushするにはPUBLISHコマンドを用いる. チャンネルのsubscribeをやめる場合は, UNSUBSCRIBEコマンドを用いる. Redis Pub/SubはパターンマッチングによるPub/Sub機能もある. それぞれPSUBSCRIBE, PUNSUBSCRIBEを使う. Pub/Sub subsystemの状態を見たい場合はPUBSUBコマンドを叩く.

以下参考.

Redisのpub/sub機能 - Qiita

Lua scripting

https://redis.io/commands/eval Luaスクリプトを実行できるよ!

> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 first second
1) "key1"
2) "key2"
3) "first"
4) "second"

RedisとLuaの相互型変換は可能らしい. ただし, 浮動小数で返してほしい場合はLua側が文字列として返す必要あり.

If you want to return a float from Lua you should return it as a string

あとSHA-1ハッシュ関数を使うEVALSHAコマンドもある.

transactions

トランザクションもあるよ. https://redis.io/topics/transactions

トランザクション — Redis Documentation (Japanese Translation)

トランザクション自体の説明は以下参考.

データベースさわったこと無い新人向けトランザクション入門 - Qiita

TL;DR

主にMULTI, EXEC, DISCARD, WATCHコマンドを使う.

> MULTI
OK
> INCR foo
QUEUED
> INCR bar
QUEUED
> EXEC
1) (integer) 1
2) (integer) 1

特徴として, コマンドがミスっていても, 実行可能なものは処理されてしまうという点には気をつけたい.

even when a command fails, all the other commands in the queue are processed

Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
MULTI
+OK
SET a 3
abc
+QUEUED
LPOP a
+QUEUED
EXEC
*2
+OK
-ERR Operation against a key holding the wrong kind of value

ロールバックはサポートされていない. 理由は - シンタックスが間違ってるときしか失敗しないから - ロールバックしなくても問題ないぐらい速い (もう一度実行しろってことかな)

DISCARDコマンドでトランザクションのabortが可能

> SET foo 1
OK
> MULTI
OK
> INCR foo
QUEUED
> DISCARD
OK
> GET foo
"1"

WATCHコマンドを使うと, 楽観的なロックが実現できる. WATCHコマンドは check-and-set の振る舞いを提供する. つまりWATCHコマンドで監視しているkeyに変更が加わった場合, トランザクション全体を中止する.

persistence

Redis Persistence – Redis

Redisでは大きく2つの永続化オプションがある もちろん使わないことも可能だし, 片方だけ使うこともできるし, 組み合わせて使うことも可能. 求める永続化の性能に依存.

  • RDB: 指定時刻ごとにデータセットのスナップショットを取得する. もしくはコマンドを叩いて取得する. スナップショットはバックアップとしては完璧だが, redisに障害発生時のデータ損失可能性はそこまで低く出来ない.

  • AOF(= Append only log): 実行されたコマンドをログとして残す. 耐障害性はRDBより高いが, ファイルサイズが大きくなりがち.

Memory optimization

Redisをメモリ効率よく使うためのTips, まだ執筆途中とのこと. https://redis.io/topics/memory-optimization

TL;DR

メモリ効率の良いhashをできるだけ使いましょう

だいぶ端折りましたが, 疲れたので残りは次回!

ABC118 に参加した話

問題

下記リンク

atcoder.jp

解答

A問題

  cin >> a >> b;
  if(b%a == 0) cout << a+b << endl;
  else cout << b-a << endl;

B問題

mapに挿入、n個あるものをカウントして出力

int k[31], a[31][31];
map<int, int> mp;

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  string s;

  cin >> n >> m;
  REP(i, n){
    cin >> k[i];
    REP(j, k[i]){
      int tmp;
      cin >> tmp;
      mp[tmp]++;
    }
  }
  int cnt = 0;
  for(auto itr = mp.begin(); itr!=mp.end(); itr++){
    if(itr->second == n) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

C問題

A_iの中から小さい数を取り出してmodをとる これを繰り返し、できなくなったら終了 最小値を出力

const int INF = 1e9;
int n;
ll a[100100];

int mini = INF;

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  REP(i,n) {
    cin >> a[i];
    if(a[i] < mini) mini = a[i];    
  }
  bool f = true;
  while(f){
    int tmp = mini;
    int cnt = 0;
    REP(i, n) {
      if(a[i]%mini != 0){
    a[i] %= mini;
      }
      else{
    cnt++;
      }
    }
    if(cnt == n) break;
    REP(i, n) mini = min((int)a[i], mini);
  }
  cout << mini << endl;
  return 0;
}

D問題

(時間内に解けなかった) 考えたことは、DPで解けそう→dp[i][j]で長さ最大の文字数を入れればいけそう→経路の復元方法が分からない→貪欲 という流れで貪欲を書いたが、RE

正解は、string型の一次元DPに文字列ごと保持する 文字列長が最大となるものを管理しつつ、長さが同じ場合は辞書順比較で小さいものを常に管理する (他の方のコードを参考にさせていただきました)

//解説AC
//https://atcoder.jp/contests/abc118/submissions/4292391

int num[]={0,2,5,5,4,5,6,3,7,6};
int a[10];
int n,m;

void cng(string &t, string p){
  if(t=="0") t=p;
  else if(t.size() < p.size())t=p;
  else if(t.size() == p.size()){
    if(t<p) t=p;
  }
}

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  REP(i,m) cin >> a[i];

  string dp[100100];

  REP(i, n+1) dp[i] = "0";

  dp[0] = "";
  REP(i, n+1){
    if(dp[i] == "0") continue;
    REP(j, m){
      cng(dp[i+num[a[j]]], dp[i]+(char)(a[j]+'0'));
    }
  }
  cout<<dp[n]<<endl;
}

感想

D問題、解けない問題ではないので、頑張って解きたかった... 引き続き精進します

学んだこと

- 文字列の辞書順比較はoperator >, <で可能

例えば '9' > '11' はtrueになる

- (char)(a[j]+'0')でint->char変換

ABC097 D Equals を解いた話

最近更新できていないので、競プロネタを投稿。

下記の問題を解説ACした。 D - Equals

問題

整数x [1, N]を適当に並び替えた順列p_1, p_2, ..., p_NとM個の整数ペア(x_1, y_2), ..., (x_M, y_M)が与えられる。
与えられた整数ペアを用いて、 swap(p_x, p_y)を何度でも行えるとする。
操作後にp_i = i となる数の最大数を求めよ。


要はインデックス通りに並べられることが可能な数字の最大の数を求める?ということ。
自力ではACできずにUnionFindの解法を参考にした。

www.slideshare.net

素集合データ構造で、同じグループに属す(Union)操作と同じグループかを探す(Find)操作を行うものである。
素集合というのは、ある要素が複数の集合に含まれないものを指すらしい。

コードはこんな感じになった。
x,yの配列いらないしメモリ無駄にしてるけど、とりあえずこれで提出してAC:

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
using ll = long long;

template <typename T>
class UnionFind {
public:
  T n;
  vector <T> d;
  UnionFind(T n) :d(n, -1) {} 
  int find(T x){
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(T x, T y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(size(x) < size(y)) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  int size(T v){ return -d[find(v)];}
  bool same(T x, T y){
    return find(x) == find(y);
  }
};

int p[1000000], x[1000000], y[1000000];

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  REP(i, n) cin >> p[i];
  REP(i, m) cin >> x[i] >> y[i];

  UnionFind<int> uf = UnionFind<int>(n+1);

  REP(i, m) uf.unite(x[i], y[i]);

  ll ans = 0LL;

  REP(i, n) if(uf.same(i+1, p[i])) ans++; 

  cout << ans << endl;
  
  //if(uf.unite(x[0], y[0])) cout << "success" << endl;
  //cout << uf.size(5) << endl;;
  
  return 0;
}

モバイルコンピューティング関連の論文をいくつか読んだのでメモを書き下す

Geofenceとは

地理空間上に仮想的なフェンスを設け、ある移動体がフェンス外→内もしくは内→外へと移動することを検知する技術。 Location-based Service(LBS)と組み合わせることで色々なサービスを提供できる。 例えば、「子供やお年寄りが指定された場所から出ないように見守る」「お店の割引クーポンを近くの人に配信する」といったものが挙げられる。
Geo-fence - Wikipediahttps://en.wikipedia.org/wiki/Geo-fenceen.wikipedia.org
これに関する論文を6つほど読んだので、簡単にまとめることとする。

所感

Geofenceと名の付く殆どの論文は、ユビキタスコンピューティングやモバイルコンピューティングらに分類されるものが多い。 もう少しコアな部分でいうと計算機幾何学のpoint in polygonアルゴリズムや移動体のフェンス内外判定を高速に行うアルゴリズムの提案といった論文などはGeofenceと非常に関係が深いと思われるが、これらは当然Geofenceと名のついた論文ではあまり使われない。コアなアルゴリズム部分がGeofenceの性能を支える役割を担う一方で、モバイルコンピューティング系の論文ではこういったコアな部分の検討があまりなされていないように感じる。主に論文の著者らは電力消費量と位置情報の精度にのみ関心を持っているように感じた。

論文

1. Specification and Evaluation of Geofence Boundary Violation Detection Algorithms

論文

解いている問題

穴あき矩形のGeofence

どういう課題

既存手法には2つの課題がある

  1. 厳密な判定が不要な場合、非常に遅いためリアルタイム性を満たせない可能性有 既存のRay Castingは、各頂点のバッファにおける対象点の存在判定を行うため、頂点数に対して線形に時間計算量が増大 この対象点のバッファ領域の存在判定処理が特に重くて、ボトルネックとなっている

  2. 矩形が変化する度に、三角形分割の計算し直しが発生 Triangle Weighed Characterization (TWC) は、事前に初期化フェーズ処理として、矩形を三角形に分割する処理が必要 -> 三角形の数つまり頂点数に対して線形に時間計算量が増大 一方で、三角形の内外判定は式を解くだけであるためO(1)、三角形の数は穴あきの数次第であるが、頂点数が膨大になればなるほどRay Castingより高速と考えられる

解決方法

新しいアルゴリズムの提案 Fast Ray Casting

内容

Ray Castingの厳密なGeofence境界チェック処理を除くことで、高速化 利点は2つ 頂点数が増大した場合において、TWCよりも高速 Fast Ray CastingはTWCで必要な初期化フェーズが不要 欠点は1つ 浮動小数丸め誤差による境界線判定に誤差が発生

課題

Fast Ray Castingでは、丸め誤差を考慮していない

Future work

TWCにバッファをもたせる TWCを使ったUASの飛行経路の計画アルゴリズム開発

2. Crowd Geofencing

群衆の動向に基づいたCrowd Geofencing。分野: ユビキタス、モバイルコンピューティング (アプリケーションの話)

解いている問題

監視される対象は1人だが、監視する側が多数いるようなシチュエーションを想定 Crowd-to-Expert(C2E)シナリオにおけるGeofence

Expert-to-Crowdは、専門家の観光TIPSを、近くの全旅行者にお届けする
Crowd-to-Expertは、地元の知識や要望を環境の研究者やその分野の専門家に伝える

この論文でいうGeofenceは、例えば旅行案内版みたいなのを、専門家「1人」がGeofenceを自前で作って、「多数の」旅行者に伝えるのではなく、地元の人や精通した旅行者といった、専門家でない「多数の」人ら(Crowdworker)がGeofenceを各々で作り、それをツアー案内人「1人」に伝える。というイメージ。

ケーススタディ: バンコクの都市の水と空気の綺麗さを調査。
この研究者の持つモバイルの位置情報を元に、円形のGeofenceを設ける。 -> 円形のGeofenceを1k個ほど作成

どういう課題

専門家は、事前にどの地域の水・空気が汚染されているかの情報を知らないため、汚染されていそうな地域を逐一訪れて調査を行わなければならない。非効率的・時間がかかる。

解決方法

Crowdの人たちがGeofence領域を定義して、mobile専門家をサポートするCrowd Geofencing 手法を提案。
研究者はアプリを介して関連する情報をタイミングよくうけとり、より効率的にフィールドワークできる。

手法の課題

C2Eシナリオは専門家や、対象の場所を訪れたボランティアのスキルに依存。
生成されたGeofences全てを活用できていない (一部だけ用いてマップを生成している)

理由は2つ:
1. 重複したコメントを考慮してGeofencesの数を間引くことが、現状できていない 2. 現在の実装では、専門家の位置情報と、各Geofencesの内外判定を行うので、バッテリーの消費が激しい

内容

https://ci.nii.ac.jp/naid/110008899957

3. Geofence Index: A Performance Estimator for the Reliability of Proactive Location-based Services

技術や環境要因が、proactive LBSの確実性に与える影響、について議論
Geofenceに入った時に、location-dependent actionが起こる確率についての推定器を導入

proactive LBS : Push-based LBSのこと。ユーザがアプリを起動したりしなくとも、勝手にサービスがトリガされる位置情報ベースのサービス。
reactive <-> proactive

どういう世界か

現実に即した世界を想定している。
位置情報は、毎時刻で必ず取れるものではない(電力消費の問題があるため)
位置情報は「確実性」というバロメータがあり、必ず正しい位置を取得できるものではない(技術・環境要因が存在)
この「確実性」を高水準にするため、IT専門家がこれらの要因を考慮したGeofenceを設計する必要がある
Geofencesは、人間だけでなくセンサでも定義可能
Geofencesは、不特定多数の人・センサによって定義され、登録される
ユーザ(興味のある対象)の移動速度は一定
ユーザは任意の形のGeofenceを任意の場所に配置できる

どういう課題

trade off energy consumption against reliability…
現状では電力消費量を抑えるため、モバイル端末上のGeofencingでは以下のような問題点が存在

ある時刻に利用できるGeofencesの数が限定的
円形のGeofenceしか利用できない
Geofencesの集合と位置のマッチングを測るためのCPU時間を減らすため
そのため、高水準の確実性を担保するためには、IT専門家による全ての影響要因を考慮した設定が必要となっている

「確実性」はF値の指標で評価される
TP: モバイル端末がGeofenceに入る -> proactive LBSがアクションを起こす
FN: モバイル端末がGeofenceに入る -> proactive LBSがアクションを起こさない
FP: モバイル端末がGeofenceに入っていない -> proactive LBSがアクションを起こす

以下の再現率で評価 (実際にtrue/trueと予測 の割合)
P = TP / (TP + FN)

このTPとFNを決めるためには、領域の専門家が、全Geofencesに対してフィールドテストかシミュレーションをしなければならない

解決方法

新しいGeofenceが生成されるごとにフィールドテストやシミュレーションをするのは非現実的なので、P(g)を解析的に決定したい
そのためGeofence indexを解析的に求める

Geofence indexを解析的に求めるには、以下の要因を考慮する必要がある

  1. Technical factors proactive LBSの固定プロパティを扱う ポジショニング(測位)メカニズムの最大サンプリングレートf_maxなどが該当する f_max: 与えられた時間単位内で、モバイル端末が自分の位置を知る回数(つまり、位置情報を知らせる回数)を決める

  2. Environmental factors ユーザとGeofence間のパス、道路のタイプ(主道路(交通量多い方)、横の道路)による固定の重み、GPS精度など

アルゴリズム

1. Geofence内にユーザが入ってきた/出ていった可能性のある地点を求める

  1. Geofenceの境界と交差した可能性のある点の移動経路を求める

  2. 有効なパスセグメントを決めるため、セグメントをサブセグメントに分割 Fig. 7.

  3. 各有効なパスの移動時間と道路の種類を求める

  4. 各有効なパスに対して、式(1)のP(k)を計算

  5. P_transitを計算

  6. Geofence Indexの式(2)を計算

手法の課題

FPを考慮すること

4. Geofencing 2.0: Taking Location-based Notifications to the Next Level

Geofences間の時間的な関係性を考慮し、ユーザの遷移をベースとしたモデルのGeofencing手法

どういう課題か

既存アプローチは、単一の地理的な領域の定義に限られる
課題は2つ
現在のアプローチでは、あるGeofenceとそれに時空間的に関連する他のGeofenceを含むような高度なシナリオを定義できない
時間的制約のあるGeofenceのパラメータ付けはまだ不可能

どういう世界か

厳密にDey’s approarch[20]に従って、問題設定を考慮
モバイル端末は、常にGeofence内にいるか、複数Geofences間を移動しているものとする

解決方法

Fig.1. のように、複数Geofencesを移動するモバイル端末の振る舞いを状態遷移モデルによってモデル化
具体的には、通知(LBSのアクション)をトリガするために必要な挙動を行動モデルによって定式化
この行動モデルを用いることで、地理的な通知システムを動的にパラメータ化

A = <G, M, pie, T, OMEGA, omega, D, d_g, d_t>
と、このようにすることで異なるGeofences間の時間的な依存関係が記述できる

Fig. 2.のようにメールのマークがあるg_2, g_5では通知のアクションをする
g_1, g_3, g_4は通知自体はしない。
g_2, g_5で通知をするためには、まずこれらのg_1, 3, 4に入り、出た後にg_2, g_5に入らなければ、g_2, g_5でも通知されない。
-> この2つのタイプのGeofenceを本論文では定義
もちろん、これまでのように、単純にあるGeofenceの入出も可能

各構成要素の仮定

duration constraints: ある期間インターバルl_min, l_maxのこと。Geofence内に居続ける、もしくはGeofence間を遷移することが必要
l_min: 許容される最小期間
l_max: 許容される最大期間
Dのl_min, l_max … 0以上の実数, 滞在は l_min < l_max, 移動はl_min <= l_max
許容というのは、「Geofence内にいた」という判定がなされること
(l_min=0, l_max=0) … g_1を離れた直後に即g_2へ入れる
これらのアノテーションがない場合は、期間が任意

global constraints:
o_g GxG … 2つのGeofencesが互いにオーバーラップしているかどうかを判定
o_t TxT … 遷移に紐づくduration constrains内の期間インターバルが、互いにオーバーラップしない場合にtrue

ある時刻にユーザが複数Geofencesに存在することを防ぐため、式(1)~(3)を定義

2つの時間的に関連するGeofencesは領域をオーバーラップするのは×
あるGeofenceから複数のGeofencesへの遷移を考慮する際(Fig. 2.)に、g_3, g_4への遷移の期間インターバルが同じ時に、g_3, g_4が互いに領域をオーバーラップするのは×
初期のGeofenceのg状態がモーションm状態そのものとみなされるので、初期g状態へのユーザの出入りにはduration constraintsがつかない
Fig. 5. のイメージ参照

Observation at Runtime:
初期設定では、任意のGeofenceの外にいるとする

初期g状態からの出力の遷移もduration constraintsがつかない
式(4) … mu: duration constraintsがない時にtrue、Geofence gにずっと居続けることができるが、duration constraintsがある場合は、経過時間gammaが[l_min, l_max]であればtrue

f_g(x), f_m(x)はそれぞれ、ユーザがGeofence g内か、もしくは遷移中であることを計算する関数
Fig. 6, 7. : それぞれマック-映画館、マラソンユースケース
実験: Geofencing serverとして、PostGISとWebUIを使ったPoCを実施、WebGUIベースでGeofenceが定義できるようにする

以下のサイクルで、位置情報をクライアント-サーバ間でやりとり:
モバイル端末はロケーションイベントを受信したあと、円形領域に位置と精度半径を形作る
その円と最も近いobservableなGeofenceの最小距離を決定 (つまり円の半径が距離となる、この円内をsafety zoneと呼ぶ)
savety zoneにgeofencesがなければ、モバイル端末がsafety zoneを出ない限り、サーバとの対話は意味がないので場所をサーバに送信しない
geofencesがある、もしくはsafety zoneを出たらば、場所をサーバに送信
サーバはモバイル端末から場所を受信、safe zoneの更新を要求
モバイル端末がGeofenceの境界線に近づいた時、サーバはモバイル端末に対して、位置更新の頻度を高くするよう指示する
精度を犠牲にせずに電力消費を抑えるため、ポジショニングメカニズムとして[18]の手法を採用

評価: Table2 6日間のモバイル端末を用いた実世界での実験 ランニング、バイクでGeofencingを使った通知
11時間のlocation updateの量, 電力, FN, TP
FN -> 通知を満たすGeofencesの経路、Geofenceへの侵入にも関わらず、通知がされなかった数
TP -> 成功した数

サーバを用いる利点:
モバイル端末のストレージを圧迫しない

手法の課題

パラメータチューニング
Geofenceの境界のサイズと必要な精度の間にあるトレードオフの調整
速度に応じた、位置更新の頻度の調整

内容

Geofenceのカテゴリは4種類ある

  1. 空間

  2. 階層ベース

  3. ネットワークベース

  4. セマンティック

Geometric addressing … 地図上に円を描く、といったGeofence
symblic addressing … symbloc keyを特定の地理的な領域に割り当てる 例. Germany/Berlin/Ernst-Reuter-Platz, MainBuilding/1F/Room10001 など

observable: g_1に入ると同時にg_2 が見えるようになり、g_2にユーザが入ったら通知を行う。g_2がobservable。

5. Geofencing for Fleet & Freight Management

テレマティクスを用いたGeofencingの考察

どういう課題か

商用車や公共交通機関の乗り物の応用例への考察が不足している
どのようなGeofencesが必要か、を考察

どういう世界か

  1. 輸送・物流部門 重い荷物を積んだトラックが、拠点(Point Of Interests)に接近したら通知

  2. 商用車や公共交通機関の乗り物 決まった時間に、決まった地点へ到達していることを確認

解決方法

Geofenceに有効な時刻をもたせたり、さらにGeofencesによる経路を遵守させるシステムの構築
例. 輸送トラックは、この時刻に、このGeofence内に存在しているべき、いなければ通知 など

手法の課題

将来的には、衛生システムEGNOSやGALILEOを用いた位置測定で、精度向上

6. Geofence and Network Proximity

地理的な境界線をベースとした手法ではなく、近傍ネットワーク規則に基づくGeofenceを提案

手法の利点2つ:
「室内での」効率的なLBSのデプロイが可能
他手法と比べて電力消費を抑えられる

どういう課題か

Fig.2. GPSを使うと、電力消費が激しい
コンテキスト: 無線ビーコン(WifiBluetooth)を用いて位置を高精度に認識しつつ、加えて周りの要因(光や音)を数えて統合したもの

他の研究者らのアプローチでは、コンテキストに関係する情報は、GPSといった位置測定の補助的に使われていることが多い。
しかし、その補助的に使っているコンテキストに関連する情報そのもので、位置を決定できると考える。

どういう世界か

GPSの電力消費が、他の無線ビーコンらより多い
クライアントサイドで位置情報をモニタリング

解決方法

地理的なのGeofenceを近傍ネットワーク規則に置き換えて、こちらをモニタリングすることでGeofenceを実現。

  1. 高順応な位置センシングの選択方法
  2. コンテキスト情報の利用
  3. クライアント側の複数LBSsの連携

手法の要約: Wifiを使った位置推定
この手法を提案する理由は3つ:

  1. 室内で動く
  2. スマホで動く
  3. 殆どのユーザはWifiを常にON

Wifiスキャンは近傍ネットワークの一部の機能
電力節約の観点では、追加の操作が不要 (GPSだと、サーバと通信したり、ローカルでGeofenceを超えたかどうかの処理が必要になる)
電波の強度(RSSI)から、ユークリウッド距離を「クライアント側で」推定
d_a,b …
Tanimoto係数バージョンの距離計算の式もある
計算されたフィンガープリントからベースポイントの集合となる地理領域を推定可能

手段の課題

  1. ネットワーク環境が変化する度に、Wi-fiの電波強度からの距離計算が発生。この計算コストが高い。
  2. クライアント側での計算による電力消費が激しい

単一Wi-fiアクセスポイント-電波強度のグラフを基に、電波強度から距離を推定。計算をしないように工夫している。 要するにローカルでこのグラフを持っておいて、推定距離を索引するだけ。

日本語形態素解析エンジンKuromojiについて調べた

はじめに

とある事情(仕事)により、日本語の形態素解析エンジンKuromojiについて調べる必要があったので、ドキュメントとコードを読み込んだ。 形態素解析とは、ものすごく簡単に言うと、文章をその構造や品詞に細かく分解することです。分解された単位をトークンと呼ぶ。(イメージとしては、単語や助詞がトークンとなりえる。)

形態素解析 - Wikipedia

特に、自然言語処理(NLP)なんかでは馴染みがあるのでは?(私は素人なので...) 形態素解析は、主に利用する辞書の精度(網羅率)に大きく依存する形になります。例えば「ほげふが」という文章を解析するとして、辞書に「ほげ」と「ふが」が存在している場合、["ほげ", "ふが"]と2つのトークンに分解することができる。(これをトークナイズと呼ぶ。) 同じく文章をトークンに分解する方法として、N-gramがあります。Nに数字が入るわけですが、例えば2-gramで文章「ほげふが」をトークナイズする場合は、["ほげ", "げふ", "ふが"]と3つのトークンを生成することができる。

なおApatche版とAtilika版の2つが存在しますが、本記事では Atilika版 version 0.9.0を対象としている。

Kuromoji

概要

Java製の日本語形態素解析エンジン。 公式
kuromoji - japanese morphological analyzer

ソースコード github.com

単語辞書

Kuromojiでは、ユーザ側は用意されている単語辞書(例. kuromoji-ipadic)に加えて、ユーザ独自で固有名詞等を指定できるユーザ辞書を利用できる。 また、内部的にはこれらの辞書に含まれない単語を、「未知の」単語辞書として保持しているようです。ちなみに未知の単語辞書については、そのカテゴリによって自動的にトークン化される。例えば「123#.!」という文章がある場合、["123", "#.!"]と数字、記号のカテゴリにトークン化される。詳しくは以下の実装を確認してほしい。

kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

Kuromojiの解析モード

トークン化する際の解析粒度に応じて、モードが3つほど存在する。

  • Normalモード デフォルトモードで、辞書にのっとってトークナイズする。 未知の単語については、上記の方法にのっとり、カテゴリごとにまとめてトークナイズする。

  • Searchモード Normalモードに加えて、複数の言葉が組み合わさった単語を分解してトークナイズする。 例えば「日本経済新聞」という名詞があった場合、["日本", "経済", "新聞"]と分解する。 何が嬉しいかというと、全文検索エンジンなどで、単語を引っ掛けたい時に有効。

  • Extendsモード Searchモードに加えて、未知語をuni-gram (雲丹ではなくて「1」という意味)としてトークナイズする。 例えば、「サバゲー」が未知語の場合は、["サ", "バ", "ゲ", "ー"]となる。

内部で用いられるアルゴリズム

  • Patricia Trieを使ったFinite State Transducerによる辞書管理。
  • Viterbi アルゴリズムによって形態素ラティスを作成し、尤もらしいトークナイズをする。

形態素ラティス

下図のような、ノードがトークンとなったラティス。 各ノード・エッジにはコストが存在し、それぞれ単語辞書・解析モード別の計算式によって与えられる。 このコストを最小となる (≒ 尤もらしいトークナイズができている) パスを求めるためにViterbiアルゴリズムを用いる。

f:id:tikeda_meu:20180922143320p:plain

Viterbi

隠れマルコフモデルに基づいた動的計画法(DP)で、考えられる経路の中で尤もらしい経路を見つける。 隠れマルコフモデルに従うので、コストの部分について確率的な解釈が可能 (というかそうするのが一般) である。しかし今回のケースではコストが一意に決まるため、最小コストを確率ではなく一意に探索することが可能。

ビタビアルゴリズム - Wikipedia

Viterbiアルゴリズム - 機械学習の「朱鷺の杜Wiki」

http://www.phontron.com/slides/nlp-programming-ja-04-ws.pdf

時間計算量がO(T*N2)かかる? (T: 時間の終端、N:ノード数)

実装は以下。

kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

Patricia Trie

基数木と呼ばれる木構造のこと。 連想配列を使って各エッジに文字が張られるイメージ。 f:id:tikeda_meu:20180922145318p:plain

基数木 - Wikipedia

Pros

  • 省メモリ
  • 検索・挿入・削除 : O(k) (k: キーの長さ) なので、 (二分木と比べると、場合によっては)物凄く速い。
  • 日本語の場合は文字列長が小さいので、ここはかなり効いてくると考えられる。

    Cons

  • 文字列や、文字列に変換可能なデータしか扱えない。

Finite State Transducer (FST)

有限状態トランスデューサと呼ばれる。いわゆる有限状態オートマトンに各エッジの出力を加えたもの。 f:id:tikeda_meu:20180922145825p:plain

Luceneで使われてるFSTを実装してみた(正規表現マッチ:VMアプローチへの招待)

Kuromoji FST

Pros

  • Patricia Trieが利用可能・状態数が最小であることが保証されるため、省メモリ。
  • 決定性を持つため、入力に対する出力が一意に決定。
  • DAGなのでトポロジカルソート可能。
ラティスにおける最小コストの経路はトポロジカルソート+ Viterbiで高速に探索可能。トポロジカルソートはO(V+E) (V:ノード数, E:エッジ数)。

有向非巡回グラフ - Wikipedia

Cons

  • 先頭文字(prefix)の探索に時間がかかる。(日本語だと候補となる文字数が多すぎるので危険...) なので、先頭文字はcachingなどによる高速化で工夫される。

FSTで単語辞書を管理している。 (未知の単語辞書も含む) // Note that FST only allows the presorted dictionaries as input.

kuromoji/Builder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

ユーザ辞書を使った単語分割

こっちもFSTで保持。 surfaceが(Trie構造)FSTで保持している辞書

kuromoji/UserDictionary.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub

若干しゃくとり法と似てるなと思った(は?)

qiita.com

以下が実装部分

 /** Lookup words in text
    * @param text text to look up user dictionary matches for
    * @return list of UserDictionaryMatch, not null */
    public List<UserDictionaryMatch> findUserDictionaryMatches(String text) {
        List<UserDictionaryMatch> matchInfos = new ArrayList<>();
        int startIndex = 0;
        while (startIndex < text.length()) {
            int matchLength = 0;
            int endIndex = 0;
            while (currentInputContainsPotentialMatch(text, startIndex, endIndex)) { //トークン検索
                String matchCandidate = text.substring(startIndex, startIndex + endIndex);
                if (surfaces.containsKey(matchCandidate)) {
                    matchLength = endIndex;
                }
                endIndex++;
            }
            if (matchLength > 0) { //マッチするようなトークンが見つかったらば,
                String match = text.substring(startIndex, startIndex + matchLength);
                int[] details = surfaces.get(match);
                if (details != null) {
                    matchInfos.addAll(
                        makeMatchDetails(startIndex, details)
                    );
                }
            }
            startIndex++;
        }
        return matchInfos;
    }

おわりに

まとめると、シンプルにかけます。 1. FSTによる管理で高速に辞書検索(トークンとなる候補をここで探す。) 2. 形態素ラティスを構築して尤もらしくトークナイズする(トークンとなる候補の中から、トークンを決定する。) 高速化を意識された実装になっていて、素晴らしいと思いました。