ナード戦隊データマン

データサイエンスを用いて悪と戦うぞ

Facebook Researchのfaissで類似検索

faissとは、類似性検索およびクラスタリングのための高速アルゴリズムを実装したライブラリです。ここでは、文書をベクトル化してfaissのインデクスに登録し、ベクトル化したクエリで検索してみます。

簡単な概念図

Untitled drawing.jpg

jupyterで実行

まず、必要となるライブラリをインポートします。faissは事前にインストールしておいてください。

In[1]:

import faiss
import tensorflow as tf
import tensorflow_hub as hub
from janome.tokenizer import Tokenizer

次に、例文を用意してベクトル化します。

In[2]:

example_sentences = [
    "京都の大学",
    "アメリカの美味しい食べ物",
    "機械学習の本",
    "ビル・ゲイツ",
    "御殿場市民"
]

jtok = Tokenizer()

with tf.Graph().as_default():
    embed = hub.Module("https://tfhub.dev/google/nnlm-ja-dim128/1")
    embeddings = embed(list(map(lambda x: ' '.join([y.surface for y in jtok.tokenize(x)]), example_sentences)))

    with tf.Session() as sess:
        sess.run(tf.global_variables_initializer())
        sess.run(tf.tables_initializer())
        example_vectors = sess.run(embeddings)

faissにベクトルをインデクシングします。

In[3]:

dim = 128
index = faiss.IndexFlatL2(dim)   
index.add(example_vectors)

検索用メソッドを作成します。

In[4]:

def encode_query(text):
    with tf.Graph().as_default():
        embed = hub.Module("https://tfhub.dev/google/nnlm-ja-dim128/1")
        embeddings = embed(list(map(lambda x: ' '.join([y.surface for y in jtok.tokenize(x)]), [text])))

        with tf.Session() as sess:
            sess.run(tf.global_variables_initializer())
            sess.run(tf.tables_initializer())
            return sess.run(embeddings)


def search_by_text(text, index, sents, k=1):
    D, I = index.search(encode_query(text), k)
    for i in I[0]:
        print(sents[i])

最後に、いくつかクエリで検索して試してみます。

In[5]:

search_by_text("バカ", index, example_sentences),
search_by_text("プログラマー", index, example_sentences),
search_by_text("立命館", index, example_sentences),

Out[5]:

御殿場市民

ビル・ゲイツ

京都の大学

まあ、大体それっぽく検索できているようです。(この文例の中で最も"バカ"に近い文は"御殿場市民")

ちなみに、search_by_textは、indexの中からクエリのtextに近いk件の文ベクトルを探すメソッドです。

参考

[1] https://github.com/facebookresearch/faiss/wiki/Getting-started [2] https://www.tensorflow.org/hub/

文書分類モデルをLTRの特徴量にする

以前の記事で、LTRの概要を書きました。MicrosoftのLTRのデータセットでは、"Quality Score"という特徴量が用意されていて、おそらくコンテンツベースの特徴量だと思うので、ここでは文書分類モデルを特徴量として与える方法を書きます。

どうやってアノテーションするおつもり?

コンテンツベースの特徴量として、例えば「文書の有害性」などを判定するモデルを作成したいと思うでしょう。でも、手作業で文書を分類してアノテーションするのは相当苦労します。そこで、ヒューリスティックな方法で以下を採用します。

事前準備1: クロール済みデータをElasticsearch等でインデクシングしておく。 事前準備2: Quality Scoreを表すフィールドをインデクスのマッピングに追加。

ヒューリスティクス: 1. このクエリを投げると殆どの検索結果が「良いページ(or 悪いページ)」になるようなクエリを複数探す。 2. そのクエリで取得した文書で、良いページのクエリで出てきたものをTrue, 悪いページのクエリで出てきたものをFalseとして自動的にアノテーションする。

以下はそのコードの例です:

from elasticsearch import Elasticsearch
from tqdm import tqdm_notebook

def create_base_query(text, size=1000):
    baseQuery = {
        'size': int(size),
        'query':{
            'function_score':{'query': {"simple_query_string": {
                "query": text,"fields": ["title"],"default_operator": "and"
            }}}
        }
    }
    return baseQuery

es = Elasticsearch("192.168.88.85:9200")
good_queries = ["Wikipedia", "はてなキーワード", "ヘルスケア大学", "医療総合QLife", "ロイター", "MIT Tech Review"]
bad_queries = ["ログ速", "2ちゃんねる","気団ログ", "エロ", "キチガイ", "ネトウヨ", "サヨク", "fuck", "萌え"]

out = []
for q in tqdm_notebook(good_queries):
    query = create_base_query(text=q, size=3000)
    results = es.search(index="test_ltr", doc_type="page", body=query)
    for r in results['hits']['hits']:
        out.append((r['_source']['texts'], True))
        
for q in tqdm_notebook(bad_queries):
    query = create_base_query(text=q, size=3000)
    results = es.search(index="test_ltr", doc_type="page", body=query)
    for r in results['hits']['hits']:
        out.append((r['_source']['texts'], False))

モデルの訓練と評価

次に、前述のデータを使って、良質なページかどうかを分類するモデルを作ります。モデリングには色々方法があるため、ここではコード的にわかりやすい方法を採用します。(DNN + nnlm-ja Embedding)

ただし、"out"という変数は、前述のコードのものをそのまま使います。(jupyterなどを使ってください。)

import tensorflow as tf
import tensorflow_hub as hub
import numpy as np
import pandas as pd
from sklearn.utils import shuffle
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split

df = pd.DataFrame(out, columns=["texts", "label"])
df = shuffle(df)
X_train, X_test, y_train, y_test = train_test_split(df[["texts"]], df["label"])

train_input_fn = tf.estimator.inputs.pandas_input_fn(
    X_train, y_train, num_epochs=None, shuffle=True)

predict_test_input_fn = tf.estimator.inputs.pandas_input_fn(
    X_test, None, shuffle=False)

embedded_text_feature_column = hub.text_embedding_column(
    key="texts", 
    module_spec="https://tfhub.dev/google/nnlm-ja-dim128/1")

estimator = tf.estimator.DNNClassifier(
    hidden_units=[500, 100],
    feature_columns=[embedded_text_feature_column],
    n_classes=2,
    optimizer=tf.train.AdagradOptimizer(learning_rate=0.003), model_dir="model2/")

estimator.train(input_fn=train_input_fn, steps=5000)

y_pred = [x['class_ids'][0] > 0.0 for x in estimator.predict(predict_test_input_fn)]

print(roc_auc_score(y_test, y_pred))

出力: 0.9833079636964895

このデータセットでは汎化性能があることがわかります。(本当は、用意したデータとは全く別のデータでAUCを求めたほうが良いです。)

Elasticsearchにアップデート

この種の特徴量は、インデクシングの際に同時に追加することが難しいため、すでにインデクシングしてあるドキュメントに対して、updateする形で特徴量を追加します。

import pandas as pd
import tensorflow as tf
import tensorflow_hub as hub
from elasticsearch import Elasticsearch
from tqdm import tqdm

def get_esindex_maxid(indexname='test_ltr', host="192.168.88.85:9200"):
    es = Elasticsearch(host)
    esquery = {
        'query': {'match_all': {}},
        'aggs': {'max_pgid': {'max': {'field': 'page_id'}}}
    }
    ret = es.search(index = indexname, size = 0, doc_type = 'page', body = esquery)
    return int(ret['aggregations']['max_pgid']['value'])


def solve_score(es, model_dir="model2/"):
    embedded_text_feature_column = hub.text_embedding_column(
            key="texts",
            module_spec="https://tfhub.dev/google/nnlm-ja-dim128/1")
    
    estimator = tf.estimator.DNNClassifier(
        hidden_units=[500, 100],
        feature_columns=[embedded_text_feature_column],
        n_classes=2,
        optimizer=tf.train.AdagradOptimizer(learning_rate=0.003), model_dir=model_dir)

    MAXSIZE = get_esindex_maxid("test_ltr")
    SIZE = 100
    for i in tqdm(range(int(MAXSIZE/SIZE) + 1)):
        results = []
        for j in range(SIZE):
            idx = j+i*SIZE
            if idx > MAXSIZE:
                break
            try:
                data = es.get(index="test_ltr", doc_type="page", id=idx)
                if 'quality_score' in data['_source']:
                    continue
                results.append((idx, data['_source']['texts']))
            except:
                print(idx)
        if len(results) == 0:
            continue
        df = pd.DataFrame(results, columns=["id", "texts"])
        input_fn = tf.estimator.inputs.pandas_input_fn(df[['texts']], None, shuffle=False)
        probs = [x['probabilities'][0] for x in estimator.predict(input_fn)]
        for idx, prob in zip(df['id'].tolist(), probs):
            try:
                es.update(index="test_ltr", doc_type="page", id=idx, body={"doc":{"quality_score": float(prob)}})
            except:
                print(idx)

if __name__ == "__main__":
    es = Elasticsearch("192.168.88.85:9200")
    solve_score(es, model_dir="/home/shun/work/scripts/model2/")

おわりに

ここで述べた方法は、あくまでも「アノテーションが面倒なときの一つの妥協案」だと考えてください。もし、信頼できる「文書の有害性コーパス」みたいなものがあれば、そちらを使ったほうが良いでしょう。ただ、ここで述べた方法の場合、「不正にTopに出現させようとしてくるWebスパム」を排除するのにも使えます。WebスパムのURLをベースにアノテーションを作成すれば、Quality Scoreをスパム検出に使えます。

参考

[1] https://www.tensorflow.org/tutorials/text_classification_with_tf_hub

Webスパムを判定するためのリンクベース手法

Webスパムを判断する方法として、1)リンクベース特徴量を用いる方法, 2)コンテンツベース特徴量を用いる方法, がありますが、そのうちリンクベース特徴量では、TrustRankやAnti-TrustRankなどが有名です。しかし、QoC, QoLというもっと精度が高いらしい方法があったのでアルゴリズムを書いておきます。 https://github.com/sugiyamath/link_based_anti_spamming

アルゴリズムの数式

Screenshot_2018-06-02_07-46-07.png

QoCとQoLは同時に更新されます。ELは初期値として設定する値ですが、以下の4種類の方法で初期化が可能です:

  1. すべて"1/ページ数"で初期化。(uniform)
  2. 良いページの値を1、そうでない値を0で初期化。
  3. 悪いページの値を-1、そうでない値を0で初期化。
  4. 2と3を組み合わせて初期化。

QoCとQoLPageRank、TrustRank、AntiTrustRankを組み合わせたような機能性を持っているようです。

アルゴリズムのコード

以下は、数式をコード化したものです。

import numpy as np

def init_edges(size):
    edges = {}
    for i in range(size):
        edges[i] = []
    return edges

def load_edges(edge_file):
    tmp = []
    with open(edge_file, 'r') as f:
        for line in f:
            target = line.strip().split()
            tmp += [int(target[0]), int(target[1])]
    max_value = max(tmp) + 1
    from2to = init_edges(max_value)
    to2from = init_edges(max_value)
    with open(edge_file, 'r') as f:
        for line in f:
            target = line.strip().split()
            from2to[int(target[0])].append(int(target[1]))
            to2from[int(target[1])].append(int(target[0]))    
    return from2to, to2from

def init_Q(size, sparse_seed=None):
    """
    initial values using four ways:
      1. uniform: [1.0/size for i in range(size)]
      2. good seed set: {1:1, 5:1, 6:1, ...}
      3. bad seed set: {2:-1, 3:-1, 8:-1, ...}
      4. mixture: {1:1, 2:-1, 3:-1, ...}
    """
    if sparse_seed is None:
        return np.array([1.0/size for i in range(size)])
    else:
        out = []
        for i in range(size):
            if i in sparse_seed:
                out.append(sparse_seed[i])
            else:
                out.append(0.0)
        return np.array(out)
    
def update_QoC(QoC, QoL, from2to, to2from, size, alpha=0.6):
    out_QoC = np.copy(QoC)
    for i in range(size):
        total = 0
        for q_i in to2from[i]:
            ON_q_i = len(from2to[q_i])
            if ON_q_i == 0:
                continue
            left = alpha * (QoC[q_i]/ON_q_i)
            right = (1.0-alpha) * (QoL[q_i]/ON_q_i)
            total += left + right
        out_QoC[i] = total
    return out_QoC

def update_QoL(QoL, QoC, from2to, to2from, size, alpha=0.6):
    out_QoL = np.copy(QoL)
    for i in range(size):
        total = 0
        for r_i in from2to[i]:
            IN_r_i = len(to2from[r_i])
            if IN_r_i == 0:
                continue
            left = alpha * (QoC[r_i]/IN_r_i)
            right = (1.0-alpha) * (QoL[r_i]/IN_r_i)
            total += left + right
        out_QoL[i] = total
    return out_QoL

def train(QoC, QoL, from2to, to2from, size, itersize=5, alpha=0.6, beta=0.6, gamma=0.6):
    """
    INPUT QoC, QoL: np.array
    """
    out_QoL = np.copy(QoL)
    out_QoC = np.copy(QoC)
    for i in range(itersize):
        print("Iter:",str(i))
        out_QoC = update_QoC(out_QoC, out_QoL, from2to, to2from, size, alpha=alpha)
        out_QoL = update_QoL(out_QoL, out_QoC, from2to, to2from, size, alpha=beta)
        out_QoC = gamma * out_QoC + (1.0-gamma) * QoC
        out_QoL = gamma * out_QoL + (1.0-gamma) * QoL
    return out_QoC, out_QoL


if __name__ == "__main__":
    from2to, to2from = load_edges("/home/shun/work/data/edges.csv")

    size = len(from2to.items())
    assert(size == len(to2from.items()))

    QoC = init_Q(size)
    QoL = np.copy(QoC)
    
    out_QoC, out_QoL = train(QoC, QoL, from2to, to2from, size, itersize=10)
    
    with open("/home/shun/work/data/nodes_and_QoC.csv", 'w') as f:
        for i in range(out_QoC.shape[0]):
            f.write("{},{}\n".format(i,out_QoC[i]))
            
    with open("/home/shun/work/data/nodes_and_QoL.csv", 'w') as f:
        for i in range(out_QoL.shape[0]):
            f.write("{},{}\n".format(i,out_QoL[i]))
    

edges.csvには、以下の形式で辺を定義します。

from_id[tab]to_id\n . . .

from_idとは、リンク元のページのIDで、to_idはリンク先のページIDです。言い換えると、クローリングしてURL、外部リンクURLsを取得し、グラフ構造をURLに対応したIDを用いて定義したものです。

精度

Screenshot_2018-06-02_07-56-10.png

Screenshot_2018-06-02_07-58-33.png

QoCとQoLは、どちらも「良いページ」や「悪いページ」を検出するのに高い精度を出していることがわかります。また、正当なページやフェイクページを分類する精度も高いようです。

考察

QoCやQoLを条件として利用し、検索システムの検索結果から悪いページを除外する使い方もありますが、LTR(ランキング学習)の特徴量の一つとして使うこともできます。

また、検索結果を改善するために、手作業のパラメータチューニングと機械学習を用いたLTRのチューニングの両方を考慮することもできます。LTRでは、通常の検索結果に対してリスコアする、という2段階の構成になりますが、通常の検索結果を改善するために手作業のチューニングを行い、リスコアの段階で機械学習を用います。

LTRの特徴量としてQoC,QoLを使う以外にも、通常の検索結果を取得する段階でPageRankの代わりにQoCやQoLを使っても良いと思います。

参考

[1] https://arxiv.org/abs/1309.7266

LTR ( learning to rank, 順序学習 ) とは何か

ElasticsearchやSolrで検索システムを構築する際に、ドキュメント-クエリペアの特徴量とクリックデータ等のラベルを用いて機械学習を適用し、Top-kに対して再ランクすることを「LTR」または「順序学習」と呼ばれています。ここでは、LTRについての全体像を説明します。

検索のフロー

Untitled drawing.png

まず、ユーザがクエリを投げ、通常の情報検索を行います。「通常の」とは、例えば形態素解析やngramによる検索のことです。

次に、上位k件に対してLTRの機械学習モデルでスコアリングをします。特徴量は、「クエリ」と「ドキュメント」のペアから抽出できるものです。例えば、クエリとドキュメントのタイトルのベクトル表現のコサイン類似度とか、ページランク、TF, IDF, あるクエリで出てきた各々のドキュメントのクリック回数、など様々です。

最後に、re-rankされた結果が取得されます。

LTRの特徴量設計

MicrofostからLTR用のデータセットが公開されています。 https://www.microsoft.com/en-us/research/project/mslr/

Feature List of Microsoft Learning to Rank Datasets
feature id    feature description      stream comments
1    covered query term number      body
2      anchor
3      title
4      url
5      whole document
6    covered query term ratio      body
7      anchor
8      title
9      url
10      whole document
11    stream length      body
12      anchor
13      title
14      url
15      whole document
16    IDF(Inverse document frequency)      body
17      anchor
18      title
19      url
20      whole document
21    sum of term frequency      body
22      anchor
23      title
24      url
25      whole document
26    min of term frequency      body
27      anchor
28      title
29      url
30      whole document
31    max of term frequency      body
32      anchor
33      title
34      url
35      whole document
36    mean of term frequency      body
37      anchor
38      title
39      url
40      whole document
41    variance of term frequency      body
42      anchor
43      title
44      url
45      whole document
46    sum of stream length normalized term frequency      body
47      anchor
48      title
49      url
50      whole document
51    min of stream length normalized term frequency      body
52      anchor
53      title
54      url
55      whole document
56    max of stream length normalized term frequency      body
57      anchor
58      title
59      url
60      whole document
61    mean of stream length normalized term frequency      body
62      anchor
63      title
64      url
65      whole document
66    variance of stream length normalized term frequency      body
67      anchor
68      title
69      url
70      whole document
71    sum of tf*idf      body
72      anchor
73      title
74      url
75      whole document
76    min of tf*idf      body
77      anchor
78      title
79      url
80      whole document
81    max of tf*idf      body
82      anchor
83      title
84      url
85      whole document
86    mean of tf*idf      body
87      anchor
88      title
89      url
90      whole document
91    variance of tf*idf      body
92      anchor
93      title
94      url
95      whole document
96    boolean model      body
97      anchor
98      title
99      url
100      whole document
101    vector space model      body
102      anchor
103      title
104      url
105      whole document
106    BM25      body
107      anchor
108      title
109      url
110      whole document
111    LMIR.ABS      body Language model approach for information retrieval (IR) with absolute discounting smoothing
112      anchor
113      title
114      url
115      whole document
116    LMIR.DIR      body Language model approach for IR with Bayesian smoothing using Dirichlet priors
117      anchor
118      title
119      url
120      whole document
121    LMIR.JM      body Language model approach for IR with Jelinek-Mercer smoothing
122      anchor
123      title
124      url
125      whole document
126    Number of slash in URL
127    Length of URL
128    Inlink number
129    Outlink number
130    PageRank
131    SiteRank Site level PageRank
132    QualityScore The quality score of a web page. The score is outputted by a web page quality classifier.
133    QualityScore2 The quality score of a web page. The score is outputted by a web page quality classifier, which measures the badness of a web page.
134    Query-url click count The click count of a query-url pair at a search engine in a period
135    url click count The click count of a url aggregated from user browsing data in a period
136    url dwell time The average dwell time of a url aggregated from user browsing data in a period

上記ページの"Feature List"では、136の特徴量があります。

しかし、これらの特徴量だけにこだわる必要はありません。例えば、SpamRankやTrustRankといったリンクベース特徴量を追加しても良いですし、URL内の/の数(深さ)みたいな独自の特徴量を付け加えても良いです。

このあたりは、データサイエンス的に特徴量設計を行うことができるフェーズです。

重要なのは、「クエリ」と「ドキュメント」のペアから取得できる特徴量を定義することです。特徴量には「動的なもの」と「静的なもの」がありますが、動的なものはクエリに依存します。静的なものはドキュメントのみに依存します。また、システムによってはユーザ属性を付け加えたいと思うかもしれませんが、その場合はユーザごとにLTRを訓練することもできます。

機械学習アルゴリズム

RankSVMが一番有名だと思いますが、LTRでは様々なアルゴリズムが開発されています。

Year Name Type Notes
1989 OPRF [16] 2 pointwise Polynomial regression (instead of machine learning, this work refers to pattern recognition, but the idea is the same)
1992 SLR [17] 2 pointwise Staged logistic regression
1999 MART (Multiple Additive Regression Trees) 2 pairwise
2000 Ranking SVM (RankSVM) 2 pairwise A more recent exposition is in,[3] which describes an application to ranking using clickthrough logs.
2002 Pranking[18] 1 pointwise Ordinal regression.
2003 RankBoost 2 pairwise
2005 RankNet 2 pairwise
2006 IR-SVM 2 pairwise Ranking SVM with query-level normalization in the loss function.
2006 LambdaRank pairwise/listwise RankNet in which pairwise loss function is multiplied by the change in the IR metric caused by a swap.
2007 AdaRank 3 listwise
2007 FRank 2 pairwise Based on RankNet, uses a different loss function - fidelity loss.
2007 GBRank 2 pairwise
2007 ListNet 3 listwise
2007 McRank 1 pointwise
2007 QBRank 2 pairwise
2007 RankCosine 3 listwise
2007 RankGP[19] 3 listwise
2007 RankRLS 2 pairwise

Regularized least-squares based ranking. The work is extended in [20] to learning to rank from general preference graphs.

2007 SVMmap 3 listwise
2008 LambdaSMART/LambdaMART pairwise/listwise Winning entry in the recent Yahoo Learning to Rank competition used an ensemble of LambdaMART models. Based on MART (1999)[21] “LambdaSMART”, for Lambda-submodel-MART, or LambdaMART for the case with no submodel (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-109.pdf).
2008 ListMLE 3 listwise Based on ListNet.
2008 PermuRank 3 listwise
2008 SoftRank 3 listwise
2008 Ranking Refinement[22] 2 pairwise A semi-supervised approach to learning to rank that uses Boosting.
2008 SSRankBoost[23] 2 pairwise An extension of RankBoost to learn with partially labeled data (semi-supervised learning to rank)
2008 SortNet[24] 2 pairwise SortNet, an adaptive ranking algorithm which orders objects using a neural network as a comparator.
2009 MPBoost 2 pairwise Magnitude-preserving variant of RankBoost. The idea is that the more unequal are labels of a pair of documents, the harder should the algorithm try to rank them.
2009 BoltzRank 3 listwise Unlike earlier methods, BoltzRank produces a ranking model that looks during query time not just at a single document, but also at pairs of documents.
2009 BayesRank 3 listwise A method combines Plackett-Luce Model and neural network to minimize the expected Bayes risk, related to NDCG, from the decision-making aspect.
2010 NDCG Boost[25] 3 listwise A boosting approach to optimize NDCG.
2010 GBlend 2 pairwise Extends GBRank to the learning-to-blend problem of jointly solving multiple learning-to-rank problems with some shared features.
2010 IntervalRank 2 pairwise & listwise
2010 CRR 2 pointwise & pairwise Combined Regression and Ranking. Uses stochastic gradient descent to optimize a linear combination of a pointwise quadratic loss and a pairwise hinge loss from Ranking SVM.
2017 ES-Rank listwise Evolutionary Strategy Learning to Rank technique with 7 fitness evaluation metrics

アルゴリズムの分類としては3種類あります。

pointwise: 各クエリ-ドキュメントペアには数値スコアが付与されます。単一の値をラベルとして持つ回帰または分類の問題になります。

pairwise: ドキュメントxとyに対し、どちらが良いドキュメントなのかを学習します。

listwise: クエリに対し、最適順序のリストを学習します。

https://en.wikipedia.org/wiki/Learning_to_rank

クリックデータを基にpointwiseやpairwiseを使うのが一般的です。 (listwiseはちょっと難しい)

クリックデータを用いたLTRの社会心理学的問題点

検索エンジンでLTRを用いる場合、社会心理学的な問題が発生します。

(1) position bias 人間は、最初と最後だけを見て、中央を無視することがあります。

(2) presentation bias 表示された結果以外のフィードバックが受け取れません。

(3) trust bias ユーザがTopに表示されたものを無批判に信用しがちです。

これらのバイアスは選択バイアスの一種ですが、例えば「見られやすいものはより見られるようになる」という現象が起きてしまいます。この現象が起きると、文書全体に対して正しい評価を与えることができません。

具体的な実装

Solr: https://lucene.apache.org/solr/guide/6_6/learning-to-rank.html Elasticsearch LTR plugin: https://github.com/o19s/elasticsearch-learning-to-rank

参考

[1] https://en.wikipedia.org/wiki/Learning_to_rank [2] https://www.microsoft.com/en-us/research/project/mslr/ [3] https://medium.com/@nikhilbd/80a8fe8fadfd [4] https://ai.google/research/pubs/pub45286

csvに出力されたグラフをTitanに読み込んでPageRankを求める

Titanとは、分散型のグラフデータベースです。グラフ操作フレームワークのtinkerpopと組み合わせて使うことができます。ここでは、csvに出力されたグラフ(ノードとエッジ)をTitanに読み込んでからpagerankを求めます。

注意: Titanは開発が放置状態!

2018/05/19現在、Titanのgithubページを見てみると、開発が3年ほど停止していました。そのため、JanusGraphというForkバージョン(The Linux Foundationが開発)を使うことをおすすめします。ただし、ここではあえてTitanを使って説明します。(titanのほうが検索されやすいので)

ダウンロードと展開

wget http://s3.thinkaurelius.com/downloads/titan/titan-1.0.0-hadoop1.zip
unzip titan-1.0.0-hadoop1.zip
cd titan-1.0.0-hadoop1

gremlinについて

gremlinとは、グラフを操作するための専用の言語のことです。groovyによって操作が可能ですが、gremlin-serverを立ち上げればpythonからアクセスできます。gremlin-serverを立ち上げるには、以下を実行します:

bin/gremlin-server.sh

gremlinpythonを使えば、pythonからgremlin-serverへアクセスできます:

pip install --user gremlinpython==3.0.1

groovyスクリプトを実行したい場合は、以下のようなコマンドを実行します:

bin/gremlin.sh -e targetscript.groovy

pythonからアクセスするには、以下のようなコードを実行します:

from gremlin_python.structure.graph import Graph
from gremlin_python.driver.driver_remote_connection import DriverRemoteConnection
g = Graph().traversal().withRemote(DriverRemoteConnection('ws://localhost:8182/gremlin','g'))
print(g.V().count().next())

今回は、PageRankを求めるだけなので、gremlinについて知りたい人は以下の記事などを見てください. https://qiita.com/wan-liner/items/737741805f4c5cfb0cb9

csvをTitanに読み込むgroovyスクリプトの作成

ノードとエッジがcsvに出力されていると仮定します。ノードリストはノードのidを改行で区切ったもの、エッジは "fromノードid,toノードid"を改行で区切ったものとします。例えば、クロールしたデータからurlとoutlinksを抽出してエッジとして出力します。

import com.thinkaurelius.titan.core.TitanFactory
import com.thinkaurelius.titan.core.Cardinality
import com.thinkaurelius.titan.core.Multiplicity
import com.thinkaurelius.titan.core.schema.ConsistencyModifier
import com.thinkaurelius.titan.core.TitanTransaction
import org.apache.tinkerpop.gremlin.structure.T
import java.util.logging.Logger

Logger logger = Logger.getLogger("")

graph = TitanFactory.open('/home/shun/work/titan-1.0.0-hadoop1/conf/titan-berkeleyje-es.properties')
m = graph.openManagement()
k = m.makePropertyKey('urlId').dataType(String.class).cardinality(Cardinality.SINGLE).make()
m.buildIndex('byid', Vertex.class).addKey(k).buildCompositeIndex()
m.makeEdgeLabel('linkTo').multiplicity(Multiplicity.MULTI).make()
m.commit()

Logger logger = Logger.getLogger("")

graph = TitanFactory.open('/home/shun/work/titan-1.0.0-hadoop1/conf/titan-berkeleyje-es.properties')
g = graph.traversal()
tx = graph.newTransaction() 


counter = 0
added = false
Vertex getVertexById(String id){
    p = g.V().has('urlId', id)
    if(p.hasNext()){
    v = p.next()
    } else {
        v = tx.addVertex(T.label, 'website', 'urlId', id)
        added = true
    }
    return v
}

logger.info("Step1")
new File('/home/shun/work/titan-1.0.0-hadoop1/mydata/data/nodes.csv').eachLine {
    theid = String.valueOf(it)
    v = getVertexById(theid)
}

if(added){
  tx.commit()
}


counter = 0
e_added = false
logger.info("Step2")
new File('/home/shun/work/titan-1.0.0-hadoop1/mydata/data/edges.csv').eachLine {
    if(!it.startsWith("from")) {
      (fid, tid) = it.split(',')
      fid = String.valueOf(fid)
      tid = String.valueOf(tid)

      fromVertex = getVertexById(fid)
      toVertex = getVertexById(tid)

      if(!g.V(fromVertex).outE('linkTo').filter(inV().is(toVertex)).hasNext()){
         fromVertex.addEdge('linkTo', toVertex)
         e_added = true
      }
   }
}

if(e_added){
  graph.tx().commit()
}

logger.info("Step3")
prvp = PageRankVertexProgram.build().create()
result = graph.compute().program(prvp).submit().get()

graph.io(IoCore.graphson()).writeGraph("/home/shun/work/titan-1.0.0-hadoop1/mydata/data/graph_with_pagerank.json")

logger.info("DONE")

フローは以下です:

  1. グラフの読み込み。
  2. プロパティキー、エッジ名、インデクスを追加。
  3. ノードの読み込み
  4. エッジの読み込み。
  5. ページランクを求める。
  6. ページランクを求めたグラフをjson出力。

SparkGraphComputerも使える

ページランクをSparkGraphComputerを使って求めるには、graph.computeで指定します。

graph = GraphFactory.open('/usr/iop/current/titan-client/conf/hadoop-graph/hadoop-gryo.properties')
prvp = PageRankVertexProgram.build().create()
result = graph.compute(SparkGraphComputer).program(prvp).submit().get()
result.memory().getRuntime()
result.memory().asMap()
g = result.graph().traversal(computer(SparkGraphComputer))
g.V().valueMap('name', PageRankVertexProgram.PAGE_RANK)

参考

[1] JanusGraph : http://janusgraph.org/ [2] Titan spark graph computing in IBM Open Platform : https://developer.ibm.com/hadoop/2017/05/21/titan-spark-graph-computing-ibm-open-platform/ [3] TITAN Distributed Graph Database : http://titan.thinkaurelius.com/

P.S. groovyなんて初めてですが、とりあえず実行はできました。

elasticsearchでユーザベクトルを用いて検索する

ユーザベクトルとは、ユーザの最近の興味を表す数値からなるベクトルのことです。このベクトルを用いて検索できれば、検索結果にユーザの興味が反映されます。ここでは、ユーザベクトルによる検索をelasticsearchを用いて行う方法を書きます。

ユーザベクトルについて

ドキュメントをベクトル化する方法があると仮定します。例えば、tensorflow-hubのnnlmエンベディングを用いれば、ドキュメントをベクトル化することが可能です。

ユーザが検索をして、検索結果のある特定のリンクをクリックします。すると、クリックされたリンクのドキュメントベクトルはユーザベクトルの一部として保存されます。例えば、保存できるベクトルの件数を最新100件などとしておきます。

そして、検索をする際に「ユーザベクトルの平均ベクトル」と「ドキュメントベクトル」の類似度を使うようにすれば、ユーザの興味に類似した記事が検索可能です。

vector-scoringプラグイン

elasticsearch 5.6.0に対応したプラグインとして以下があります。 https://github.com/lior-k/fast-elasticsearch-vector-scoring

これは、ベクトルのbase64表現をインデクス登録することにより、ベクトルでスコアリングすることができるプラグインです。例えば、pythonでドキュメントベクトルを求めた場合、base64表現に変換するには以下の関数を使います。

import base64
import numpy as np

dbig = np.dtype('>f8')

def encode_array(arr):
    base64_str = base64.b64encode(np.array(arr).astype(dbig)).decode("utf-8")
    return base64_str

あとは、この関数でエンコーディングしたベクトルを以下のように登録するだけです:

{
    "id": 1,
    ....
    "embedding_vector": "v7l48eAAAAA/s4VHwAAAAD+R7I5AAAAAv8MBMAAAAAA/yEI3AAAAAL/IWkeAAAAAv7s480AAAAC/v6DUgAAAAL+wJi0gAAAAP76VqUAAAAC/sL1ZYAAAAL/dyq/gAAAAP62FVcAAAAC/tQRvYAAAAL+j6ycAAAAAP6v1KcAAAAC/bN5hQAAAAL+u9ItAAAAAP4ckTsAAAAC/pmkjYAAAAD+cYpwAAAAAP5renEAAAAC/qY0HQAAAAD+wyYGgAAAAP5WrCcAAAAA/qzjTQAAAAD++LBzAAAAAP49wNKAAAAC/vu/aIAAAAD+hqXfAAAAAP4FfNCAAAAA/pjC64AAAAL+qwT2gAAAAv6S3OGAAAAC/gfMtgAAAAD/If5ZAAAAAP5mcXOAAAAC/xYAU4AAAAL+2nlfAAAAAP7sCXOAAAAA/petBIAAAAD9soYnAAAAAv5R7X+AAAAC/pgM/IAAAAL+ojI/gAAAAP2gPz2AAAAA/3FonoAAAAL/IHg1AAAAAv6p1SmAAAAA/tvKlQAAAAD/I2OMAAAAAP3FBiCAAAAA/wEd8IAAAAL94wI9AAAAAP2Y1IIAAAAA/rnS4wAAAAL9vriVgAAAAv1QxoCAAAAC/1/qu4AAAAL+inZFAAAAAv7aGA+AAAAA/lqYVYAAAAD+kNP0AAAAAP730BiAAAAA="
}

ちなみに、embedding_vectorのテンプレートは以下のように定義します:

   {
        "embedding_vector": {
        "type": "binary",
        "doc_values": true
   }

検索の際には、以下のようなクエリを送信するだけです:

{
  "query": {
    "function_score": {
      "boost_mode": "replace",
      "script_score": {
        "lang": "knn",
        "params": {
          "cosine": false,
          "field": "embedding_vector",
          "vector": [
               -0.09217305481433868, 0.010635560378432274, -0.02878434956073761, 0.06988169997930527, 0.1273992955684662, -0.023723633959889412, 0.05490724742412567, -0.12124507874250412, -0.023694118484854698, 0.014595639891922474, 0.1471538096666336, 0.044936809688806534, -0.02795785665512085, -0.05665992572903633, -0.2441125512123108, 0.2755320072174072, 0.11451690644025803, 0.20242854952812195, -0.1387604922056198, 0.05219579488039017, 0.1145530641078949, 0.09967200458049774, 0.2161576747894287, 0.06157230958342552, 0.10350126028060913, 0.20387393236160278, 0.1367097795009613, 0.02070528082549572, 0.19238869845867157, 0.059613026678562164, 0.014012521132826805, 0.16701748967170715, 0.04985826835036278, -0.10990987718105316, -0.12032567709684372, -0.1450948715209961, 0.13585780560970306, 0.037511035799980164, 0.04251480475068092, 0.10693439096212387, -0.08861573040485382, -0.07457160204648972, 0.0549330934882164, 0.19136285781860352, 0.03346432000398636, -0.03652812913060188, -0.1902569830417633, 0.03250952064990997, -0.3061246871948242, 0.05219300463795662, -0.07879918068647385, 0.1403723508119583, -0.08893408626317978, -0.24330253899097443, -0.07105310261249542, -0.18161986768245697, 0.15501035749912262, -0.216160386800766, -0.06377710402011871, -0.07671763002872467, 0.05360138416290283, -0.052845533937215805, -0.02905619889497757, 0.08279753476381302
             ]
        },
        "script": "binary_vector_score"
      }
    }
  },
  "size": 100
}

サンプルコード

サンプルコードは以下で公開しました。 https://github.com/sugiyamath/personalized_search_example2

flaskでプロトタイプを作成し、app.pyは以下のように書いています:

#!/usr/bin/python3
# coding:utf-8

import sys
sys.path.append("../module")

import os
import re
import time
import numpy as np
import sqlite3
from elasticsearch import Elasticsearch
import search
from flask import Flask, jsonify, request, abort, render_template, make_response

db_root = "../db/"
app = Flask(__name__, template_folder='templates')
app.config['JSON_AS_ASCII'] = False
es = Elasticsearch("localhost:9202")
user_vector = []
user_vector.append([0.01 for x in range(128)])

@app.route('/search', methods=['GET'])
def search_it():
    global user_vector
    if not request.args:
        pages = []
        words = ['']
    else:
        query = request.args.get('q')
        qtype = request.args.get('qtype')
        if query.strip() == '' and qtype != '0':
            pages = []
            words = ['']
        else:
            conn = sqlite3.connect(os.path.join(db_root, 'mainichi.db'))
            if qtype == '1':
                terms = query.replace('%20',' ').replace(' ',' ')
                words = terms.split()
                pages = search.search(es, conn, terms, np.mean(user_vector,axis=0).tolist())
            elif qtype == '0':
                words = ['']
                pages = search.search_by_uv(es, conn, np.mean(user_vector, axis=0).tolist())

    return render_template('search.html', pages=pages, words=words)

@app.route('/redirect', methods=['GET'])
def redirect():
    global user_vector
    if not request.args:
        render_template('search.html', pages=[], words=[''])
    else:
        conn = sqlite3.connect(os.path.join(db_root, 'mainichi.db'))
        idx = request.args.get('id')
        url = request.args.get('url')
        article_vector = search.get_vector(conn, idx)
        user_vector.append(article_vector)
        user_vector.reverse()
        user_vector = user_vector[:10]
        user_vector.reverse()
        return render_template('redirect.html', url=url)

if __name__ == '__main__':
    app.run(debug=True, port=5504, host="0.0.0.0", threaded=True)

ただし、ユーザ数は1人を想定したものです。プロトタイプなので、多少コード的にマズイ部分もありますが、許してください。(例えば、グローバル変数の定義でflask.gを使っていないこと。)

参考

[1] https://github.com/lior-k/fast-elasticsearch-vector-scoring