| 8月3日（月） | 8月4日（火） |
林 浩平 （ＮＩＩ）
Real-time Top-R Topic Detection on Twitter with Topic Hijack Filtering (KDD’15)
Twitterは全世界で3億人が使うソーシャルメディアであり，「いま」に関するあらゆる情報を発信している．本発表では，Twitter上でどのようなことが話題になっているかをリアルタイムで抽出するシステムを提案する．具体的には，非負行列分解に確率勾配法を適用し，単位時間あたりの文字数に対して線形で動作するオンラインアルゴリズムを導出した．また，通常の単語分布がべき則に従うことを利用した，統計的検定を用いたスパム文の自動除去を同時に実装した．実際のTwitterストリームに適用し，実在のイベントに対応する話題が首尾よく抽出できたことを確認した．
Twitter is a “what’s-happening-right-now” tool that enables interested parties to follow thoughts and commentary of individual users in nearly real-time. While it is a valuable source of information for real-time topic detection and tracking, Twitter data are not clean because of noisy messages and users, which significantly diminish the reliability of obtained results.
In this paper, we integrate both the extraction of meaningful topics and the filtering of messages over the Twitter stream. We develop a streaming algorithm for a sequence of document-frequency tables; our algorithm enables real-time monitoring of the top-10 topics from approximately 25% of all Twitter messages, while automatically filtering noisy and meaningless topics. We apply our proposed streaming algorithm to the Japanese Twitter stream and successfully demonstrate that, compared with other online nonnegative matrix factorization methods, our framework both tracks real-world events with high accuracy in terms of the perplexity and simultaneously eliminates irrelevant topics.
小宮山 純平 （東京大学）
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (COLT’15)
バンディット問題（multi-armed bandit problem）は、情報の活用と探索の間のトレードオフをモデル化した問題である。バンディット問題にはいくつかの亜種があるが、そのうち比較バンディット問題（dueling bandit problem）と呼ばれるものは、一対比較によるフィードバックを用いて最適化を行う。比較バンディット問題の枠組みを用いることによって、検索エンジンのランキング手法の比較や、人間の選好抽出の問題に対して、効率的な最適化を行うことができる。本研究では、比較バンディット問題における理論的な性能限界およびそれを達成するアルゴリズムを提案する。提案手法を評価するため、検索エンジンの実データにおけるランキング手法の比較や、寿司データセット（神嶌，2003）などによる人間の選好抽出における性能を既存手法と比較する。
We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm is proposed and its regret is analyzed. The proposed algorithm is found to be the first one with a regret upper bound that matches the lower bound. Experimental comparisons of dueling bandit algorithms show that the proposed algorithm significantly outperforms existing ones.
前原 貴憲 （静岡大学）
Learning Word Representations from Relational Graphs (AAAI’15)
Embedding Semantic Relations into Word Representations (IJCAI’15)
単語をベクトルで表現することは自然言語処理における最も基本的な課題であり，最近は大規模テキストデータを利用し，周辺の単語を予測する問題を解くことでベクトル表現を学習する手法（word2vecなど）が注目を集めている．我々は「単語の意味的関係」に関する情報を利用することで，単にテキストデータだけを用いるよりも高品質なベクトル表現が得られることを示した．本発表ではこのトピックに関する２つの論文について説明する．
Representing words by vectors is a fundamental task in natural language processing, and recently, distributional representations with very large text data (eg., word2vec) attract much attention. We showed that, by combining information of “semantic relations,” higher quality word representations can be obtained. In this talk I give a talk about two papers related with this topic.
杉山 将 （東京大学）
Convex Formulation for Learning from Positive and Unlabeled Data (ICML’15)
正例とラベルなしデータだけから分類器を学習する新しいアルゴリズムを提案し，その有効性を理論的・実験的に示す．
We propose a novel algorithm for training a classifier only from positive and unlabeled data, and demonstrate its usefulness theoretically and experimentally.
宮内 敦史 （東京工業大学）
Threshold Influence Model for Allocating Advertising Budgets (ICML’15)
企業が自社の商品を PR するために広告を打つ状況を考える．テレビや新聞などの広告媒体に予算を配分すると，その効果で顧客が商品を購入することが予想されるが，こうした広告予算配分の影響はどのようにモデル化できるだろうか？本研究では，広告予算配分に対する新たなモデルとして，閾値影響モデルを提案する．提案モデルの特徴は，各顧客が広告の影響で購買行動に出るか否かを閾値的な振舞いとして捉えた点である．提案モデルの上で，予算制約付き影響最大化問題とコスト効率性最大化問題という二つの問題を定式化し，前者に対しては効率的な貪欲解法を，後者に対しては精度保証付き近似解法を設計した．最後に，数値実験によって提案解法の性能を検証した．
We propose a new influence model for allocating advertising budgets. Our model captures customer’s sensitivity to advertisements as a threshold behavior. Over our proposed model, we consider two optimization problems. The first one is the budget-constrained influence maximization. We design two greedy algorithms, and analyze the approximability for the submodular influence case. We then introduce a new characteristic to measure the performance of advertising budget allocation, which is called the cost-effectiveness. For the cost-effectiveness maximization, we design a fast approximation algorithm and an LP-based approximation algorithm. We conduct computational experiments to confirm that our algorithms outperform baseline algorithms.
恐神 貴行 （IBM東京基礎研究所）
Robust partially observable Markov decision process (ICML’15)
部分観測マルコフ決定過程のパラメタに不確実性がある場合に、最悪の場合に期待累積報酬を最大にする、ロバストな方策を算出する。
ロバストな方策によって得られる期待累積報酬を表すロバスト価値関数が凸になることを証明し、凸性に基づいて、価値反復アルゴリズムを設計する。
We seek to find the robust policy that maximizes the expected cumulative reward for the worst case when a partially observable Markov decision process (POMDP) has uncertain parameters whose values are only known to be in a given region. We prove that the robust value function, which represents the expected cumulative reward that can be obtained with the robust policy, is convex with respect to the belief state. Based on the convexity, we design a value-iteration algorithm for finding the robust policy. We prove that our value iteration converges for an infinite horizon. We also design point-based value iteration for fining the robust policy more efficiency possibly with approximation. Numerical experiments show that our point-based value iteration can adequately find robust policies.
Oussama Chelly （ＮＩＩ）
Estimating Local Intrinsic Dimensionality (KDD’15)
This work is concerned with the estimation of a local measure of intrinsic dimensionality (ID) recently proposed by Houle. The local model can be regarded as an extension of Karger and Ruhl’s expansion dimension to a statistical setting in which the distribution of distances to a query point is modeled in terms of a continuous random variable. This form of intrinsic dimensionality can be particularly useful in search, classification, outlier detection, and other contexts in machine learning, databases, and data mining, as it has been shown to be equivalent to a measure of the discriminative power of similarity functions. Several estimators of local ID are proposed and analyzed based on extreme value theory, using maximum likelihood estimation (MLE), the method of moments (MoM), probability weighted moments (PWM), and regularly varying functions (RV).
大坂 直人 （東京大学）
Efficient PageRank Tracking in Evolving Networks (KDD’15)
World Wide Webやソーシャルネットワーク等の現実のグラフは大規模かつ動的である．そのような動的グラフにおいて頂点の重要度・頂点間の関連度の指標であるPersonalized PageRankを追跡することはネットワーク解析やグラフマイニングへの応用において重要である．
本論文は，動的グラフにおいてPersonalized PageRankを効率的に計算するアルゴリズムを提案する．提案手法は，パラメータepsに対し，各Personalized PageRankスコアをeps以内の誤差で計算する．また，グラフの変化に対し，ならしO(1/eps)反復でPersonalized PageRankスコアを更新し，m辺が無作為に順次挿入された際には，更新にかかる総反復数の期待値がO(log m/eps)となる．
現実のグラフを用いた実験により，提案手法は，辺の挿入・削除に対し，1億頂点／37億辺を有するWebグラフ上では3マイクロ秒，4200万頂点／15億辺を有するソーシャルネットワーク上では20ミリ秒でPersonalized PageRankスコアを更新し，既存手法と同等以上の精度を保ちながら2-290倍の高速化を達成することを確認した．
Real-world networks, such as the World Wide Web and online social networks,are very large and are evolving rapidly. Thus tracking personalized PageRank in such evolving networks is an important challenge in network analysis and graph mining.
In this paper, we propose an efficient online algorithm for tracking personalized PageRank in an evolving network. The proposed algorithm tracks personalized PageRank accurately (i.e., within a given accuracy eps > 0). Moreover it can update the personalized PageRank scores in amortized O(1/eps) iterations for each graph modification.
In addition, when m edges are randomly and sequentially inserted, the total number of iterations is expected to be O(log m/eps).
We evaluated our algorithm in real-world networks. In average case, for each edge insertion and deletion, our algorithm updated the personalized PageRank in 3us in a web graph with 105M vertices and 3.7B edges, and 20ms in a social network with 42M vertices and 1.5B edges. By comparing existing state-of-the-arts algorithms, our algorithm is 2-290 times faster with an equal accuracy.
馬場 雪乃 （京都大学）
Predictive Approaches for Low-cost Preventive Medicine Program in Developing Countries (KDD’15)
非感染性疾患による死亡者増加が発展途上国でも深刻な問題となっている。予防医療が有効策だが、所得水準が低く医療従事者も不足している途上国においては、その普及は困難である。 我々は、バングラデシュにおけるヘルスケア大規模実験を実施し、その結果を用いて予防医療コスト削減に向けた３つの応用例で機械学習の有用性を示した：(1)低価格検査結果からの健康状態予測による、健康診断費用の削減、(2)次年度の健康状態予測による、経過観察コストの削減、(3)健康診断結果からの薬推薦による、医師の負荷軽減
Non-communicable diseases (NCDs) are no longer just a problem for high-income countries, but they are also a problem that affects developing countries. Preventive medicine is the key to combat NCDs; however, the cost is a critical issue in developing countries. We investigate predictive modeling for providing a low-cost preventive medicine program using the health checkup datasets collected in Bangladesh. Experimental results show the practicability of our predictive approaches in subject risk prediction, drug recommendation, and future risk prediction.
杉山 麿人 （大阪大学）
Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing (KDD’15)
アイテム集合や部分グラフのマイニングでは，これまで頻出パターンの発見が主な目的だった．本論文では，単に頻出するだけでなく，統計的に有意に頻出するパターンを全て列挙する手法 Westfall-Young light を提案する．これは，パターン列挙の高速化とパターン中の偽陽性の割合（FWER）の制御を同時に実現するために，検定可能性と呼ばれる統計的性質を用いた探索空間の削減と，permutation test を用いたFWERの制御を，パターンマイニングのアルゴリズムに統合した手法である．
We present a novel algorithm for significant pattern mining, Westfall-Young light. The target patterns are statistically significantly enriched in one of two classes of objects. Our method corrects for multiple hypothesis testing and correlations between patterns via the Westfall-Young permutation procedure, which empirically estimates the null distribution of pattern frequencies in each class via permutations.
