| 8月9日(火) | 8月10日(水) |
山田 誠京都大学
Beyond Ranking: Optimizing Whole-Page Presentation（WSDM’16）
近年の検索エンジンにおいては、ウェブページ、ニュース、画像、ビデオ、ショッピング、ノレッジカード、地図等の複数の情報をまとめて表示しており、ウェブページを10件表示するような従来の検索エンジンと異なり、検索結果は多種多様なデータの組み合わせとなっている。そのため、ウェブページをただランキングするだけではなく、複数のデータソースの検索結果の配置をユーザーの興味を引くように効率良く配置することが重要である。本論文では、最適な検索結果のレイアウトをデータから最適化する枠組み(SERP)を提案する。
Modern search engines aggregate results from different verticals: webpages, news, images, video, shopping, knowledge cards, local maps, etc. Unlike ten blue links”, these search results are heterogeneous in nature and not even arranged in a list on the page. This revolution directly challenges the conventional ranked list” formulation in ad hoc search. Therefore, finding proper presentation for a gallery of heterogeneous results is critical for modern search engines. We propose a novel framework that learns the optimal page presentation to render heterogeneous results onto search result page (SERP).
吉田 悠一国立情報学研究所
Nonlinear Laplacian for Digraphs and its Applications to Network Analysis（WSDM’16）
本研究では、非線形ラプラシアンと呼ばれる、有向グラフに対する新しいマルコフ作用素を導入する。既存の有向グラフに対するラプラシアンと異なり、非線形ラプラシアンはランダムウォークの定常分布に依存しないため、強連結でない有向グラフにも定義される。次に、非線形ラプラシアンには非自明な固有値が存在することを示し、また、非自明な固有値と有向グラフのコンダクタンスを関係付けるCheeger不等式が成り立つことを示す。最後に、実ネットワークに対して非線形ラプラシアンを適用し、有用な結果が得られることを示す。
In this work, we introduce a new Markov operator associated with a digraph, which we refer to as a nonlinear Lapla- cian. Unlike previous Laplacians for digraphs, the nonlinear Laplacian does not rely on the stationary distribution of the random walk process and is well defined on digraphs that are not strongly connected. We show that the nonlinear Laplacian has nontrivial eigenvalues and give a Cheeger-like inequality, which relates the conductance of a digraph and the smallest non-zero eigenvalue of its nonlinear Laplacian. Finally, we apply the nonlinear Laplacian to the analysis of real-world networks and obtain encouraging results.
小西 卓哉国立情報学研究所
Identifying Key Observers to Find Popular Information in Advance（IJCAI’16）
ウェブサービスにおいて、将来注目される情報を前もって把握することは様々なメリットがある。こうした流行情報を、事前に察知する傾向があるユーザを観測者と呼び、ユーザの情報取得履歴から発見することを考える。本研究では、分類器の非負制約付きスパース推定による特徴選択を用いることで、有用な観測者の集合を発見する手法を提案する。実際のソーシャルブックマークデータを用いた評価実験により提案手法の有効性を示す。
Identifying soon-to-be-popular items in web services offers important benefits. We attempt to identify users who can find prospective popular items. Such visionary users are called observers. We propose a feature selection based framework to identify efficient observers. This uses a binary classifier with sparse and non-negative constraints to predict item popularity. In experiments, we test our approach using real social bookmark datasets. The results demonstrate that our approach can find more efficient observers than baseline methods.
江崎 貴裕国立情報学研究所
Reinforcement Learning Explains Conditional Cooperation and Its Moody Cousin（PLOS Computational Biology）
ネットワーク上で社会的ジレンマ状況に置かれた人間は、周囲にいる相手のうちどれだけの割合の相手が前回協力的な選択を行ったかによって次の自分の行動を大きく変えているということが、近年の繰り返し社会的ジレンマゲームの行動実験によって明らかになってきた。
一方、人間がなぜこのような条件付き協力と呼ばれる振る舞いを見せるのかは明らかになっていない。
本研究では強化学習の数理モデルを用いた数値計算によって、この振る舞いがどのようにして発生するかを説明することに成功した。特に、このような振る舞いを再現する強化学習ルールは、GRIM戦略と呼ばれる有名な行動原理の派生として理解することができることが分かった。
Behavioral experiments using repeated multiplayer social dilemma games on contact networks have revealed that players condition their decisions on the fraction of cooperative partners in the previous round of the repeated game. This behavior is referred to as the conditional cooperation. The origin of conditional cooperation and its moody variant still remains unclear. In this talk we provide a proximate explanation by numerical simulations. We show that players adopting a variant of the Bush-Mosteller reinforcement learning rule show the targeted behavior. We found that the reinforcement learners that showed (moody) conditional cooperation obeyed a behavioral pattern corresponding to the GRIM strategy, a well-known strategy in the repeated prisoner’s dilemma game.
馬場 雪乃京都大学
Assessing Translation Ability through Vocabulary Ability Assessment（IJCAI’16）
クラウドソーシング翻訳の作業割当において、翻訳者の能力推定は重要な課題である。従来の翻訳テストを利用した能力推定は、専門家による評価を必要とするため高コストである。我々は、語彙テストを利用した、手軽な翻訳能力推定法を提案する。 翻訳者にある英文中の単語の意味を知っているかどうかを聞き、その結果から翻訳能力を推定ための確率モデルを構築した。提案法を用いることで、翻訳作業と翻訳者のマッチングを効率的に行えることを実験で示した。
We propose a practical method for assessing translation ability. Our key idea is to incorporate translators’ vocabulary knowledge for translation ability assessment. Our method involves just asking translators to tell if they know given words. Using this vocabulary information, we build a probabilistic model to estimate the translators’ vocabulary and translation abilities simultaneously. The results of our experiments show that the proposed method accurately estimates translation ability and selects translators who have sufficient skills in translating a given sentence.
高濱 隆輔京都大学
Progressive Comparison for Ranking Estimation（IJCAI’16）
多数のオブジェクトのランキング推定のためのデータ収集にはしばしば一対比較法が用いられるが、一対比較法は1組の比較結果を得るたびに2つのオブジェクトの評価を必要とする。オブジェクトの評価にかかるコストは往々にして大きいため、本研究ではオブジェクトの評価回数を抑えつつ多数の比較結果を得るデータ収集法である漸進比較法と、その能動学習法をそれぞれ提案する。人工データおよび実データを用いた実験の結果、漸進比較法とその能動学習法は、一定のランキングの推定精度に達するために必要なオブジェクトの評価回数を減少させることに寄与することを確認した。
Object ranking is a problem that involves ordering given objects by aggregating pairwise comparison data collected from one or more evaluators; however, the cost of object evaluations is high in some applications. In this paper, we propose an efficient data collection method called progressive comparison, whose objective is to collect many pairwise comparison data while reducing the number of evaluations. We also propose active learning methods to determine which object should be evaluated next in the progressive comparison; we propose two measures of expected model changes, one considering the changes in the evaluation score distributions and the other considering the changes in the winning probabilities. The results of experiments using a synthetic dataset and two real datasets demonstrate that the progressive comparison method achieves high estimation accuracy with a smaller number of evaluations than the standard pairwise comparison method, and that the active learning methods further reduce the number of evaluations as compared with a random sampling method.
波多野 大督国立情報学研究所
Adaptive Budget Allocation for Maximizing Influence of Advertisements（IJCAI’16）
予算配分問題はオンライン広告を扱う上で重要な問題の一つである。本研究では、広告主が広告媒体に広告を出すための予算が限られている状態において、可能な限り多くの顧客に宣伝できるような広告媒体への予算配分を探したい。現実世界においては過去に出された広告の影響に基づき予算の配分を変更する方法がより一般的である。しかし、このような適応的に予算を配分する問題はこれまでに考えられていない。そこで本研究では、適応的な予算配分問題に対して鈍感戦略と呼ばれる貪欲法に基づく方法を提案し、その近似精度に理論保証を与えた。
The budget allocation problem is an optimization problem arising from advertising planning. In the problem, an advertiser has limited budgets to allocate across media, and seeks to optimize the allocation such that the largest fraction of customers can be influenced. It is known that this problem admits a (1 − 1/e)-approximation algorithm. However, no previous studies on this problem considered adjusting the allocation adaptively based upon the effect of the past campaigns, which is a usual strategy in the real setting. Our main contribution in this paper is to analyze adaptive strategies for the budget allocation problem. We define a greedy strategy, referred to as the insensitive policy, and then give a provable performance guarantee. This result is obtained by extending the adaptive submodularity, which is a concept studied in the context of active learning and stochastic optimization, to the functions over an integer lattice.
櫻井 保志熊本大学
Regime Shifts in Streams: Real-time Forecasting of Co-evolving Time Sequences（KDD’16）
Mining and Forecasting of Big Time-series Data（SIGMOD’15）
Non-Linear Mining of Competing Local Activities（WWW’16）
Mining Big Time-series Data on the Web（WWW’16）
近年のIoTデバイスの急速な普及に伴い、それらのデバイスから多様かつ大量のデータが生成され続けている。また、FacebookやTwitterなどの巨大なソーシャルネットワーク上を大量の情報が高速に流通するようになっている。増え続ける大規模なデータ、すなわち時系列ビッグデータを高速に解析する時系列データマイニング技術は非常に重要になっている。本講演では、講演者が取り組んでいる時系列ビッグデータ解析技術、特に非線形テンソル解析に基づく予測技術の研究を紹介する。さらに時系列ビッグデータ解析の応用例として、具体的な事例をいくつか紹介する。
Given a large collection of time series, such as web-click logs, electric medical records and motion capture sensors, how can we efficiently and effectively find typical patterns? How can we statistically summarize all the sequences, and achieve a meaningful segmentation? What are the major tools for forecasting and outlier detection? Time-series data analysis is becoming of increasingly high importance, thanks to the decreasing cost of hardware and the increasing on-line processing capability. The objective of this tutorial is to provide a concise and intuitive overview of the most important tools that can help us find patterns in large-scale time-series sequences. We review the state of the art in four related
fields: (1) similarity search and pattern discovery, (2) linear modeling and summarization, (3) non-linear modeling and forecasting, and (4) the extension of time-series mining and tensor analysis. The emphasis of the tutorial is to provide the intuition behind these powerful tools, which is usually lost in the technical literature, as well as to introduce case studies that illustrate their practical use.
竹内 一郎名古屋工業大学
Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining（KDD’16）
本論文では予測パターンマイニングの問題を考察する。予測パターンマイニングとはデータベースに含まれる予測に有用なパターンを用いたモデルである。本研究の主な貢献はセーフパターン枝刈り法と呼ぶ新たな方法を提案することである。提案法を用いると最適な予測モデルに使われるパターン集合の上位集合を見つけることができる。提案法の利点は、従来法が何度もデータベース内の探索を繰り返す必要があるのに対し、一度の探索で上位集合を見つけられる点である。提案法は、近年、機械学習分野で注目されているセーフスクリーニング法に基づいている。セーフスクリーニング法で使われている考え方をパターンマイニングの問題に適用するため、我々は新たなパターン木に対する枝刈り規則を導入した。この枝刈り規則を用いると、規則が満たされるノードの子孫ノードが最適な予測モデルにとって不要であることが保障できる。数値実験により提案法の有効性を検証する。
In this paper we study predictive pattern mining problems where the goal is to construct a predictive model based on a subset of predictive patterns in the database. Our main contribution is to introduce a novel method called safe pattern pruning (SPP) for a class of predictive pattern mining problems. The SPP method allows us to efficiently find a superset of all the predictive patterns in the database that are needed for the optimal predictive model. The advantage of the SPP method over existing boosting-type method is that the former can find the superset by a single search over the database, while the latter requires multiple searches. The SPP method is inspired by recent development of safe feature screening. In order to extend the idea of safe feature screening into predictive pattern mining, we derive a novel pruning rule called safe pattern pruning (SPP) rule that can be used for searching over the tree defined among patterns in the database. The SPP rule has a property that, if a node corresponding to a pattern in the database is pruned out by the SPP rule, then it is guaranteed that all the patterns corresponding to its descendant nodes are never needed for the optimal predictive model. We apply the SPP method to graph mining and item-set mining problems, and demonstrate its computational advantage.
田部井 靖生東京工業大学
Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices（KDD’16）
解釈可能な統計モデルをスケーラブルに学習するための新しいデータ行列の圧縮表現を提案する。
膨大な高次元実データを用いた実験により、 PLS回帰モデル学習における提案手法の有効性を示す。
We present a novel compressed representation of data matrices for learning statistical models with high interpretability.
Experiments using various massive high-dimensional data show that our method enables us to space-efficiently learn the linear model in PLS on the compressed representation of data matrices and our PLS performs superiorly in terms of prediction accuracy, computational efficiency, and interpretability.
秋葉 拓哉Preferred Networks
Compact and Scalable Graph Neighborhood Sketching（KDD’16）
頂点の重要度や頂点間の距離・関連度を求めることは、グラフ解析における最も基礎的な処理である。
集合に対する乱択スケッチ手法であるMin-wise Hashing (MinHash)をグラフに向け拡張した手法としてAll-Distances Sketches (ADS)がある。ADSはグラフの大きさに対しほぼ線形時間で全ての頂点について計算を行うことができ、ADSを用いると、頂点の重要度(Closeness Centrality)、頂点間の関連度(Closeness Similarity)、頂点間の距離などの推定を、誤差の理論的保証を伴って行うことができる。All-Distances Sketchesは理論的には非常に優れた性質を持っているため、実用化が強く期待される技術であった。しかし、実用的には、定数項の影響でデータ構造のサイズが非常に大きくなってしまい、大規模なグラフで使うことができないことが分かってきた。
そこで、本研究では、ADSに潜む冗長性に注目し、冗長性を取り除いたスケッチデータ構造である Sketch Retrieval Shortcuts (SRS)を提案する。SRSはADSから最大で10倍以上サイズが小さいが、SRSを計算しておけば、瞬時にADSと全く同じ精度での任意の推定を行うことができる。
The all-distances sketch (ADS) has recently emerged as a promising paradigm of graph neighborhood sketching. An ADS is a probabilistic data structure that is defined for each vertex of a graph. ADSs facilitate accurate estimation of many useful indicators for network analysis with the guarantee of accuracy, and the ADSs for all the vertices in a graph can be computed in near-linear time. Because of these useful properties, ADS has attracted considerable attention. However, a critical drawback of ADS is its space requirement, which tends to be much larger than that of the graph itself. In the present study, we address this issue by designing a new graph sketching scheme, namely, sketch retrieval shortcuts (SRS). Although SRSs are more space-efficient than ADSs by an order of magnitude, an ADS of any vertex can be quickly retrieved from the SRSs. The retrieved ADSs can be used to estimate the aforementioned indicators in exactly the same manner as with plain ADSs, inheriting the same accuracy guarantee. Our experiments on real-world networks demonstrate the usefulness of SRSs as a practical back-end of large-scale graph data mining.
相馬 輔東京大学
A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice（NIPS’15）
近年、劣モジュラ最適化は、様々な機械学習タスクに応用され注目を集めている。中でも、劣モジュラ被覆と呼ばれる問題は、文書要約やセンサー配置など多くの問題で共通に現れる定式化として知られている。
本研究では、劣モジュラ被覆に対して、整数格子点上の劣モジュラ性を用いた拡張を提案する。これにより、既存モデルでは捉えきれなかった複雑な状況も統一的に扱えるようになる。また、整数格子点上の劣モジュラ被覆に対して、効率的な近似アルゴリズムを提案し、拡張モデルでも高速に最適化が可能であることを示す。実データおよび大規模人工データを用いた数値実験も示す。
本研究は、NIIの吉田悠一准教授との共同研究である。
We consider a generalization of the submodular cover problem based on the concept of diminishing return property on the integer lattice. We are motivated by real scenarios in machine learning that cannot be captured by (traditional) submodular set functions. We show that the generalized submodular cover problem can be applied to various problems and devise a bicriteria approximation algorithm. Our algorithm is guaranteed to output a log-factor approximate solution that satisfies the constraints with the desired accuracy. The running time of our algorithm is roughly O(n\log (nr) \log{r}), where n is the size of the ground set and r is the maximum value of a coordinate. The dependency on r is exponentially better than the naive reduction algorithms. Several experiments on real and artificial datasets demonstrate that the solution quality of our algorithm is comparable to naive algorithms, while the running time is several orders of magnitude faster. This is joint work with Yuichi Yoshida.
今泉 允聡東京大学
Doubly Decomposing Nonparametric Tensor Regression（ICML’16）
テンソルを共変量とする非線形回帰の問題（テンソル回帰）に対して、新しいノンパラメトリックモデルおよび推定方法を提案する。テンソル回帰におけるノンパラメトリックな関数はテンソルの高次元性により複雑性が高いため、その推定量の収束が遅いことが知られている。本研究はその問題を回避するために、共変量と関数の両方に分解を施すことで回帰関数を局所関数の組み合わせで表現し、ガウス過程事前分布を用いてそれらをベイズ推定する手法を提案する。これらの分解によって回帰関数の複雑性を制御することで、問題だった推定量の収束の遅さを回避することが可能になる。推定量の収束はノンパラメトリック統計学の理論を用いて評価され、またその結果は人工データとネットワーク上の感染症に関する実データを用いた実験により裏付けられた。
Nonparametric extension of tensor regression is proposed. Nonlinearity in a high-dimensional tensor space is broken into simple local functions by incorporating low-rank tensor decomposition. Compared to naive nonparametric approaches, our formulation considerably improves the convergence rate of estimation while maintaining consistency with the same function class under specific conditions. To estimate local functions, we develop a Bayesian estimator with the Gaussian process prior. Experimental results show its theoretical properties and high performance in terms of predicting a summary statistic of a real complex network.
Song Liu統計数理研究所
Structure Learning of Partitioned Markov Networks（ICML’16）
We learn the structure of a Markov Network between two groups of random variables from joint observations. Since modelling and learning the full MN structure may be hard, learning the links between two groups directly may be a preferable option. We introduce a novel concept called the partitioned ratio whose factorization directly associates with the Markovian properties of random variables across two groups. A simple one-shot convex optimization procedure is proposed for learning the sparse factorizations of the partitioned ratio and it is theoretically guaranteed to recover the correct inter-group structure under mild conditions. The performance of the proposed method is experimentally compared with the state of the art MN structure learning methods using ROC curves. Real applications on analyzing bipartisanship in US congress and pairwise DNA/time-series alignments are also reported.
前原 貴憲静岡大学
Joint word representation learning using a corpus and a semantic lexicon（AAAI’16）
大規模なテキストコーパスから単語表現を学習することが現在高い注目を集めている。これらの表現は様々な自然言語処理タスクに対して高い性能を発揮することがわかっている。
ところが、これらの成功にも関わらず、データドリブンな単語学習法は単語同士の意味的関係を活用していない。一方で、単語同士の意味的関係については、WordNetなどの人手で整備したデータベース（レキシコン）が構築されている。
そこで本研究では、これらのレキシコンと大規模コーパスと組み合わせることで、よりよい単語表現が得られるかについて考えた。我々はレキシコンとコーパスを同時に学習するアルゴリズムを提案した。アルゴリズムは通常の、コーパスから単語を学習する際に用いる目的関数に対し、レキシコン上で関係があるとされた単語ベクトルが近くなるような正則化項を導入する。
提案手法は従来のコーパスとレキシコンを組み合わせる方法に比べて統計的優位に高性能を発揮した。
Methods for learning word representations using large text corpora have received much attention lately due to their impressive performance in numerous natural language processing (NLP) tasks such as, semantic similarity measurement, and word analogy detection.
Despite their success, these datadriven word representation learning methods do not consider the rich semantic relational structure between words in a cooccurring context.
On the other hand, already much manual effort has gone into the construction of semantic lexicons such as the WordNet that represent the meanings of words by defining the various relationships that exist among the words in a language.
We consider the question, can we improve the word representations learnt using a corpora by integrating the knowledge from semantic lexicons?.
For this purpose, we propose a joint word representation learning method that simultaneously predicts the co-occurrences of two words in a sentence subject to the relational constrains given by the semantic lexicon.
We use relations that exist between words in the lexicon to regularize the word representations learnt from the corpus.
Our proposed method statistically significantly outperforms previously proposed methods for incorporating semantic lexicons into word representations on several benchmark datasets for semantic similarity and word analogy.
林 浩平産業技術総合研究所
Expected Tensor Decomposition with Stochastic Gradient Descent（AAAI’16）
テンソル分解は高次の関係性を解析するための基礎的なツールとして位置づけられる。時系列ネットワークやテキストデータなど、いくつかの応用では解析対象となるテンソルはしばしば複数のテンソルの和で与えられるが、既存の方法では計算の前に一度全テンソルを積算する必要があり、スケーラビリティに問題があった。本発表では１つのテンソルが与えられるごとに逐次分解を更新するオンラインアルゴリズムを提案し、素早い収束や省メモリなど良い性質を持つことを理論的・実験的に示す。
In this study, we investigate expected CP decomposition — a special case of CP decomposition in which a tensor to be decomposed is given as the sum or average of tensor samples. To determine this decomposition, we develope stochastic-gradient-descent-type algorithms with four appealing features: efficient memory use, ability to work in an online setting, robustness of parameter tuning, and simplicity. Our theoretical analysis show that the solutions do not diverge to infinity for any initial value or step size. Experimental results confirm that our algorithms significantly outperform all existing methods in terms of accuracy. We also show that they can successfully decompose a large tensor, containing billion-scale nonzero elements.
福水 健次統計数理研究所
Persistence weighted Gaussian kernel for topological data analysis（ICML’16）
近年、データの位相的・幾何的情報を抽出する新しい方法として位相的データ解析（TDA）が注目されている。TDAにおいては位相情報の表現としてパーシステント図という2次元プロットがよく用いられる。
本研究では、意味のある位相構造とノイズとを分離し、TDAに系統的データ解析を導入する目的で、パーシステント図をベクトル化するための新しいカーネルを定義する。このカーネルに対し、計算上の問題と近似手法を議論するとともに、安定性定理を証明する。また、提案したカーネルを物質科学と生物データに適用し、従来法と比較して良好な結果が得られることを示す。
Topological data analysis (TDA) is an emerging mathematical method for extracting topological and geometrical information of data. In the method, a persistence diagram (PD), 2-D plot for illustrating the topology, is widely used as a descriptor of data.
In this work, we introduce a kernel method for PD to apply statistical methods systematically to TDA, aiming at flexibly distinguishing significant topological structures from noise. We also discuss a computational challenge of TDA, and propose an approximate computation method. As a theoretical background, a stability theorem is proved. The proposed kernel is applied to practical data analysis in materials science and biology, showing favorable results in comparison with other existing methods.
Mathieu BlondelNTTコミュニケーション科学基礎研究所
Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms（ICML’16）
Polynomial networks and factorization machines are two recently-proposed models that can efficiently use feature interactions in classification and regression tasks. In this paper, we revisit both models from a unified perspective. Based on this new view, we study the properties of both models and propose new efficient training algorithms. Key to our approach is to cast parameter learning as a low-rank symmetric tensor estimation problem, which we solve by multi-convex optimization. We demonstrate our approach on regression and recommender system tasks.
宮内 敦史東京工業大学
What Is a Network Community? A Novel Quality Function and Detection Algorithms（CIKM’15）
実社会に現れる多くのネットワークは、「コミュニティ」と呼ばれるまとまりらしい構造をもつ。与えられたネットワークからコミュニティを検出する手法は「コミュニティ検出法」と呼ばれ、その設計はネットワーク解析における中心的な研究課題である。本研究では、頂点部分集合のコミュニティらしさを評価するための関数を提案し、その関数を最大化する線形時間ヒューリスティックを設計した。計算機実験により、提案手法がコミュニティを高精度に検出することを確認した。
We introduce a novel quality function for a network community, which we refer to as the communitude. Specifically, it measures the Z-score of a subset of vertices S with respect to the fraction of the number of edges within the subgraph induced by S. To evaluate the detection ability of our quality function, we address the communitude maximization problem and its variants for realistic scenarios. For the problems, we propose a linear-time heuristic algorithm together with some modified versions. Computational experiments using both synthetic graphs and real-world networks demonstrate the validity of the proposed quality function and algorithms.
大坂 直人東京大学
Dynamic Influence Analysis in Evolving Networks（VLDB’16）
ソーシャルネットワーク上の「情報拡散」は、その大規模化にともない解析の重要性を増している。特に、バイラルマーケティングへの応用を動機づけとする (1)「影響力推定」＝ 頂点の影響力の推定問題と (2)「影響最大化」＝ 高影響力の頂点集合の抽出問題は、大規模グラフ上で解くための効率的手法が数多く提案されてきた。しかしながら、現実のソーシャルネットワークは動的であり急速に成長を続けている。したがって、最新のグラフにおける解析結果の獲得・追従が望ましいものの、既存の静的手法をグラフの構造変化の度に適用することは計算時間の観点で現実的ではない。
本研究は、成長するネットワークにおける影響解析のための実時間完全動的索引データ構造を提案する。提案手法は、頂点・辺の追加・削除を含むグラフの任意の更新を効率的に索引へ反映し、最新のグラフにおける「影響力推定」と「影響最大化」に更新した索引を用いて高速に答える。索引更新手法には影響力推定・影響最大化の精度を保ち続ける理論的保証がある。さらに、実性能向上のため、索引更新の効率化手法・索引サイズの削減手法を導入する。実データを用いた評価実験により、高速かつスケーラブルな索引構築・索引更新と効率的かつ高精度な影響力推定・影響最大化の達成を検証した。
We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks. With this aim, we carefully redesign the data structure of the state-of-the-art sketching method introduced by Borgs et al., and construct corresponding update algorithms. Using this index, we present algorithms for two kinds of queries, influence estimation and influence maximization, which are strongly motivated by practical applications, such as viral marketing. We provide a thorough theoretical analysis, which guarantees the non-degeneracy of the solution accuracy after an arbitrary number of updates. Furthermore, we introduce a reachability-tree-based technique and a skipping method, which greatly reduce the time consumption required for edge/vertex deletions and vertex additions, respectively, and counter-based random number generators, which improve the space efficiency.
Experimental evaluations using real dynamic networks with tens of millions of edges demonstrate the efficiency, scalability, and accuracy of our proposed indexing scheme. Specifically, it can reflect a graph modification within a time of several orders of magnitude smaller than that required to reconstruct an index from scratch, estimate the influence spread of a vertex set accurately within a millisecond, and select highly influential vertices at least ten times faster than state-of-the-art static algorithms.
垣村 尚徳東京大学
Exact and Approximation Algorithms for Weighted Matroid Intersection（SODA’16）
マトロイド交わり問題は基本的な組合せ最適化問題のひとつである。この問題は二部グラフの最大マッチング問題や有向グラフの有向木詰め込み問題などを特殊な場合として含み、また、電気回路解析やネットワーク符号化などさまざまな工学的応用を持つ。本講演では、重み付きマトロイド交わり問題に対する新しいアルゴリズムを提案する。提案アルゴリズムは最大重みが小さな場合に既存アルゴリズムより高速である。また、このアルゴリズムの枠組みは近似アルゴリズムの設計にも利用できる。
The weighted matroid intersection is a common generalization of various combinatorial optimization problems such as bipartite matchings, packing spanning trees, and arborescences in a directed graph. In this talk, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1-epsilon)-approximate solution with a running time significantly faster than most known exact algorithms.
平原 秀一東京大学
Limits of Minimum Circuit Size Problem as Oracle（CCC’16）
回路最小化問題（MCSP）は素因数分解などのNPの中間の問題よりは難しいことが知られている一方で、回路最小化問題がNP完全かどうかは計算量理論において重要な未解決問題である。本講演では、既存の帰着手法の単純な拡張では回路最小化問題のNP完全性を示すことができない、ということを証明する。具体的には、Oracle-independent帰着という既存の帰着手法を捉える概念を導入し、Oracle-independent帰着の限界を示す。
The Minimum Circuit Size Problem (MCSP) is known to be harder than NP-intermediate problems such as integer factorization. However, it is one of important open problems in computational complexity whether MCSP is NP-hard or not. In this talk, we prove that the current reduction techniques cannot establish NP-hardness of MCSP. Specifically, we introduce the notion of oracle-independent reduction, which captures current reduction techniques, and then we prove that oracle-independent reductions have certain inherent limits.
河村 彰星東京大学
A lower bound on opaque sets（SoCG'16）
与えられた図形に交るすべての直線に交る集合をその図形の遮光壁という。曲線可算本からなる単位正方形の遮光壁の全長が2.00002以上であることを示す。従来最良の下界は2であった。三角形以外の任意の凸図形の遮光壁についても同様の下界を得る。関連して図形を半直線の視線から掩蔽する最短の壁を探す問題についても述べる。
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. The best known lower bound has been 2. A similar bound is proved for all convex sets U other than a triangle.