Journal of Artificial Intelligence Resarch: Volume 55の論文一覧

by

Journal of Artificial Intelligence Resarch Vol. 55 (2016)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

目次

論文

Introduction to the Special Issue on Cross-Language Algorithms and Applications

Introduction to the Special Issue on Cross-Language Algorithms and Applications / クロスランゲージアルゴリズムとアプリケーション特集号の紹介

With the increasingly global nature of our everyday interactions, the need for multilin- gual technologies to support efficient and effective information access and communication cannot be overemphasized. Computational modeling of language has been the focus of Natural Language Processing, a subdiscipline of Artificial Intelligence. One of the current challenges for this discipline is to design methodologies and algorithms that are cross- language in order to create multilingual technologies rapidly. The goal of this JAIR special issue on Cross-Language Algorithms and Applications (CLAA) is to present leading re- search in this area, with emphasis on developing unifying themes that could lead to the development of the science of multi- and cross-lingualism. In this introduction, we provide the reader with the motivation for this special issue and summarize the contributions of the papers that have been included. The selected papers cover a broad range of cross-lingual technologies including machine translation, domain and language adaptation for sentiment analysis, cross-language lexical resources, dependency parsing, information retrieval and knowledge representation. We anticipate that this special issue will serve as an invaluable resource for researchers interested in topics of cross-lingual natural language processing.



私たちの日常的な交流がますますグローバル化している中で、効率的かつ効果的な情報アクセスとコミュニケーションを支援するための多言語技術の必要性は、いくら強調してもし過ぎることはありません。言語の計算モデル化は、人工知能のサブ分野である自然言語処理の焦点となっています。この分野における現在の課題の一つは、多言語技術を迅速に構築するために、言語横断的な方法論とアルゴリズムを設計することです。JAIRのこの特集号「Cross-Language Algorithms and Applications (CLAA)」の目的は、この分野における最先端の研究を紹介することであり、特に多言語・異言語科学の発展につながる統一テーマの開発に重点を置きます。本稿では、特集号の趣旨を説明し、収録論文の概要を示します。選抜された論文は、機械翻訳、感情分析のためのドメインおよび言語適応、異言語語彙リソース、係り受け解析、情報検索、知識表現など、幅広い異言語技術を網羅しています。この特集号が、異言語自然言語処理のトピックに関心を持つ研究者にとって貴重なリソースとなることを期待しています。

Semi-supervised Learning with Induced Word Senses for State of the Art Word Sense Disambiguation

Semi-supervised Learning with Induced Word Senses for State of the Art Word Sense Disambiguation / 最先端の語義曖昧性解消のための誘導語義を用いた半教師あり学習

Word Sense Disambiguation (WSD) aims to determine the meaning of a word in context, and successful approaches are known to benefit many applications in Natural Language Processing. Although supervised learning has been shown to provide superior WSD performance, current sense-annotated corpora do not contain a sufficient number of instances per word type to train supervised systems for all words. While unsupervised techniques have been proposed to overcome this data sparsity problem, such techniques have not outperformed supervised methods. In this paper, we propose a new approach to building semi-supervised WSD systems that combines a small amount of sense-annotated data with information from Word Sense Induction, a fully-unsupervised technique that automatically learns the different senses of a word based on how it is used. In three experiments, we show how sense induction models may be effectively combined to ultimately produce high-performance semi-supervised WSD systems that exceed the performance of state-of-the-art supervised WSD techniques trained on the same sense-annotated data. We anticipate that our results and released software will also benefit evaluation practices for sense induction systems and those working in low-resource languages by demonstrating how to quickly produce accurate WSD systems with minimal annotation effort.



単語意味曖昧性解消(WSD)は、文脈における単語の意味を決定することを目的としており、成功したアプローチは自然言語処理の多くのアプリケーションにメリットをもたらすことが知られています。教師あり学習は優れたWSDパフォーマンスを提供することが示されていますが、現在の意味が注釈されたコーパスには、すべての単語について教師ありシステムをトレーニングするのに十分な数の単語ごとのインスタンスが含まれていません。このデータのスパース性の問題を克服するために教師なし手法が提案されていますが、そのような手法は教師あり方法を上回るパフォーマンスを発揮していません。本稿では、少量の意味が注釈されたデータと、単語の使用方法に基づいて単語のさまざまな意味を自動的に学習する完全な教師なし手法であるWord Sense Inductionからの情報を組み合わせた、半教師ありWSDシステムを構築する新しいアプローチを提案します。3つの実験では、意味誘導モデルを効果的に組み合わせて、最終的に同じ意味が注釈されたデータでトレーニングされた最先端の教師ありWSD手法のパフォーマンスを超える高性能な半教師ありWSDシステムを作成する方法を示します。私たちの成果とリリースされたソフトウェアは、最小限の注釈付け作業で正確なWSDシステムを迅速に作成する方法を実証することで、感覚誘導システムの評価方法やリソースの少ない言語で作業するシステムにも役立つと期待しています。

Learning Concept Graphs from Online Educational Data

Learning Concept Graphs from Online Educational Data / オンライン教育データからの概念グラフの学習

This paper addresses an open challenge in educational data mining, i.e., the problem of automatically mapping online courses from different providers (universities, MOOCs, etc.) onto a universal space of concepts, and predicting latent prerequisite dependencies (directed links) among both concepts and courses. We propose a novel approach for inference within and across course-level and concept-level directed graphs. In the training phase, our system projects partially observed course-level prerequisite links onto directed concept-level links; in the testing phase, the induced concept-level links are used to infer the unknown course-level prerequisite links. Whereas courses may be specific to one institution, concepts are shared across different providers. The bi-directional mappings enable our system to perform interlingua-style transfer learning, e.g. treating the concept graph as the interlingua and transferring the prerequisite relations across universities via the interlingua. Experiments on our newly collected datasets of courses from MIT, Caltech, Princeton and CMU show promising results.



本論文は、教育データマイニングにおける未解決の課題、すなわち、異なる提供元（大学、MOOCなど）のオンラインコースを普遍的な概念空間に自動的にマッピングし、概念とコース間の潜在的な前提条件依存関係（有向リンク）を予測するという問題に取り組みます。本論文では、コースレベルおよび概念レベルの有向グラフ内およびグラフ間で推論を行うための新しいアプローチを提案します。トレーニングフェーズでは、システムは部分的に観測されたコースレベルの前提条件リンクを有向概念レベルのリンクに投影します。テストフェーズでは、誘導された概念レベルのリンクを用いて、未知のコースレベルの前提条件リンクを推論します。コースは特定の機関に固有のものである可能性がありますが、概念は異なる提供元間で共有されています。双方向マッピングにより、本システムはインターリングア型の転移学習を実行できます。例えば、概念グラフをインターリングアとして扱い、インターリングアを介して前提条件関係を大学間で転移できます。MIT、Caltech、Princeton、CMUのコースのデータセットを新たに収集し、実験では有望な結果が得られました。

Semantic Visualization with Neighborhood Graph Regularization

Semantic Visualization with Neighborhood Graph Regularization / 近傍グラフによるセマンティック可視化正則化

Visualization of high-dimensional data, such as text documents, is useful to map out the similarities among various data points. In the high-dimensional space, documents are commonly represented as bags of words, with dimensionality equal to the vocabulary size. Classical approaches to document visualization directly reduce this into visualizable two or three dimensions. Recent approaches consider an intermediate representation in topic space, between word space and visualization space, which preserves the semantics by topic modeling. While aiming for a good fit between the model parameters and the observed data, previous approaches have not considered the local consistency among data instances. We consider the problem of semantic visualization by jointly modeling topics and visualization on the intrinsic document manifold, modeled using a neighborhood graph. Each document has both a topic distribution and visualization coordinate. Specifically, we propose an unsupervised probabilistic model, called SEMAFORE, which aims to preserve the manifold in the lower-dimensional spaces through a neighborhood regularization framework designed for the semantic visualization task. To validate the efficacy of SEMAFORE, our comprehensive experiments on a number of real-life text datasets of news articles and Web pages show that the proposed methods outperform the state-of-the-art baselines on objective evaluation metrics.



テキスト文書などの高次元データの可視化は、様々なデータポイント間の類似性をマッピングするのに役立ちます。高次元空間では、文書は通常、語彙サイズに等しい次元を持つ単語の集まりとして表現されます。文書可視化の従来のアプローチは、これを視覚化可能な2次元または3次元に直接縮小します。最近のアプローチでは、トピック空間（単語空間と可視化空間の中間表現）において、トピックモデリングによって意味を保持する中間表現が考慮されています。従来のアプローチは、モデルパラメータと観測データとの良好な適合を目指していますが、データインスタンス間の局所的な一貫性を考慮していませんでした。本研究では、近傍グラフを用いてモデル化された固有の文書多様体上で、トピックと可視化を共同でモデル化することにより、意味的可視化の問題を検討します。各文書は、トピック分布と可視化座標の両方を持ちます。具体的には、意味的可視化タスク用に設計された近傍正則化フレームワークを用いて、低次元空間における多様体を保持することを目的とする、SEMAFOREと呼ばれる教師なし確率モデルを提案します。SEMAFOREの有効性を検証するため、ニュース記事とWebページからなる多数の実世界のテキストデータセットを用いた包括的な実験を実施しました。その結果、提案手法が客観的な評価指標において最先端のベースラインを上回る性能を示すことが示されました。

Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks

Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks / 動的ベイジアンネットワークにおける選択的ビリーフフィルタリングのための因果関係の活用

Dynamic Bayesian networks (DBNs) are a general model for stochastic processes with partially observed states. Belief filtering in DBNs is the task of inferring the belief state (i.e. the probability distribution over process states) based on incomplete and noisy observations. This can be a hard problem in complex processes with large state spaces. In this article, we explore the idea of accelerating the filtering task by automatically exploiting causality in the process. We consider a specific type of causal relation, called passivity, which pertains to how state variables cause changes in other variables. We present the Passivity-based Selective Belief Filtering (PSBF) method, which maintains a factored belief representation and exploits passivity to perform selective updates over the belief factors. PSBF produces exact belief states under certain assumptions and approximate belief states otherwise, where the approximation error is bounded by the degree of uncertainty in the process. We show empirically, in synthetic processes with varying sizes and degrees of passivity, that PSBF is faster than several alternative methods while achieving competitive accuracy. Furthermore, we demonstrate how passivity occurs naturally in a complex system such as a multi-robot warehouse, and how PSBF can exploit this to accelerate the filtering task.



動的ベイジアンネットワーク（DBN）は、部分的に観測された状態を持つ確率過程の一般的なモデルです。DBNにおけるビリーフフィルタリングは、不完全でノイズの多い観測に基づいてビリーフ状態（つまり、プロセス状態全体の確率分布）を推論するタスクです。これは、大規模な状態空間を持つ複雑なプロセスでは困難な問題となる可能性があります。本稿では、プロセスにおける因果関係を自動的に活用することでフィルタリングタスクを高速化するというアイデアを検討します。本稿では、状態変数が他の変数の変化を引き起こす仕組みに関係する、受動性と呼ばれる特定の種類の因果関係を考察します。本稿では、因子分解されたビリーフ表現を維持し、受動性を利用してビリーフ因子に対して選択的な更新を実行する受動性に基づく選択的ビリーフフィルタリング（PSBF）手法を紹介します。PSBFは、特定の仮定の下では正確な確信状態を生成し、そうでない場合は近似的な確信状態を生成します。近似誤差は、プロセスにおける不確実性の程度によって制限されます。本研究では、様々なサイズと受動性の度合いを持つ合成プロセスにおいて、PSBFが他の手法よりも高速でありながら、競争力のある精度を達成することを実証的に示します。さらに、マルチロボット倉庫のような複雑なシステムにおいて受動性がどのように自然に発生するか、そしてPSBFがこれを利用してフィルタリングタスクを高速化する方法を示します。

Distributional Correspondence Indexing for Cross-Lingual and Cross-Domain Sentiment Classification.

Distributional Correspondence Indexing for Cross-Lingual and Cross-Domain Sentiment Classification. / クロスリンガルおよびクロスドメイン感情分類のための分布対応インデックス作成

Domain Adaptation (DA) techniques aim at enabling machine learning methods learn effective classifiers for a “target” domain when the only available training data belongs to a different “source” domain. In this paper we present the Distributional Correspondence Indexing (DCI) method for domain adaptation in sentiment classification. DCI derives term representations in a vector space common to both domains where each dimension reflects its distributional correspondence to a pivot, i.e., to a highly predictive term that behaves similarly across domains. Term correspondence is quantified by means of a distributional correspondence function (DCF). We propose a number of efficient DCFs that are motivated by the distributional hypothesis, i.e., the hypothesis according to which terms with similar meaning tend to have similar distributions in text. Experiments show that DCI obtains better performance than current state-of-the-art techniques for cross-lingual and cross-domain sentiment classification. DCI also brings about a significantly reduced computational cost, and requires a smaller amount of human intervention. As a final contribution, we discuss a more challenging formulation of the domain adaptation problem, in which both the cross-domain and cross-lingual dimensions are tackled simultaneously.



ドメイン適応（DA）技術は、利用可能なトレーニングデータが「ソース」ドメインと異なるドメインに属する場合に、機械学習手法が「ターゲット」ドメインに適した効果的な分類器を学習できるようにすることを目的としています。本稿では、感情分類におけるドメイン適応のための分布対応インデックス（DCI）法を紹介します。DCIは、両ドメインに共通のベクトル空間における用語表現を導出します。各次元は、ピボット（つまり、ドメイン間で同様に振る舞う予測性の高い用語）への分布対応を反映します。用語の対応は、分布対応関数（DCF）によって定量化されます。本稿では、分布仮説、つまり、意味が類似する用語はテキスト内で同様の分布を示す傾向があるという仮説に基づいた、いくつかの効率的なDCFを提案します。実験では、DCIがクロスリンガルおよびクロスドメイン感情分類において、現在の最先端技術よりも優れた性能を示すことが示されています。また、DCIは計算コストを大幅に削減し、人的介入の必要性も低減します。最終的な貢献として、ドメイン適応問題のより困難な定式化について議論します。この定式化では、ドメイン間および言語間の両方の側面を同時に扱う。

Effectiveness of Automatic Translations for Cross-Lingual Ontology Mapping

Effectiveness of Automatic Translations for Cross-Lingual Ontology Mapping / クロスリンガルオントロジーマッピングにおける自動翻訳の有効性

Accessing or integrating data lexicalized in different languages is a challenge. Multilingual lexical resources play a fundamental role in reducing the language barriers to map concepts lexicalized in different languages. In this paper we present a large-scale study on the effectiveness of automatic translations to support two key cross-lingual ontology mapping tasks: the retrieval of candidate matches and the selection of the correct matches for inclusion in the final alignment. We conduct our experiments using four different large gold standards, each one consisting of a pair of mapped wordnets, to cover four different families of languages. We categorize concepts based on their lexicalization (type of words, synonym richness, position in a subconcept graph) and analyze their distributions in the gold standards. Leveraging this categorization, we measure several aspects of translation effectiveness, such as word-translation correctness, word sense coverage, synset and synonym coverage. Finally, we thoroughly discuss several findings of our study, which we believe are helpful for the design of more sophisticated cross-lingual mapping algorithms.



異なる言語で語彙化されたデータへのアクセスや統合は課題です。多言語語彙リソースは、異なる言語で語彙化された概念をマッピングする際の言語障壁を低減する上で基本的な役割を果たす。本論文では、候補マッチの検索と最終アラインメントに含める正しいマッチの選択という、2つの主要なクロスリンガルオントロジーマッピングタスクをサポートする自動翻訳の有効性に関する大規模な研究を示す。実験は、4つの異なる言語ファミリーをカバーするために、それぞれがマッピングされたワードネットのペアで構成される4つの異なる大規模なゴールドスタンダードを用いて行う。概念を語彙化（単語の種類、同義語の豊富さ、サブコンセプトグラフにおける位置）に基づいて分類し、ゴールドスタンダードにおけるそれらの分布を分析します。この分類を利用して、単語翻訳の正確さ、語義の網羅性、シノニムセットと同義語の網羅性など、翻訳の有効性のいくつかの側面を測定します。最後に、より洗練されたクロスリンガルマッピングアルゴリズムの設計に役立つと思われる、本研究のいくつかの発見について徹底的に議論します。

Integrating Rules and Dictionaries from Shallow-Transfer Machine Translation into Phrase-Based Statistical Machine Translation

Integrating Rules and Dictionaries from Shallow-Transfer Machine Translation into Phrase-Based Statistical Machine Translation / 浅い転移機械翻訳のルールと辞書をフレーズベース統計機械翻訳に統合

We describe a hybridisation strategy whose objective is to integrate linguistic resources from shallow-transfer rule-based machine translation (RBMT) into phrase-based statistical machine translation (PBSMT). It basically consists of enriching the phrase table of a PBSMT system with bilingual phrase pairs matching transfer rules and dictionary entries from a shallow-transfer RBMT system. This new strategy takes advantage of how the linguistic resources are used by the RBMT system to segment the source-language sentences to be translated, and overcomes the limitations of existing hybrid approaches that treat the RBMT systems as a black box. Experimental results confirm that our approach delivers translations of higher quality than existing ones, and that it is specially useful when the parallel corpus available for training the SMT system is small or when translating out-of-domain texts that are well covered by the RBMT dictionaries. A combination of this approach with a recently proposed unsupervised shallow-transfer rule inference algorithm results in a significantly greater translation quality than that of a baseline PBSMT; in this case, the only hand-crafted resource used are the dictionaries commonly used in RBMT. Moreover, the translation quality achieved by the hybrid system built with automatically inferred rules is similar to that obtained by those built with hand-crafted rules.



浅い転移ルールベース機械翻訳（RBMT）の言語リソースをフレーズベース統計機械翻訳（PBSMT）に統合することを目的としたハイブリッド化戦略について説明します。これは基本的に、浅い転移RBMTシステムの転移ルールと辞書エントリに一致するバイリンガルフレーズペアでPBSMTシステムのフレーズテーブルを拡充することから構成されます。この新しい戦略は、RBMTシステムが言語リソースを使用して翻訳対象のソース言語の文をセグメント化する方法を活用し、RBMTシステムをブラックボックスとして扱う既存のハイブリッドアプローチの限界を克服します。実験結果から、本手法は既存の手法よりも高品質な翻訳を実現することが確認されました。特に、SMTシステムの学習に利用可能な対訳コーパスが小さい場合や、RBMT辞書で十分にカバーされている分野外のテキストを翻訳する場合に有効です。この手法を、最近提案された教師なしの浅い転移ルール推論アルゴリズムと組み合わせることで、ベースラインPBSMTよりも大幅に優れた翻訳品質が得られます。この場合、手作業で作成されたリソースは、RBMTで一般的に使用される辞書のみです。さらに、自動推論ルールで構築されたハイブリッドシステムによって達成された翻訳品質は、手作業で作成されたルールで構築されたシステムと同等です。

Synthetic Treebanking for Cross-Lingual Dependency Parsing

Synthetic Treebanking for Cross-Lingual Dependency Parsing / クロスリンガル係り受け解析のための合成ツリーバンキング

How do we parse the languages for which no treebanks are available? This contribution addresses the cross-lingual viewpoint on statistical dependency parsing, in which we attempt to make use of resource-rich source language treebanks to build and adapt models for the under-resourced target languages. We outline the benefits, and indicate the drawbacks of the current major approaches. We emphasize synthetic treebanking: the automatic creation of target language treebanks by means of annotation projection and machine translation. We present competitive results in cross-lingual dependency parsing using a combination of various techniques that contribute to the overall success of the method. We further include a detailed discussion about the impact of part-of-speech label accuracy on parsing results that provide guidance in practical applications of cross-lingual methods for truly under-resourced languages.



ツリーバンクが利用できない言語をどのように解析するのか？本稿では、統計的係り受け解析におけるクロスリンガルな観点を取り上げ、リソースが豊富なソース言語のツリーバンクを利用して、リソースが不足しているターゲット言語用のモデルを構築・適応させる試みを行う。現在の主要なアプローチの利点を概説し、欠点を示す。特に、アノテーション投影と機械翻訳によってターゲット言語のツリーバンクを自動的に作成する合成ツリーバンキングに重点を置く。本稿では、この手法の全体的な成功に貢献する様々な手法を組み合わせたクロスリンガル係り受け解析において、競争力のある結果を示す。さらに、品詞ラベルの精度が解析結果に与える影響についても詳細に議論し、リソースが不足している言語に対するクロスリンガル手法の実際的な適用の指針を提供します。

Utilisation of Metadata Fields and Query Expansion in Cross-Lingual Search of User-Generated Internet Video

Utilisation of Metadata Fields and Query Expansion in Cross-Lingual Search of User-Generated Internet Video / ユーザー生成インターネット動画のクロスリンガル検索におけるメタデータフィールドとクエリ拡張の活用

Recent years have seen significant efforts in the area of Cross Language Information Retrieval (CLIR) for text retrieval. This work initially focused on formally published content, but more recently research has begun to concentrate on CLIR for informal social media content. However, despite the current expansion in online multimedia archives, there has been little work on CLIR for this content. While there has been some limited work on Cross-Language Video Retrieval (CLVR) for professional videos, such as documentaries or TV news broadcasts, there has to date, been no significant investigation of CLVR for the rapidly growing archives of informal user generated (UGC) content. Key differences between such UGC and professionally produced content are the nature and structure of the textual UGC metadata associated with it, as well as the form and quality of the content itself. In this setting, retrieval effectiveness may not only suffer from translation errors common to all CLIR tasks, but also recognition errors associated with the automatic speech recognition (ASR) systems used to transcribe the spoken content of the video and with the informality and inconsistency of the associated user-created metadata for each video. This work proposes and evaluates techniques to improve CLIR effectiveness of such noisy UGC content. Our experimental investigation shows that different sources of evidence, e.g. the content from different fields of the structured metadata, significantly affect CLIR effectiveness. Results from our experiments also show that each metadata field has a varying robustness to query expansion (QE) and hence can have a negative impact on the CLIR effectiveness. Our work proposes a novel adaptive QE technique that predicts the most reliable source for expansion and shows how this technique can be effective for improving the CLIR effectiveness for UGC content.



近年、テキスト検索のためのクロスランゲージ情報検索（CLIR）の分野で多大な努力が行われています。当初は正式に出版されたコンテンツに焦点を当てていたが、最近では非公式なソーシャルメディアコンテンツのCLIRに研究が集中し始めています。しかし、オンライン マルチメディア アーカイブの現在の拡大にもかかわらず、このコンテンツに対するCLIRに関する研究はほとんど行われていません。ドキュメンタリーやテレビ ニュース放送などのプロフェッショナル ビデオに対するCross-Language Video Retrieval (CLVR)に関する研究は限定的ですが、急速に増加している非公式なユーザー生成コンテンツ(UGC)アーカイブに対するCLVRの重要な調査はこれまで行われていません。このようなUGCとプロフェッショナルに制作されたコンテンツとの主な違いは、UGCに関連付けられたテキスト メタデータの性質と構造、およびコンテンツ自体の形式と品質です。このような設定では、検索の有効性は、すべてのCLIRタスクに共通する翻訳エラーだけでなく、ビデオの音声コンテンツの書き起こしに使用される自動音声認識(ASR)システムに関連する認識エラー、および各ビデオに関連付けられたユーザー作成メタデータの非公式性と不一致によっても影響を受ける可能性があります。本研究では、このようなノイズの多いUGCコンテンツのCLIR有効性を向上させる手法を提案し、評価します。実験的調査により、たとえば、次のようなさまざまな証拠源が示されています。構造化メタデータの異なるフィールドのコンテンツは、CLIRの有効性に大きな影響を与えます。実験の結果から、各メタデータ フィールドはクエリ拡張(QE)に対する堅牢性が異なるため、CLIRの有効性に悪影響を与える可能性があることもわかりました。私たちの研究では、拡張のための最も信頼できるソースを予測する新しい適応型QE手法を提案し、この手法がUGCコンテンツのCLIRの有効性を向上させるのにどのように効果的であるかを示します。

News Across Languages – Cross-Lingual Document Similarity and Event Tracking

News Across Languages – Cross-Lingual Document Similarity and Event Tracking / 言語間のニュース – クロスリンガル文書の類似性とイベント追跡

In today’s world, we follow news which is distributed globally. Significant events are reported by different sources and in different languages. In this work, we address the problem of tracking of events in a large multilingual stream. Within a recently developed system Event Registry we examine two aspects of this problem: how to compare articles in different languages and how to link collections of articles in different languages which refer to the same event. Taking a multilingual stream and clusters of articles from each language, we compare different cross-lingual document similarity measures based on Wikipedia. This allows us to compute the similarity of any two articles regardless of language. Building on previous work, we show there are methods which scale well and can compute a meaningful similarity between articles from languages with little or no direct overlap in the training data. Using this capability, we then propose an approach to link clusters of articles across languages which represent the same event. We provide an extensive evaluation of the system as a whole, as well as an evaluation of the quality and robustness of the similarity measure and the linking algorithm.



今日の世界では、私たちは世界中に配信されるニュースをフォローしています。重要なイベントは、さまざまなソースとさまざまな言語で報告されています。この研究では、大規模な多言語ストリーム内のイベントの追跡の問題に取り組みます。最近開発されたシステムEvent Registryでは、この問題の2つの側面、つまり異なる言語の記事を比較する方法と、同じイベントに言及する異なる言語の記事のコレクションをリンクする方法を調べます。多言語ストリームと各言語の記事のクラスターを取り、Wikipediaに基づくさまざまな言語間ドキュメント類似度尺度を比較します。これにより、言語に関係なく、任意の2つの記事の類似度を計算できます。先行研究に基づき、学習データにおいて直接的な重複がほとんど、あるいは全くない言語の記事間でも、スケール性に優れ、意味のある類似度を計算できる手法があることを示す。さらに、この機能を用いて、同じ事象を表す複数の言語の記事クラスターをリンクする手法を提案します。システム全体の広範な評価に加え、類似度指標とリンクアルゴリズムの品質と堅牢性についても評価します。

Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems

Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems / クラウドソーシング市場のための適応型契約設計：反復プリンシパル・エージェント問題のためのバンディットアルゴリズム

Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task’s requester, and may be adjusted based on the quality of the completed work, for example, through the use of “bonus” payments. In this paper, we study the requester’s problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each “arm” representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.



クラウドソーシング市場は、利用可能な労働者と完了すべきタスクをマッチングさせる人気のプラットフォームとして台頭しています。特定のタスクに対する報酬は通常、タスクの依頼者によって設定され、完了した作業の品質に基づいて調整されることもあります（例えば、「ボーナス」支払いなど）。本稿では、タスクに対する品質依存型報酬を依頼者が動的に調整するという問題を考察します。よく知られているプリンシパル・エージェント・モデルのマルチラウンド版を考察します。このモデルでは、各ラウンドにおいて、労働者は依頼者から直接観察できない労力レベルを戦略的に選択します。特に、本稿の定式化は、先行研究で研究された予算フリーのオンラインタスク価格設定問題を大幅に一般化します。この問題を多腕バンディット問題として扱い、各「腕」は潜在的な契約を表します。多数の（そして実際には無限の）腕に対処するために、契約空間を有限個の領域に離散化し、各領域を実質的に単一の腕として扱う新しいアルゴリズム、AgnosticZoomingを提案します。この離散化は適応的に改良され、契約空間のより有望な領域が最終的により細かく離散化されます。我々はこのアルゴリズムを解析し、時間範囲において後悔が線形以下となり、非適応的離散化（文献で唯一の競合アプローチ）よりも大幅に改善されることを示す。我々の結果は、クラウドソーシング市場の理論、プリンシパル・エージェント問題、多腕バンディット、動的価格設定といった、いくつかの異なるトピックにおける最先端技術を前進させるものです。

Bayesian Optimization in a Billion Dimensions via Random Embeddings

Bayesian Optimization in a Billion Dimensions via Random Embeddings / ランダム埋め込みによる10億次元ベイズ最適化

Bayesian optimization techniques have been successfully applied to robotics, planning, sensor placement, recommendation, advertising, intelligent user interfaces and automatic algorithm configuration. Despite these successes, the approach is restricted to problems of moderate dimension, and several workshops on Bayesian optimization have identified its scaling to high-dimensions as one of the holy grails of the field. In this paper, we introduce a novel random embedding idea to attack this problem. The resulting Random EMbedding Bayesian Optimization (REMBO) algorithm is very simple, has important invariance properties, and applies to domains with both categorical and continuous variables. We present a thorough theoretical analysis of REMBO. Empirical results confirm that REMBO can effectively solve problems with billions of dimensions, provided the intrinsic dimensionality is low. They also show that REMBO achieves state-of-the-art performance in optimizing the 47 discrete parameters of a popular mixed integer linear programming solver.



ベイズ最適化手法は、ロボット工学、計画、センサー配置、推奨、広告、インテリジェントユーザーインターフェース、自動アルゴリズム設定などに効果的に適用されてきた。これらの成功にもかかわらず、このアプローチは中程度の次元の問題に限定されており、ベイズ最適化に関するいくつかのワークショップでは、高次元へのスケーリングがこの分野の聖杯の1つであるとされています。本稿では、この問題に取り組むための新しいランダム埋め込みのアイデアを紹介します。結果として得られるランダム埋め込みベイズ最適化（REMBO）アルゴリズムは非常に単純で、重要な不変性を持ち、カテゴリ変数と連続変数の両方を含む領域に適用できます。本稿ではREMBOの徹底的な理論的分析を示します。実験結果により、固有次元が低い場合、REMBOは数十億次元の問題を効果的に解くことができることが確認されました。また、REMBOは、一般的な混合整数線形計画ソルバーの47個の離散パラメータの最適化において最先端のパフォーマンスを達成することも示しています。

Predicting Twitter User Demographics using Distant Supervision from Website Traffic Data

Predicting Twitter User Demographics using Distant Supervision from Website Traffic Data / ウェブサイトトラフィックデータからの遠隔教師を用いたTwitterユーザーの人口統計予測

Understanding the demographics of users of online social networks has important applications for health, marketing, and public messaging. Whereas most prior approaches rely on a supervised learning approach, in which individual users are labeled with demographics for training, we instead create a distantly labeled dataset by collecting audience measurement data for 1,500 websites (e.g., 50% of visitors to gizmodo.com are estimated to have a bachelor’s degree). We then fit a regression model to predict these demographics from information about the followers of each website on Twitter. Using patterns derived both from textual content and the social network of each user, our final model produces an average held-out correlation of .77 across seven different variables (age, gender, education, ethnicity, income, parental status, and political preference). We then apply this model to classify individual Twitter users by ethnicity, gender, and political preference, finding performance that is surprisingly competitive with a fully supervised approach.



オンラインソーシャルネットワークのユーザーの人口統計を理解することは、健康、マーケティング、および公共メッセージングへの重要な応用があります。従来のアプローチのほとんどは、個々のユーザーにトレーニング用の人口統計ラベルを付ける教師あり学習アプローチに依存していますが、本稿では代わりに1,500のウェブサイトの視聴者測定データを収集することにより、遠隔的にラベル付けされたデータセットを作成します（例：gizmodo.comへの訪問者の50%は学士号を取得していると推定されます）。次に、Twitter上の各ウェブサイトのフォロワー情報からこれらの人口統計を予測する回帰モデルを当てはめました。各ユーザーのテキストコンテンツとソーシャルネットワークの両方から得られたパターンを用いた最終モデルは、7つの異なる変数（年齢、性別、教育、民族、収入、親の状況、政治的志向）において平均ホールドアウト相関が0.77という結果を示しました。さらに、このモデルを適用して個々のTwitterユーザーを民族、性別、政治的志向で分類したところ、完全教師ありアプローチと比較して驚くほど競争力のある結果が得られました。

Automatic Description Generation from Images: A Survey of Models, Datasets, and Evaluation Measures

Automatic Description Generation from Images: A Survey of Models, Datasets, and Evaluation Measures / 画像からの自動記述生成：モデル、データセット、評価尺度のサーベイ

Automatic description generation from natural images is a challenging problem that has recently received a large amount of interest from the computer vision and natural language processing communities. In this survey, we classify the existing approaches based on how they conceptualize this problem, viz., models that cast description as either generation problem or as a retrieval problem over a visual or multimodal representational space. We provide a detailed review of existing models, highlighting their advantages and disadvantages. Moreover, we give an overview of the benchmark image datasets and the evaluation measures that have been developed to assess the quality of machine-generated image descriptions. Finally we extrapolate future directions in the area of automatic image description generation.



自然画像からの自動記述生成は、近年、コンピュータビジョンおよび自然言語処理コミュニティから大きな関心を集めている困難な問題です。本調査では、この問題の概念化方法に基づいて既存のアプローチを分類します。すなわち、記述を生成問題として捉えるモデルと、視覚的またはマルチモーダルな表現空間における検索問題として捉えるモデルです。既存モデルの詳細なレビューを行い、それぞれの長所と短所を明らかにします。さらに、機械生成画像記述の品質を評価するために開発されたベンチマーク画像データセットと評価尺度の概要を示します。最後に、自動画像記述生成分野における将来の方向性を推定します。

Optimally Solving Dec-POMDPs as Continuous-State MDPs

Optimally Solving Dec-POMDPs as Continuous-State MDPs / 連続状態MDPとしてのDec-POMDPの最適解法

Decentralized partially observable Markov decision processes (Dec-POMDPs) provide a general model for decision-making under uncertainty in decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be decentralized. This new Dec-POMDP formulation, which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. To provide scalability, we refine this approach by combining heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to converge to an optimal solution. In particular, we introduce a feature-based heuristic search value iteration (FB-HSVI) algorithm that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that FB-HSVI terminates in finite time with an optimal solution. We include an extensive empirical analysis using well-known benchmarks, thereby demonstrating that our approach provides significant scalability improvements compared to the state of the art.



分散型部分観測マルコフ決定過程（Dec-POMDP）は、分散環境における不確実性下での意思決定のための一般的なモデルを提供しますが、最適に解くことは困難です（NEXP-Complete）。これらの問題を解決する新たな方法として、我々はDec-POMDPを区分線形かつ凸な値関数を持つ連続状態決定論的MDPに変換するというアイデアを導入します。このアプローチは、計画は集中型のオフラインで実行できる一方で、実行は分散化できるという事実を利用します。我々が占有MDPと呼ぶこの新しいDec-POMDPの定式化により、強力なPOMDPおよび連続状態MDP法を初めて使用することが可能になります。スケーラビリティを実現するために、我々はこのアプローチを改良し、マルチエージェント領域に存在する構造を活用するコンパクト表現とヒューリスティック探索を組み合わせることで、最適解への収束能力を失うことなく、このアプローチを実現します。特に、特徴ベースのコンパクト表現、ポイントベースの更新、効率的なアクション選択に基づく特徴ベースヒューリスティック探索値反復（FB-HSVI）アルゴリズムを導入します。理論分析により、FB-HSVIは有限時間内に最適解で終了することが実証されています。我々は、よく知られたベンチマークを用いた広範な実証分析を実施し、本手法が最先端技術と比較して大幅なスケーラビリティ向上をもたらすことを実証します。

Module Extraction in Expressive Ontology Languages via Datalog Reasoning

Module Extraction in Expressive Ontology Languages via Datalog Reasoning / データログ推論による表現オントロジー言語におけるモジュール抽出

Module extraction is the task of computing a (preferably small) fragment M of an ontology T that preserves a class of entailments over a signature of interest S. Extracting modules of minimal size is well-known to be computationally hard, and often algorithmically infeasible, especially for highly expressive ontology languages. Thus, practical techniques typically rely on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations ensure that M preserves all second-order entailments of T w.r.t. S, which is a stronger condition than is required in many applications, and may lead to unnecessarily large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach generalises existing approximations in an elegant way. More importantly, it allows extraction of modules that are tailored to preserve only specific kinds of entailments, and thus are often significantly smaller. Our evaluation on a wide range of ontologies confirms the feasibility and benefits of our approach in practice.



モジュール抽出とは、関心のあるシグネチャSに対する含意のクラスを保持するオントロジーTの（できれば小さな）フラグメントMを計算するタスクです。最小サイズのモジュールを抽出することは、計算的に困難であり、特に表現力の高いオントロジー言語においては、しばしばアルゴリズム的に実行不可能であることがよく知られています。したがって、実用的な手法は通常、近似に依存しており、Mは関連する含意を証明できるものの、最小であることが保証されているわけではない。既存の近似では、MがSに関してTのすべての2階含意を保持することが保証されているが、これは多くのアプリケーションで要求されるよりも強い条件であり、実際には不必要に大きなモジュールにつながる可能性があります。本論文では、モジュール抽出をデータログにおける推論問題に簡略化する新しい手法を提案します。本手法は、既存の近似をエレガントな方法で一般化します。さらに重要なのは、特定の種類の含意のみを保持するように調整されたモジュールを抽出できるため、多くの場合、モジュールのサイズが大幅に縮小されることです。幅広いオントロジーでの評価により、このアプローチの実現可能性と実用上の利点が確認されました。

Finding Strategyproof Social Choice Functions via SAT Solving

Finding Strategyproof Social Choice Functions via SAT Solving / SAT解法による戦略証明可能な社会選択関数の発見

A promising direction in computational social choice is to address research problems using computer-aided proving techniques. In particular with SAT solvers, this approach has been shown to be viable not only for proving classic impossibility theorems such as Arrow’s Theorem but also for finding new impossibilities in the context of preference extensions. In this paper, we demonstrate that these computer-aided techniques can also be applied to improve our understanding of strategyproof irresolute social choice functions. These functions, however, requires a more evolved encoding as otherwise the search space rapidly becomes much too large. Our contribution is two-fold: We present an efficient encoding for translating such problems to SAT and leverage this encoding to prove new results about strategyproofness with respect to Kelly’s and Fishburn’s preference extensions. For example, we show that no Pareto-optimal majoritarian social choice function satisfies Fishburn-strategyproofness. Furthermore, we explain how human-readable proofs of such results can be extracted from minimal unsatisfiable cores of the corresponding SAT formulas.



計算社会選択における有望な方向性の一つは、コンピュータ支援による証明技術を用いて研究課題に取り組むことです。特にSATソルバーを用いた場合、このアプローチはアローの定理などの古典的な不可能定理を証明するだけでなく、選好拡張の文脈における新たな不可能性を発見するためにも有効であることが示されました。本稿では、これらのコンピュータ支援技術が、戦略的証明不可能な社会選択関数の理解を深めるためにも適用できることを示す。しかし、これらの関数はより進化したエンコーディングを必要とし、そうでなければ探索空間が急速に大きくなりすぎる。我々の貢献は2つあります。まず、このような問題をSATに翻訳するための効率的なエンコーディングを提示し、次にこのエンコーディングを利用してケリーとフィッシュバーンの選好拡張に関する戦略的証明性に関する新たな結果を証明した。例えば、フィッシュバーンの戦略的証明性を満たすパレート最適な多数派社会選択関数は存在しないことを示す。さらに、そのような結果の人間が読める証明を、対応するSAT公式の最小の充足不可能な核からどのように抽出できるかを説明します。

Large-Scale Election Campaigns: Combinatorial Shift Bribery

Large-Scale Election Campaigns: Combinatorial Shift Bribery / 大規模選挙キャンペーン：組み合わせシフト賄賂

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber’s favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber’s preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.



選挙におけるシフト賄賂問題の組合せ的変種の複雑さを調査します。標準的なシフト賄賂問題では、各有権者が候補者集合に対する優先順位を持ち、外部エージェントである賄賂提供者が各有権者に金銭を支払って、賄賂提供者のお気に入りの候補者を指定された数だけ順位高くすることができる選挙が与えられます。目標は、賄賂提供者が好む候補者の勝利を確実にすることです。本論文で導入されるこの問題の組合せ的変種は、単一の賄賂行為によって、複数の投票におけるお気に入りの候補者の順位にプラスまたはマイナスの影響を与えることが可能な状況をモデル化します。この問題のこの変種は、大規模な選挙運動管理問題（技術的には賄賂問題としてモデル化される）の文脈において特に興味深い。一般に、この問題の組合せ的変種は非常に扱いにくいことを示す。具体的には、NP困難、パラメータ化された意味での困難、そして近似が困難です。それでもなお、我々は自然な限定されたケースに対してパラメータ化されたアルゴリズムと近似アルゴリズムを提供します。

Cross-Lingual Bridges with Models of Lexical Borrowing

Cross-Lingual Bridges with Models of Lexical Borrowing / 語彙借用モデルを用いた言語間橋渡し

Linguistic borrowing is the phenomenon of transferring linguistic constructions (lexical, phonological, morphological, and syntactic) from a donor language to a recipient language as a result of contacts between communities speaking different languages. Borrowed words are found in all languages, andin contrast to cognate relationshipsborrowing relationships may exist across unrelated languages (for example, about 40% of Swahilis vocabulary is borrowed from the unrelated language Arabic). In this work, we develop a model of morpho-phonological transformations across languages. Its features are based on universal constraints from Optimality Theory (OT), and we show that compared to several standardbut linguistically more naïvebaselines, our OT-inspired model obtains good performance at predicting donor forms from borrowed forms with only a few dozen training examples, making this a cost-effective strategy for sharing lexical information across languages. We demonstrate applications of the lexical borrowing model in machine translation, using resource-rich donor language to obtain translations of out-of-vocabulary loanwords in a lower resource language. Our framework obtains substantial improvements (up to 1.6 BLEU) over standard baselines.



言語借用とは、異なる言語を話すコミュニティ間の接触の結果として、言語構造（語彙、音韻、形態、統語）が供与言語から受益言語へ移転される現象です。借用語はすべての言語に見られ、同源関係とは対照的に、借用語は無関係な言語間に存在する場合があります（例えば、スワヒリ語の語彙の約40%は、無関係な言語であるアラビア語から借用されています）。本研究では、言語間の形態音韻変換モデルを開発します。その特徴は、最適化理論（OT）の普遍的制約に基づいています。OTに着想を得た本モデルは、いくつかの標準的だが言語学的にはよりナイーブなベースラインと比較して、わずか数十の学習例で借用語から供与語を予測する優れた性能を示し、言語間で語彙情報を共有するための費用対効果の高い戦略となっています。本モデルは、機械翻訳において語彙借用語モデルの応用を示し、リソースが豊富な供与語言語を用いて、リソースの少ない言語における語彙外借用語の翻訳を取得します。本フレームワークは、標準的なベースラインと比較して大幅な改善（最大1.6 BLEU）を達成しました。

Exact Algorithms for MRE Inference

Exact Algorithms for MRE Inference / MRE推論のための正確なアルゴリズム

Most Relevant Explanation (MRE) is an inference task in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact MRE algorithm has been developed previously except exhaustive search. This paper fills the void by introducing two Breadth-First Branch-and-Bound (BFBnB) algorithms for solving MRE based on novel upper bounds of GBF. One upper bound is created by decomposing the computation of GBF using a target blanket decomposition of evidence variables. The other upper bound improves the first bound in two ways. One is to split the target blankets that are too large by converting auxiliary nodes into pseudo-targets so as to scale to large problems. The other is to perform summations instead of maximizations on some of the target variables in each target blanket. Our empirical evaluations show that the proposed BFBnB algorithms make exact MRE inference tractable in Bayesian networks that could not be solved previously.



最も関連性の高い説明（MRE）は、ベイジアンネットワークにおける推論タスクであり、一般化ベイズ係数（GBF）を最大化することにより、与えられた証拠の説明として最も関連性の高いターゲット変数の部分インスタンス化を見つけます。これまで、網羅的な探索を除いて、正確なMREアルゴリズムは開発されていませんでした。本論文では、GBFの新しい上限に基づいてMREを解決するための2つの幅優先分枝限定法（BFBnB）アルゴリズムを紹介することで、この問題を解決します。1つの上限は、証拠変数のターゲットブランケット分解を使用してGBFの計算を分解することによって作成されます。もう1つの上限は、最初の上限を2つの方法で改善します。1つは、補助ノードを疑似ターゲットに変換することで大きすぎるターゲットブランケットを分割し、大規模な問題に拡張できるようにすることです。もう1つは、各ターゲットブランケット内の一部のターゲット変数に対して最大化ではなく合計を実行することです。実証的評価により、提案されたBFBnBアルゴリズムにより、これまで解決できなかったベイジアンネットワークにおける正確なMRE推論が処理可能になることが示されました。

Quadratization and Roof Duality of Markov Logic Networks

Quadratization and Roof Duality of Markov Logic Networks / マルコフ論理ネットワークの2乗化とルーフ双対性

This article discusses the quadratization of Markov Logic Networks, which enables efficient approximate MAP computation by means of maximum flows. The procedure relies on a pseudo-Boolean representation of the model, and allows handling models of any order. The employed pseudo-Boolean representation can be used to identify problems that are guaranteed to be solvable in low polynomial-time. Results on common benchmark problems show that the proposed approach finds optimal assignments for most variables in excellent computational time and approximate solutions that match the quality of ILP-based solvers.



本稿では、最大フローを用いた効率的な近似MAP計算を可能にするマルコフ論理ネットワークの2乗化について論じる。この手順は、モデルの擬似ブール表現を利用し、任意の次数のモデルを扱うことができます。採用された擬似ブール表現は、低多項式時間で解けることが保証されている問題を特定するために使用できます。一般的なベンチマーク問題に対する結果は、提案されたアプローチが優れた計算時間でほとんどの変数の最適な割り当てを見つけ、ILPベースのソルバーの品質に匹敵する近似解が得られることを示しています。

Combining Two and Three-Way Embedding Models for Link Prediction in Knowledge Bases

Combining Two and Three-Way Embedding Models for Link Prediction in Knowledge Bases / 知識ベースにおけるリンク予測のための2方向および3方向埋め込みモデルの組み合わせ

This paper tackles the problem of endogenous link prediction for knowledge base completion. Knowledge bases can be represented as directed graphs whose nodes correspond to entities and edges to relationships. Previous attempts either consist of powerful systems with high capacity to model complex connectivity patterns, which unfortunately usually end up overfitting on rare relationships, or in approaches that trade capacity for simplicity in order to fairly model all relationships, frequent or not. In this paper, we propose Tatec, a happy medium obtained by complementing a high-capacity model with a simpler one, both pre-trained separately and then combined. We present several variants of this model with different kinds of regularization and combination strategies and show that this approach outperforms existing methods on different types of relationships by achieving state-of-the-art results on four benchmarks of the literature.



本稿では、知識ベース補完のための内生的リンク予測の問題に取り組む。知識ベースは、ノードがエンティティ、エッジが関係性に対応する有向グラフとして表すことができます。これまでの試みは、複雑な接続パターンをモデル化する高い能力を持つ強力なシステム（残念ながら、通常はまれな関係性に過剰適合してしまう）か、または、頻繁かどうかにかかわらずすべての関係性を公平にモデル化するために能力と単純さを犠牲にするアプローチのいずれかです。本稿では、大容量モデルをより単純なモデルで補完し、それぞれを個別に事前学習させて組み合わせることで得られる、ちょうど良い中間的な手法であるTatecを提案します。本稿では、異なる種類の正則化および組み合わせ戦略を用いたこのモデルの複数のバリエーションを提示し、この手法が、文献の4つのベンチマークで最先端の結果を達成することにより、さまざまなタイプの関係性において既存の手法よりも優れていることを示す。

Knowledge Representation in Probabilistic Spatio-Temporal Knowledge Bases

Knowledge Representation in Probabilistic Spatio-Temporal Knowledge Bases / 確率的時空間知識ベースにおける知識表現

We represent knowledge as integrity constraints in a formalization of probabilistic spatio-temporal knowledge bases. We start by defining the syntax and semantics of a formalization called PST knowledge bases. This definition generalizes an earlier version, called SPOT, which is a declarative framework for the representation and processing of probabilistic spatio-temporal data where probability is represented as an interval because the exact value is unknown. We augment the previous definition by adding a type of non-atomic formula that expresses integrity constraints. The result is a highly expressive formalism for knowledge representation dealing with probabilistic spatio-temporal data. We obtain complexity results both for checking the consistency of PST knowledge bases and for answering queries in PST knowledge bases, and also specify tractable cases. All the domains in the PST framework are finite, but we extend our results also to arbitrarily large finite domains.



確率的時空間知識ベースの形式化において、知識を整合性制約として表現します。まず、PST知識ベースと呼ばれる形式化の構文と意味を定義します。この定義は、確率的時空間データの表現と処理のための宣言的フレームワークであるSPOTと呼ばれる以前のバージョンを一般化するものです。SPOTは、確率が正確な値が不明であるため区間として表現される確率的時空間データの表現と処理のための宣言的フレームワークです。本稿では、整合性制約を表現する非原子式のタイプを追加することで、以前の定義を拡張します。その結果、確率的時空間データを扱う知識表現のための、表現力の高い形式主義が実現されます。PST知識ベースの整合性検証とPST知識ベースにおけるクエリへの回答の両方について計算量の結果を取得し、扱いやすいケースも特定しました。PSTフレームワークのすべての領域は有限ですが、この結果を任意の大きさの有限領域にも拡張しました。

An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem

An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem / MaxSATに基づく正確なアルゴリズム最大重みクリーク問題の推論

Recently, MaxSAT reasoning is shown very effective in computing a tight upper bound for a Maximum Clique (MC) of a (unweighted) graph. In this paper, we apply MaxSAT reasoning to compute a tight upper bound for a Maximum Weight Clique (MWC) of a wighted graph. We first study three usual encodings of MWC into weighted partial MaxSAT dealing with hard clauses, which must be satisfied in all solutions, and soft clauses, which are weighted and can be falsified. The drawbacks of these encodings motivate us to propose an encoding of MWC into a special weighted partial MaxSAT formalism, called LW (Literal-Weighted) encoding and dedicated for upper bounding an MWC, in which both soft clauses and literals in soft clauses are weighted. An optimal solution of the LW MaxSAT instance gives an upper bound for an MWC, instead of an optimal solution for MWC. We then introduce two notions called the Top-k literal failed clause and the Top-k empty clause to extend classical MaxSAT reasoning techniques, as well as two sound transformation rules to transform an LW MaxSAT instance. Successive transformations of an LW MaxSAT instance driven by MaxSAT reasoning give a tight upper bound for the encoded MWC. The approach is implemented in a branch-and-bound algorithm called MWCLQ. Experimental evaluations on the broadly used DIMACS benchmark, BHOSLIB benchmark, random graphs and the benchmark from the winner determination problem show that our approach allows MWCLQ to reduce the search space significantly and to solve MWC instances effectively. Consequently, MWCLQ outperforms state-of-the-art exact algorithms on the vast majority of instances. Moreover, it is surprisingly effective in solving hard and dense instances.



最近、MaxSAT推論は（重み付けされていない）グラフの最大クリーク（MC）の厳密な上限を計算するのに非常に効果的であることが示されています。この論文では、重み付きグラフの最大重みクリーク（MWC）の厳密な上限を計算するためにMaxSAT推論を適用します。最初に、すべてのソリューションで満たされる必要があるハード句と重み付けされていて偽造できるソフト句を扱う重み付き部分MaxSATへのMWCの3つの一般的なエンコードを検討します。これらのエンコードの欠点が、ソフト句とソフト句内のリテラルの両方に重みが付けられる、MWCの上限専用のLW（リテラル重み付け）エンコードと呼ばれる特別な重み付き部分MaxSAT形式へのMWCのエンコードを提案する動機になっています。LW MaxSATインスタンスの最適解は、MWCの最適解ではなく、MWCの上限を与えます。次に、古典的なMaxSAT推論手法を拡張するためにTop-kリテラル失敗節とTop-k空節という2つの概念を導入し、LW MaxSATインスタンスを変換するための2つの健全な変換規則も導入します。MaxSAT推論によって駆動されるLW MaxSATインスタンスの連続的な変換により、エンコードされたMWCの厳密な上限が与えられます。このアプローチは、MWCLQと呼ばれる分岐限定アルゴリズムで実装されています。広く使用されているDIMACSベンチマーク、BHOSLIBベンチマーク、ランダム グラフ、および勝者決定問題のベンチマークでの実験的評価により、このアプローチによってMWCLQによって検索空間が大幅に削減され、MWCインスタンスが効果的に解決されることが示されています。その結果、MWCLQは、ほとんどのインスタンスで最先端の正確なアルゴリズムよりも優れています。さらに、難しくて密なインスタンスを解決する際に驚くほど効果的です。

Parallel Model-Based Diagnosis on Multi-Core Computers

Parallel Model-Based Diagnosis on Multi-Core Computers / マルチコアコンピュータにおける並列モデルベース診断

Model-Based Diagnosis (MBD) is a principled and domain-independent way of analyzing why a system under examination is not behaving as expected. Given an abstract description (model) of the system’s components and their behavior when functioning normally, MBD techniques rely on observations about the actual system behavior to reason about possible causes when there are discrepancies between the expected and observed behavior. Due to its generality, MBD has been successfully applied in a variety of application domains over the last decades.In many application domains of MBD, testing different hypotheses about the reasons for a failure can be computationally costly, e.g., because complex simulations of the system behavior have to be performed. In this work, we therefore propose different schemes of parallelizing the diagnostic reasoning process in order to better exploit the capabilities of modern multi-core computers. We propose and systematically evaluate parallelization schemes for Reiter’s hitting set algorithm for finding all or a few leading minimal diagnoses using two different conflict detection techniques. Furthermore, we perform initial experiments for a basic depth-first search strategy to assess the potential of parallelization when searching for one single diagnosis. Finally, we test the effects of parallelizing “direct encodings” of the diagnosis problem in a constraint solver.



モデルベース診断（MBD）は、検査対象のシステムが期待通りに動作しない理由を分析するための、原理に基づいたドメイン非依存の手法です。システムの構成要素と、正常動作時のそれらの動作に関する抽象的な記述（モデル）が与えられた場合、MBD手法は、期待される動作と観測された動作の間に矛盾がある場合に、実際のシステム動作に関する観察に基づいて考えられる原因を推論します。MBDはその汎用性により、過去数十年にわたり様々な応用分野で効果的に適用されてきました。MBDの多くの応用分野において、障害の原因に関する様々な仮説を検証することは、例えばシステム動作の複雑なシミュレーションを実行する必要があるため、計算コストが高くなる場合があります。そこで本研究では、最新のマルチコアコンピュータの能力をより有効に活用するために、診断推論プロセスを並列化する様々な手法を提案します。2つの異なる競合検出手法を用いて、最小診断のすべてまたはいくつかを導くためのライターのヒットセットアルゴリズムの並列化手法を提案し、体系的に評価します。さらに、基本的な深さ優先探索戦略の初期実験を行い、単一の診断を探索する際の並列化の可能性を評価します。最後に、制約ソルバーにおける診断問題の「直接エンコーディング」の並列化の効果を検証します。

Searching for the M Best Solutions in Graphical Models

Searching for the M Best Solutions in Graphical Models / グラフィカルモデルにおけるM最適解の探索

The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.



本論文は、最良優先探索または深さ優先分岐限定探索を用いて、組合せ最適化問題におけるm個の最良解を求めることに焦点を当てる。具体的には、よく知られているA*をm-最良タスクに拡張した新しいアルゴリズムm-A*を提示し、健全性、完全性、最適効率など、その望ましい特性がすべて維持されることを初めて証明します。最良優先アルゴリズムは膨大なメモリを必要とするため、メモリ効率の高い深さ優先分岐限定探索もm-最良タスクに拡張します。両アルゴリズムをグラフィカルモデル（ベイジアンネットワークにおける重み付きCSPやMPEなど）上の最適化タスクに適用し、複雑性分析と実証的評価を行う。実験により、メモリが利用可能な場合、最良優先アプローチは概ね優れているものの、深さ優先分岐限定探索の方がより堅牢であるという理論が裏付けられた。また、私たちのアルゴリズムは、m-bestタスク用に最近開発された関連方式と競合可能であることも示しています。

How Translation Alters Sentiment

How Translation Alters Sentiment / 翻訳が感情に及ぼす影響

Sentiment analysis research has predominantly been on English texts. Thus there exist many sentiment resources for English, but less so for other languages. Approaches to improve sentiment analysis in a resource-poor focus language include: (a) translate the focus language text into a resource-rich language such as English, and apply a powerful English sentiment analysis system on the text, and (b) translate resources such as sentiment labeled corpora and sentiment lexicons from English into the focus language, and use them as additional resources in the focus-language sentiment analysis system. In this paper we systematically examine both options. We use Arabic social media posts as stand-in for the focus language text. We show that sentiment analysis of English translations of Arabic texts produces competitive results, w.r.t. Arabic sentiment analysis. We show that Arabic sentiment analysis systems benefit from the use of automatically translated English sentiment lexicons. We also conduct manual annotation studies to examine why the sentiment of a translation is different from the sentiment of the source word or text. This is especially relevant for building better automatic translation systems. In the process, we create a state-of-the-art Arabic sentiment analysis system, a new dialectal Arabic sentiment lexicon, and the first Arabic-English parallel corpus that is independently annotated for sentiment by Arabic and English speakers.



感情分析研究は主に英語テキストを対象としてきました。そのため、英語には多くの感情分析リソースが存在します。しかし、他の言語にはそれほど多くありません。リソースの乏しい焦点言語における感情分析を改善するアプローチには、(a)焦点言語のテキストを英語などのリソースが豊富な言語に翻訳し、強力な英語感情分析システムを適用する、(b)英語の感情ラベル付きコーパスや感情辞書などのリソースを焦点言語に翻訳し、焦点言語の感情分析システムの追加リソースとして使用する、といったものがあります。本稿では、両方の選択肢を体系的に検証します。焦点言語のテキストの代わりに、アラビア語のソーシャルメディア投稿を使用します。アラビア語テキストの英語翻訳に対する感情分析は、アラビア語の感情分析と比較して競争力のある結果を生み出すことを示します。また、アラビア語の感情分析システムは、自動翻訳された英語感情辞書の使用からメリットを得られることを示します。さらに、翻訳の感情が原文の単語またはテキストの感情と異なる理由を検証するために、手動アノテーション研究を実施します。これは、より優れた自動翻訳システムの構築に特に重要です。このプロセスにおいて、最先端のアラビア語感情分析システム、新しい方言アラビア語感情辞書、そしてアラビア語話者と英語話者による感情が独立して注釈付けされた初のアラビア語・英語対訳コーパスを構築しました。

Bilingual Distributed Word Representations from Document-Aligned Comparable Data

Bilingual Distributed Word Representations from Document-Aligned Comparable Data / 文書アラインメントされた比較データからのバイリンガル分散単語表現

We propose a new model for learning bilingual word representations from non-parallel document-aligned data. Following the recent advances in word representation learning, our model learns dense real-valued word vectors, that is, bilingual word embeddings (BWEs). Unlike prior work on inducing BWEs which heavily relied on parallel sentence-aligned corpora and/or readily available translation resources such as dictionaries, the article reveals that BWEs may be learned solely on the basis of document-aligned comparable data without any additional lexical resources nor syntactic information. We present a comparison of our approach with previous state-of-the-art models for learning bilingual word representations from comparable data that rely on the framework of multilingual probabilistic topic modeling (MuPTM), as well as with distributional local context-counting models. We demonstrate the utility of the induced BWEs in two semantic tasks: (1) bilingual lexicon extraction, (2) suggesting word translations in context for polysemous words. Our simple yet effective BWE-based models significantly outperform the MuPTM-based and context-counting representation models from comparable data as well as prior BWE-based models, and acquire the best reported results on both tasks for all three tested language pairs.



非対訳文書対応データからバイリンガル単語表現を学習するための新しいモデルを提案します。単語表現学習における近年の進歩を踏まえ、本モデルは高密度実数値単語ベクトル、すなわちバイリンガル単語埋め込み（BWE）を学習します。対訳文対応コーパスや辞書などの容易に入手可能な翻訳リソースに大きく依存していたBWEの誘導に関するこれまでの研究とは異なり、本論文では、追加の語彙リソースや統語情報なしに、文書対応比較データのみに基づいてBWEを学習できることを明らかにしています。本稿では、多言語確率トピックモデリング（MuPTM）の枠組みに基づく、比較可能なデータからバイリンガル単語表現を学習する、これまでの最先端モデル、および分布的ローカルコンテキストカウントモデルと、我々のアプローチとの比較を示す。我々は、誘導されたBWEの有用性を2つの意味タスク、(1)バイリンガル語彙抽出、(2)多義語の文脈における単語翻訳の提案、において示す。我々のシンプルだが効果的なBWEベースのモデルは、比較可能なデータからのMuPTMベースおよびコンテキストカウント表現モデル、ならびに従来のBWEベースのモデルを大幅に上回り、テストされた3つの言語ペアすべてにおいて、両方のタスクで報告されている最高の結果を獲得した。

A Distributed Representation-Based Framework for Cross-Lingual Transfer Parsing

A Distributed Representation-Based Framework for Cross-Lingual Transfer Parsing / クロスリンガル転移解析のための分散表現ベースのフレームワーク

This paper investigates the problem of cross-lingual transfer parsing, aiming at inducing dependency parsers for low-resource languages while using only training data from a resource-rich language (e.g., English). Existing model transfer approaches typically don’t include lexical features, which are not transferable across languages. In this paper, we bridge the lexical feature gap by using distributed feature representations and their composition. We provide two algorithms for inducing cross-lingual distributed representations of words, which map vocabularies from two different languages into a common vector space. Consequently, both lexical features and non-lexical features can be used in our model for cross-lingual transfer. Furthermore, our framework is flexible enough to incorporate additional useful features such as cross-lingual word clusters. Our combined contributions achieve an average relative error reduction of 10.9% in labeled attachment score as compared with the delexicalized parser, trained on English universal treebank and transferred to three other languages. It also significantly outperforms state-of-the-art delexicalized models augmented with projected cluster features on identical data. Finally, we demonstrate that our models can be further boosted with minimal supervision (e.g., 100 annotated sentences) from target languages, which is of great significance for practical usage.



本論文は、リソースが豊富な言語（例えば、英語）からのトレーニングデータのみを使用しながら、リソースの少ない言語用の係り受け解析器を誘導することを目指し、クロスリンガル転移解析の問題を調査しています。既存のモデル転移アプローチは通常、言語間で転移できない語彙特徴を含んでいない。本稿では、分散特徴表現とその合成を用いることで、語彙特徴のギャップを埋める。異なる2言語の語彙を共通のベクトル空間にマッピングする、クロスリンガルな単語分散表現を誘導するための2つのアルゴリズムを提供します。その結果、クロスリンガル転送のためのモデルでは、語彙特徴と非語彙特徴の両方を利用できます。さらに、本フレームワークは、クロスリンガル単語クラスタなどの有用な追加機能を組み込むのに十分な柔軟性を備えています。本稿の貢献を組み合わせることで、英語ユニバーサルツリーバンクで学習し、他の3言語に転送した脱語彙化パーサと比較して、ラベル付きアタッチメントスコアにおいて平均相対誤差10.9%の削減を達成した。また、同一データにおいて、投影されたクラスター特徴で拡張された最先端の脱語彙化モデルを大幅に上回る性能を示した。最後に、本モデルは、ターゲット言語からの最小限の教師（例えば、100個の注釈付き文）でさらに強化できることを実証します。これは実用化において非常に重要です。

参考文献

関連情報