論文の概要、ライセンス

# (参考訳) 因果的発見のサンプル複雑さとドメインエキスパートの価値について [全文訳有]

On the Sample Complexity of Causal Discovery and the Value of Domain Expertise ( http://arxiv.org/abs/2102.03274v1 )

ライセンス: CC BY 4.0
Samir Wadhwa, Roy Dong(参考訳) 因果発見法は、実験者が相関関係のサブセットに介入する実験データに対して、純粋に観測データからランダム変数間の因果関係を同定する。 これは条件付き独立(CI) oracle: 2つのランダム変数が条件付き独立であるかどうかを別のランダム変数の集合で表すことができるオーラクルである。 このアルゴリズムの実践的実装には、CIオラクルの代わりに条件付き独立性に関する統計的テストが組み込まれている。 本稿では、CIオラクルを使わずに因果発見アルゴリズムのサンプル複雑性を分析する:一定の信頼度から、因果発見アルゴリズムが因果構造を特定するのに必要なデータポイントがいくつ必要か。 さらに、本手法は、データサンプルの観点から、ドメインの専門知識の価値を定量化することができる。 最後に,これらのサンプルレートの精度を数値例で示し,スパーシティ優先と既知の因果方向の利点を定量化する。

Causal discovery methods seek to identify causal relations between random variables from purely observational data, as opposed to actively collected experimental data where an experimenter intervenes on a subset of correlates. One of the seminal works in this area is the Inferred Causation algorithm, which guarantees successful causal discovery under the assumption of a conditional independence (CI) oracle: an oracle that can states whether two random variables are conditionally independent given another set of random variables. Practical implementations of this algorithm incorporate statistical tests for conditional independence, in place of a CI oracle. In this paper, we analyze the sample complexity of causal discovery algorithms without a CI oracle: given a certain level of confidence, how many data points are needed for a causal discovery algorithm to identify a causal structure? Furthermore, our methods allow us to quantify the value of domain expertise in terms of data samples. Finally, we demonstrate the accuracy of these sample rates with numerical examples, and quantify the benefits of sparsity priors and known causal directions.
公開日: Fri, 5 Feb 2021 16:26:17 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and 因果的発見のサンプル複雑性について 0.75
the Value of Domain Expertise ドメイン専門知識の価値 0.58
Samir Wadhwa 1 Roy Dong 2 Samir Wadhwa 1 Roy Dong 2。 0.94
1 2 0 2 b e F 5 1 2 0 2 b e F 5 0.85
] G L . ] G L。 0.79
s c [ 1 v 4 7 2 3 0 sc [ 1 v 4 7 2 3 0 0.68
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Abstract Causal discovery methods seek to identify causal relations between random variables from purely observational data, as opposed to actively collected experimental data where an experimenter intervenes on a subset of correlates. 概要 因果発見法は、実験者が相関関係のサブセットに介入する実験データに対して、純粋に観測データからランダム変数間の因果関係を同定する。 0.61
One of the seminal works in this area is the Inferred Causation algorithm, which guarantees successful causal discovery under the assumption of a conditional independence (CI) oracle: an oracle that can states whether two random variables are conditionally independent given another set of random variables. これは条件付き独立(CI) oracle: 2つのランダム変数が条件付き独立であるかどうかを別のランダム変数の集合で表すことができるオーラクルである。
訳抜け防止モード: この領域における基礎研究の1つは推論因果アルゴリズムである。 条件付き独立(CI)託宣という前提の下で因果発見を成功させる 2つの確率変数が別の確率変数の集合に対して条件独立であるかどうかを記述することができる。
0.74
Practical implementations of this algorithm incorporate statistical tests for conditional independence, in place of a CI oracle. このアルゴリズムの実践的実装には、CIオラクルの代わりに条件付き独立性に関する統計的テストが組み込まれている。 0.54
In this paper, we analyze the sample complexity of causal discovery algorithms without a CI oracle: given a certain level of confidence, how many data points are needed for a causal discovery algorithm to identify a causal structure? 本稿では、CIオラクルを使わずに因果発見アルゴリズムのサンプル複雑性を分析する:一定の信頼度から、因果発見アルゴリズムが因果構造を特定するのに必要なデータポイントがいくつ必要か。 0.80
Furthermore, our methods allow us to quantify the value of domain expertise in terms of data samples. さらに、本手法は、データサンプルの観点から、ドメインの専門知識の価値を定量化することができる。
訳抜け防止モード: さらに 我々の方法では データサンプルの観点で、ドメインの専門知識の価値を定量化します。
0.78
Finally, we demonstrate the accuracy of these sample rates with numerical examples, and quantify the benefits of sparsity priors and known causal directions. 最後に,これらのサンプルレートの精度を数値例で示し,スパーシティ優先と既知の因果方向の利点を定量化する。 0.77
1. Introduction Causal inference is growing in importance as data is used to make decisions. 1. データの意思決定に使用されるにつれて、因果推論の重要性が増している。 0.76
Understanding correlations is insufficient to understand the effect of an action or intervention taken by a decision-making agent. 相関を理解することは、意思決定エージェントが行う行動や介入の効果を理解するには不十分である。
訳抜け防止モード: 相関の理解 意思決定エージェントが行う行動や介入の効果を理解するには不十分です。
0.73
It would be fallacious reasoning for a decision-maker to to change an effect in hopes of inducing a change in an cause; however, distinguishing cause and effect is more difficult than identifying correlations. 意思決定者が原因の変更を誘発することを期待して効果を変更するのは誤った理由となるが、原因と効果の区別は相関関係を特定するよりも難しい。 0.79
1Department of Mechanical Science and Engineering, University of Illinois, Urbana, Illinois 2Department of Electrical and Computer Engineering, University of Illinois, Urbana, Illinois. 1department of mechanical science and engineering, university of illinois, urbana, illinois 2department of electrical and computer engineering, university of illinois, urbana, illinois (英語) 0.76
Correspondence to: Samir Wadhwa <samirw2@illinois.edu >. 対応: Samir Wadhwa <samirw2@illinois.edu >。 0.89
Submitted to the Proceedings of the 38 th International Conference on Machine Learning, PMLR 139, 2021. 第38回機械学習国際会議, PMLR 139, 2021に参加して 0.59
Copyright 2021 by the author(s). 著作者による著作権2021。 0.53
Causal discovery methods seek to identify causal relations between random variables from purely observational data. 因果発見法は、純粋観測データからランダム変数間の因果関係を同定する。 0.75
Much of the data available for learning today was collected passively (i.e. 今日の学習に利用できるデータの多くは受動的に収集された(すなわち)。 0.69
without any experimenter intervening on any correlates), and, in such settings, we often wish to discover causal relations that were not known a priori. 実験者がいかなる相関関係にも介入することなく) そして、そのような設定では、しばしば、先駆者ではない因果関係を発見したいと願う。 0.60
The earliest methods for causal discovery assumed that one had access to a conditional independence (CI) oracle: this oracle can reveal whether or not two random variables are independent conditioned on another set of random variables. 因果的発見の初期の方法は、条件付き独立(CI)オラクルへのアクセスを前提としていた:このオラクルは、2つのランダム変数が別のランダム変数の集合上で独立条件であるかどうかを明らかにすることができる。 0.65
With a CI oracle, the Inferred Causation (IC) algorithm is guaranteed to recover the causal dependencies up to fundamental ambiguities. CIオーラクルにより、推論因果関係(IC)アルゴリズムは、因果依存性を根本的な曖昧さまで回復することを保証する。 0.71
(We will discuss this in greater detail in Section 3.) (第3節で詳しく説明します) 0.47
In practice, when the IC algorithm is deployed in real-world settings, some changes are required. 実際には、ICアルゴリズムを実環境にデプロイする場合、いくつかの変更が必要である。 0.63
First, a conditional independence tester that checks for conditional independence from a finite number of observations typically replaces the CI oracle. 第一に、有限数の観測から条件独立をチェックする条件独立テスターは、通常CIオラクルを置き換える。 0.67
Second, some amounts of a priori knowledge, which we refer to as domain expertise, may regularize the problem and improve its computational complexity and sample efficiency. 第二に、ドメインの専門知識と呼ばれるいくつかの事前知識は、問題を規則化し、その計算複雑性とサンプル効率を改善することができる。 0.63
The contributions of this paper are as follows. 本論文の貢献は以下の通りである。 0.79
• To the best of our knowledge, this is the first paper that considers the sample complexity of causal discovery algorithms in the absence of a CI oracle. • 私たちの知る限りでは、この論文はciオラクルがいない場合、因果発見アルゴリズムのサンプル複雑さを検討する最初の論文です。 0.74
We combine recent results analyzing the sample complexity of conditional independence tests with an analysis of family-wise error rates in the repeated testing of causal inference algorithms to provide confidence bounds on the performance of causal discovery algorithms. 本研究では,条件付き独立性テストのサンプル複雑性を解析した結果と,因果推論アルゴリズムの繰り返しテストにおける家族的誤り率の分析を組み合わせ,因果探索アルゴリズムの性能に信頼性を与える。 0.86
This allows us to determine how many samples are needed to achieve a certain level of confidence in the recovery of the causal structure. これにより、因果構造の回復においてある程度の信頼を得るのに必要なサンプル数を決定することができる。 0.81
• Furthermore, we introduce the formalization of domain expertise as a partial CI oracle: domain expertise comes in the form of known results from particular conditional independence queries. さらに、ドメインの専門知識の形式化を部分的なCIオーラクルとして紹介します。ドメインの専門知識は、特定の条件付き独立クエリから既知の結果の形で提供されます。 0.56
This can encapsulate domain expertise in the form of a sparsity prior (e.g. これにより、ドメインの専門知識を事前にスパーシティの形でカプセル化することができる(例)。 0.48
an upper bound on the number of contextual variables that can render two random variables conditionally independent), a known causal direction, or knowledge 2つの確率変数を条件付き独立にすることができる文脈変数の数の上界、既知の因果方向、または知識 0.76
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
of dependence or independence in a particular context. 特定の文脈における依存または独立の 0.80
Our results allow us to quantify the value of domain expertise: how many additional samples are needed to achieve the same level of confidence in the absence of the provided domain expertise? 提供されたドメインの専門知識の欠如において、同じレベルの信頼性を達成するために、追加のサンプルがいくつ必要か?
訳抜け防止モード: 私たちの結果により、ドメインの専門知識の価値を定量化できます。 提供されるドメインの専門知識がない場合、同じレベルの信頼を得るために必要ですか?
0.66
Our work is motivated by the observation that an understanding of the value of domain expertise allows one to more efficiently conduct experiments when some passively observed data is available. 私たちの研究は、ドメインの専門知識の価値を理解することで、パッシブに観察されたデータがある場合、実験をより効率的に行えるという観察によって動機付けられたものです。 0.55
In the presence of some passively observed data, we can ask which domain expertise would best increase the confidence of causal discovery. 受動的に観測されたデータがある場合、どのドメインの専門知識が因果発見の信頼性を最も高めるかを問うことができる。 0.62
The rest of the paper is organized as follows. 残りの論文は以下の通り整理される。 0.66
In Section 2, we review related work. 第2節では、関連する作業についてレビューする。 0.46
In Section 3, we outline the mathematical preliminaries required for our results. 第3節では、結果に必要とされる数学的前提について概説する。 0.53
In Section 4, we prove our key theorems, which give the sample complexity of causal discovery in the presence and absence of domain expertise. 第4節では、ドメインの専門知識の存在と欠如に因果発見のサンプル複雑さを与える重要な定理を証明している。 0.75
In Section 5, we verify the rates with numerical simulations, and we end with closing remarks in Section 6. 第5節では、数値シミュレーションによるレートの検証を行い、第6節の閉会式で終わります。 0.70
2. Related Work When events A and B co-occur, it is not obvious whether A causes B, B causes A, or neither. 2. 関連する作業 a と b が共起する場合、a が b の原因であるか、b が a の原因であるかは明確ではない。 0.77
Classical approaches to handle the difficulty of causal inference either: 1) require an experimenter to actively intervene on certain factors, as is done in randomized control trials (Imbens & Rubin, 2015), or 2) to a priori assume causal dependencies, as is typical in classical econometrics (Wooldridge, 2019). 因果推論の難しさに対処する古典的なアプローチ: 1) ランダム化制御試験(Imbens & Rubin, 2015)のように実験者が何らかの要因に積極的に介入すること、または(2) 古典的計量学(Wooldridge, 2019)のように、先行者が因果依存性を仮定すること。 0.77
However, in the last several decades, there has been a growing interest in methods to identify causal dependencies from observational data. しかし、過去数十年の間に、観測データから因果依存性を識別する方法への関心が高まっています。 0.70
One of the seminal works in this area is the development of the IC algorithm (Pearl & Verma, 1995). この領域における専門的な研究の1つは、ICアルゴリズムの開発である(Pearl & Verma, 1995)。 0.83
Building on a results in Bayesian networks, it identified conditions in which passive observations can reveal necessary links in a causal structure, and provided a computational method to identify said links. ベイズネットワークの結果に基づいて、受動的観測により因果構造における必要なリンクを明らかにする条件を特定し、そのリンクを同定する計算方法を提供した。 0.77
This original algorithm requires access to a CI oracle, which can exactly identify when two random variables are independent conditioned on some other set of contextual variables. このオリジナルのアルゴリズムはCIオーラクルへのアクセスを必要とし、2つのランダム変数が他のコンテクスト変数のセットで独立しているときに正確に識別できる。 0.68
Since then, the area of causal discovery has grown dramatically. それ以来、因果発見の領域は劇的に拡大した。 0.70
One of the state-of-theart methods for causal discovery is kernel-based methods. 因果発見の最先端の方法の1つはカーネルベースのメソッドである。 0.50
These methods use kernel-based methods for the conditional independence test in lieu of a CI oracle (Sun et al., 2007; Zhang et al., 2011; Mitrovic et al., 2018). これらの方法は、CIオラクル(Sun et al., 2007; Zhang et al., 2011; Mitrovic et al., 2018)の代わりに、条件付き独立テストにカーネルベースの方法を使用する。 0.77
These works are typically either empirically validated or provided asymptotic theoretical guarantees. これらの作品は通常、経験的に検証されるか、漸近的な理論的な保証が与えられる。 0.46
In contrast, our work focuses on finite-sample results, using a conditional independence tester with known sample complexity. 対照的に,本研究では,サンプル複雑性が知られている条件付き独立性テスタを用いて,有限サンプル結果に着目した。 0.56
Relatedly, (Acharya et al., 2018) seeks to identify which experiment should be done to best recover the causal graph, 関連して (Acharya et al., 2018) は、因果グラフを最もよく回復するためにどの実験を行うべきかを特定しようとしている。
訳抜け防止モード: 関連して(Acharya et al ., 2018) 因果グラフを回復するために どの実験を行うべきかを 特定することです
0.82
in either an adaptive or non-adaptive fashion. 適応的または非適応的な方法で。 0.68
In contrast, our work attempts to quantify the value of potential interventions by identifying the comparable number of samples needed to achieve the same confidence level. 対照的に、我々の研究は、同じ信頼レベルを達成するのに必要なサンプル数を識別することで、潜在的な介入の価値を定量化しようと試みています。
訳抜け防止モード: 対照的に 我々の研究は 潜在的な介入の価値を 同じ信頼レベルを達成するのに必要なサンプル数を識別する。
0.67
(Lee & Bareinboim, 2020) studies issues of identifiability when some variables are unobserved. (lee & bareinboim, 2020)一部の変数が観測できない場合の識別可能性の問題を研究する。 0.60
Synergistic with our work is the work of (Jaber et al., 2019), which seeks to identify when domain expertise and observational data are sufficient to resolve ambiguities between observationally equivalent causal graphs. 我々の研究と相乗効果は (Jaber et al., 2019) の研究であり、観測に等価な因果グラフ間のあいまいさを解決するのに、ドメインの専門知識と観測データがいつ十分であるかを特定することを目的としている。 0.54
Alternatively, some methods assume some known structure that regularizes the problem. あるいは、この問題を正則化する既知の構造を仮定する手法もある。 0.59
Functional causal models assume that the causal dependencies have a known, parameterized functional form (Shimizu et al., 2006; Hoyer et al., 2009; Zhang & Hyv¨arinen, 2009; Kumor et al., 2020). 関数因果関係モデルは、因果関係が既知のパラメータ化された関数形式(Shimizu et al., 2006; Hoyer et al., 2009; Zhang & Hyv sarinen, 2009; Kumor et al., 2020)であると仮定する。 0.85
For an overview of functional causal model methods, we refer the reader to (Glymour et al., 2019). 機能的因果モデルメソッドの概要については、読者を(Glymour et al., 2019)に紹介します。 0.81
In (Greenewald et al., 2019), the authors assume the causal graph has a tree structure. 著者らは(Greenewald et al., 2019)、因果グラフに木構造があると仮定している。 0.82
Our work focuses on the settings where one is agnostic to the causal structures, but adds an assumption that the variables of interest are discrete. 我々の研究は、因果構造に非依存な設定に焦点を当てるが、興味のある変数が離散的であるという仮定を加える。 0.66
To the best of our knowledge, this is one of the first works to analyze the sample complexity of causal discovery. 我々の知る限りでは、これは因果発見のサンプルの複雑さを分析する最初の研究の1つである。 0.77
The IC algorithm itself consists of repeated tests for conditional independence, and recent results on the sample complexity of these conditional independence tests are what enable the results in this paper. icアルゴリズム自体は条件付き独立性の繰り返しテストから成り、この条件付き独立性テストのサンプル複雑性に関する最近の結果は、この結果を可能にするものである。 0.82
In particular, we build on the recent work of (Canonne et al., 2018), which provides sublinear conditional independence testing sample complexity. 特に、我々は最近の研究(Canonne et al., 2018)に基づいて、サブ線形条件付き独立試験サンプル複雑性を提供する。 0.77
Testing for conditional independence has a rich literature, and we can only provide a superficial summary here. 条件付き独立のテストには豊富な文献があり、表面的な概要はここでしか提供できません。 0.64
The conditional independence testing problem has known hardness results when the variables are continuous (see, e.g. 条件付き独立性テスト問題は、変数が連続であるときに既知の硬さを持つ(例えば、)。 0.68
(Shah & Peters, 2020)), and recent work has focused on identifying regularizing assumptions for the case where the variables are continuous (Matey Neykov, 2020). (Shah & Peters, 2020)) と最近の研究は、変数が連続である場合(Matey Neykov, 2020)の正規化仮定の特定に焦点を当てている。 0.82
Another interesting direction is to add assumptions on the computational complexity of the coupling between random variables, as is assumed in (Marx & Vreeken, 2019). もう1つの興味深い方向は、確率変数間の結合の計算複雑性の仮定を追加することである(marx & vreeken, 2019)。 0.71
Motivated by the hardness results for continuous variables, we focus on the setting where all the random variables are discrete. 連続変数のハードネス結果に動機づけられ、すべての確率変数が離散的な設定に焦点が当てられる。 0.72
For discrete distributions, common methods include G2 tests (Aliferis et al., 2010; Schl¨uter, 2014) and conditional mutual information (Zhang et al., 2010). 離散分布の一般的な方法は、G2テスト(Aliferis et al., 2010; Schl suter, 2014)と条件付き相互情報(Zhang et al., 2010)である。 0.81
For G2 tests, sample complexity bounds exist, but prior to the work of (Canonne et al., 2018), sublinear sample complexity results were not available. g2テストでは、サンプル複雑性境界が存在するが(canonne et al., 2018)、サブリニアなサンプル複雑性の結果は得られなかった。 0.77
Our work uses these sublinear bounds in the analysis of the sample complexity of causal discovery methods. 本研究では,これらのサブリニア境界を因果的発見手法のサンプル複雑性解析に用いる。 0.70
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
2.1. Notation We use the following notation throughout this paper. 2.1. 表記 本論文全体では以下の表記を用いる。 0.67
For a finite set A, we let |A| denote the cardinality of A, and we let 2A denote the powerset of A. Additionally, for any collection of sets Ai across an index set I, we use (cid:116)i∈I Ai to denote the disjoint union, whose elements are of the form (i, x) with x ∈ Ai. 有限集合 A に対して、|A| は A の基数を表し、2A は A の基数を表す。さらに、指数集合 I 上の任意の集合 Ai の集合に対して、(cid:116)i∂I Ai を用いて、元が x ∈ Ai の形式 (i, x) であるような整合を表す。 0.79
For any event A, P (A) will denote the probability of event A, with the underlying probability space implicitly understood. 任意の事象 A に対して、P (A) は事象 A の確率を表し、基礎となる確率空間は暗黙的に理解される。 0.69
For any random variable X, we let E[X] denote the expectation of X, and let supp(X) denote the support of X. 任意のランダム変数 X に対して、E[X] を X の期待値、supp(X) を X のサポート値とする。 0.76
We say X ⊥⊥ Y |Z to indicate that X and Y are conditionally independent given Z. X と Y が Z に対して条件独立であることを示すために、X は Y | Z である。 0.74
3. Mathematical Preliminaries In this section, we formulate our problem and introduce the definitions and tools used for our results in Section 4. 3. 数学的前提 このセクションでは、問題を定式化し、第4節で結果に用いる定義とツールを紹介します。 0.78
3.1. Causal models 3.1. 因果モデル 0.69
First, we quickly introduce common definitions in causal inference. まず、因果推論において共通定義を迅速に導入する。 0.67
For a more detailed coverage of these concepts, we refer the reader to (Pearl, 2013). これらの概念のより詳細なカバレッジについては、読者を参照します(Pearl, 2013)。 0.78
Definition 1 (Directed, acyclic graphs (DAGs)). 定義 1 (Directed, acyclic graphs (DAGs))。 0.77
A directed graph is a set of nodes V and a set of edges E ⊆ V × V . 有向グラフ (direct graph) はノード V の集合であり、エッジの集合 E は V × V である。 0.80
Throughout this paper, we assume V is finite, and let N = |V |. この論文を通して、V は有限であると仮定し、N = |V | とする。 0.72
For any node i ∈ V , we denote the parents of i as pa(i) = {j ∈ V : (j, i) ∈ E}. 任意のノード i ∈ V に対して、i の親を pa(i) = {j ∈ V : (j, i) ∈ E} と表す。 0.81
We iteratively define n-th generation ancestry as pan(i) = {j ∈ V : k ∈ pan−1(i), (j, k) ∈ E}, with the base case pa1 = pa. We define the ancestors of a node i ∈ V as anc(i) = ∪∞ n=1 pan(i), and a directed graph is acyclic if i /∈ anc(i) for all i ∈ V . i) = {j ∈ V : k ∈ pan−1(i), (j, k) ∈ E}, with the base case pa1 = pa. 我々は、ノード i ∈ V の祖先を anc(i) = \∞ n=1 pan(i) として定義し、有向グラフはすべての i ∈ V に対して i /∈ anc(i) ならば非環的である。 0.81
Definition 2 (Markov compatibility). 定義 2 (Markov 互換性)。 0.86
Let G = (V, E) be a DAG and let Xi be a discrete random variable for each i ∈ V . G = (V, E) を DAG とし、Xi を各 i ∈ V に対して離散確率変数とする。 0.75
We say G and X = (Xi)i∈V are compatible if the distribution of X factorizes as: G と X = (Xi)i∈V は、X の分布が次のように分解すると互換性があると言う。 0.64
(cid:89) i∈V (cid:89) i∈V 0.69
P (X = x) = P (X = x) = 0.85
P (Xi = xi|(Xj)j∈pa(i) = (xj)j∈pa(i)) P (Xi = xi|(Xj)j∈pa(i) = (xj)j∈pa(i)) 0.96
We also say G represents X, and refer to G as a causal structure. また、G は X を表し、G を因果構造と呼びます。 0.69
Definition 3 (Stability, faithfulness). 定義3(安定性、忠実さ)。 0.71
We say G = (V, E) and X satisfy the stability condition if the following holds. 次が成立すると、G = (V, E) と X は安定性条件を満たす。 0.79
For any i ∈ V, j ∈ V and A ⊆ V , if Xi ⊥⊥ Xj|(Xk)k∈A, then Yi ⊥⊥ Yj|(Yk)k∈A for any other random variables Y compatible with G. This condition is also sometimes referred to as faithfulness. 任意の i ∈ V に対して、j ∈ V と A を V とすると、Xi を Xj|(Xk)k∈A とすると、他の任意の任意のランダム変数 Y に対して、Yi は Yj|(Yk)k∈A となる。 0.83
Finally, we should note that there are some fundamental ambiguities in causal discovery. 最後に、因果発見にはいくつかの基本的な曖昧さがあることに注意する必要がある。 0.48
In other words, there are some parts of the causal structure that can never be identified from passive observation alone. 言い換えれば、因果構造の一部には受動的観察だけでは特定できない部分がある。 0.64
We formalize this by defining observationally equivalent DAGs. 観測的に等価なDAGを定義することでこれを形式化する。 0.47
Definition 4 (Observational equivalence and patterns). 定義4(観察的同値性とパターン)。 0.79
Two DAGs G1 and G2 are observationally equivalent if for any random variables X compatible with G1, then X is also compatible with G2, and vice versa. 2つのDAG G1 と G2 は、G1 と互換性のある任意の確率変数 X に対して、X が G2 と互換性があり、その逆も同様である。 0.71
Observational equivalence forms an equivalence class on the set of DAGs. 観測等価性はDAGの集合上の等価性クラスを形成する。 0.70
These equivalence classes can be represented by patterns, which are partially directed graphs (i.e. これらの同値クラスは、部分的に有向グラフであるパターンで表すことができる。 0.73
some edges are directed and some are undirected). 一部のエッジは指示され、一部は無指示です)。 0.56
Undirected edges will be denoted {i, j} ∈ E, and the interpretation is that either (i, j) ∈ E or (j, i) ∈ E for any DAG in the equivalence class. 非直接エッジは {i, j} ∈ E と表記され、解釈は、(i, j) ∈ E または (j, i) ∈ E が同値クラス内の任意の DAG に対するものである。 0.87
The IC algorithm is provided in Algorithm 1. ICアルゴリズムは、アルゴリズム1で提供される。 0.81
The IC algorithm provides a computational method by which to identify the equivalence class of DAGs which generated the random variables X, assuming access to a conditional independence oracle, defined here. ICアルゴリズムは、ここで定義された条件独立オラクルへのアクセスを想定したランダム変数Xを生成するDAGの等価クラスを同定する計算方法を提供する。 0.85
Definition 5 (Conditional independence (CI) oracle). 定義5 (Conditional independent (CI) oracle)。 0.76
A CI oracle takes in any i ∈ V, j ∈ V and B ⊆ V and outputs true if Xi ⊥⊥ Xj|(Xk)k∈B and f alse otherwise. CI oracle は任意の i ∈ V, j ∈ V, B ∈ V を取り、Xi が Xj|(Xk)k∈B および f がそうでなければ true を出力する。 0.86
We note that only Step 1 of Algorithm 1 requires data; Steps 2 and 3 are post-processing and do not require any data. アルゴリズム1のステップ1だけがデータを必要とし、ステップ2とステップ3は後処理であり、データを必要としない。 0.80
Furthermore, the IC algorithm is complete, in the sense of the following proposition. さらに、次の命題の観点から、ICアルゴリズムは完全である。 0.65
Proposition 1 (Completeness of the IC algorithm (Verma & Pearl, 1992; Meek, 1995)). Proposition 1 (Completeness of the IC algorithm (Verma & Pearl, 1992; Meek, 1995)。 0.75
Suppose X and G satisfy the stability criteria. X と G が安定性基準を満たすと仮定する。 0.75
Then, there is a unique equivalence class of causal structures consistent with X, and the IC algorithm recovers this equivalence class. そして、X と整合した因果構造のユニークな同値類が存在し、ICアルゴリズムはこの同値類を復元する。 0.69
3.2. Conditional independence testers 3.2. 条件付き独立テスター 0.70
This formalization serves as the model for causality. この形式化は因果性のモデルとなる。 0.70
When G and X are compatible, the causal interpretation is that if there is an edge from i to j, then Xi is a direct cause of Xj. G と X が互換性のあるとき、因果的解釈は i から j へのエッジがある場合、Xi は Xj の直接的な原因である。 0.81
One regularizing condition is one of stability: it states that every conditional independence in the variables X arises necessarily from the causal structure G, and not some quirk of the parameterization. 1つの正規化条件は安定性の1つであり、変数 X の条件付き独立は必ず因果構造 G から生じ、パラメータ化のクォークは存在しない。 0.78
Intuitively, this means that a conditional independence holds if and only if some property of the causal structure is satisfied. 直感的には、条件付き独立は、因果構造の一部の性質が満たされている場合にのみ成立することを意味する。 0.68
As noted previously, it is uncommon in practice to have access to a CI oracle. 前述したように、ci oracleにアクセスすることは、実際には珍しいことです。 0.56
In practice, we often use a finite number of data samples and a conditional independence tester to identify when there is a conditional independence or dependence. 実際には、有限個のデータサンプルと条件付き独立テスターを使って、条件付き独立性や依存があるかどうかを識別します。 0.74
In this section, we outline some of the theoretical results in conditional independence testing, as recently discovered by (Canonne et al., 2018). このセクションでは、最近発見された条件付き独立テスト(Canonne et al., 2018)における理論的結果のいくつかについて概説します。 0.72
If the conditional dependencies can be arbitrarily small, then it will be difficult to detect from a finite number of samples. 条件付き依存関係が任意に小さい場合、有限個のサンプルから検出することは困難である。 0.68
英語(論文から抽出)日本語訳スコア
Algorithm 1 Inferred Causation (IC) algorithm アルゴリズム 1 Inferred Causation (IC) アルゴリズム 0.76
Algorithm 2 Testing for conditional independence アルゴリズム2 条件付き独立試験 0.75
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
Input: A collection of nodes [N ] and a CI oracle. 入力: ノード[N]とCIオーラクルのコレクション。 0.57
Output: An equivalence class of DAGs. 出力:DAGの等価クラス。 0.61
// Step 1: Use data to construct an undirected graph such that i and j are connected if and only if Xi and Xj are always conditionally dependent. ステップ1: Xi と Xj が常に条件依存である場合に限り、i と j が連結であるような無向グラフを構築するためにデータを使用する。 0.78
Initialize an empty graph V = [N ] and E = ∅. 空のグラフ V = [N ] と E = s を初期化します。 0.83
for {i, j} such that i ∈ V , j ∈ V \ {i} do i ∈ V , j ∈ V \ {i} が行うような {i, j} に対して 0.93
f ound = f alse for B ⊆ V \ {i, j} do f ound = f alse for b \ v \ {i, j} do である。 0.92
if Xi ⊥⊥ Xj|(Xk)k∈B then Xj|(Xk)k∈B であれば 0.85
f ound = true, S{i,j} = B, break f ound = true, S{i,j} = B, break 0.85
end if end for if f ound = f alse, then add {i, j} to E end if end if f ound = f alse ならば、 {i, j} を e に追加する。 0.91
end for // Step 2: Add directed edges based on v-structures. end for // step 2: v-structuresに基づく有向エッジの追加。 0.82
For more details on v-structures, see (Pearl, 2013). v-structures の詳細は (Pearl, 2013) を参照のこと。 0.89
for k ∈ V do k ∈ V に対して 0.90
for {i,j} such that {i, k} ∈ E, {j, k} ∈ E, {i, j} /∈ E, i (cid:54)= j do i, k} ∈ E, {j, k} ∈ E, {i, j} /∂ E, i (cid:54)= j do であるような {i, j} について 0.92
if k /∈ S{i,j} then add (i, k) and (j, k) to E k /∈ S{i,j} ならば (i, k) と (j, k) を E に追加する。 0.93
end for end for // Step 3: Orient undirected edges without introducing new v-structures or introducing a directed cycle. 終止符 end for // step 3: orient undirected edges 新しいv-structuresを導入するか、directed cycleを導入するかのどちらかです。
訳抜け防止モード: 終止符 end for // step 3 : orient undirected edges without 新しいv - 構造の導入、あるいは有向サイクルの導入。
0.72
Orient undirected edges according to the rules outlined in (Pearl, 2013). orient undirected edgesは(pearl, 2013)で概説されているルールに従っている。 0.71
As such, we assume that dependencies cannot be arbitrarily small. したがって、依存関係は任意に小さくならないと仮定する。 0.61
Assumption 1 (Minimum level of dependence). 推定1(最小限の依存度)。 0.66
Let PX,Y |Z denote the set of probability distributions such that X ⊥⊥ Y |Z. PX,Y |Z を X > Y |Z となるような確率分布の集合とする。 0.86
For our unknown distribution P , we assume either X ⊥⊥ Y |Z or dT V (P,PX,Y |Z) := inf Q∈PX,Y |Z supA |P (A) − Q(A)| > , for some known constant  > 0. 未知の分布 P に対しては、ある既知の定数 s > 0 に対して、X の Y |Z または dT V (P,PX,Y |Z) := inf Q∈PX,Y |Z supA |P (A) − Q(A)| > のどちらかと仮定する。 0.84
The algorithm itself is relatively intuitive. アルゴリズム自体は比較的直感的です。 0.70
Suppose we observe several samples of random variables (X, Y, Z) and wish to determine if X ⊥⊥ Y |Z. 確率変数 (X, Y, Z) のサンプルをいくつか観察し、X が Y |Z であるかどうかを判断する。 0.74
Essentially, for each possible value of Z, we test if X ⊥⊥ Y |Z = z, and we aggregate the results across all possible values of z as a test for conditional independence. 本質的には、Z の各可能な値に対して、X が Y |Z = z であるかどうかを検証し、条件独立のテストとして z の可能なすべての値に結果を集約する。
訳抜け防止モード: 本質的には z の可能な値ごとに x が y |z = z であればテストする。 条件付き独立性の試験として z の可能なすべての値に結果を集約する。
0.81
This is provided in Algorithm 2. これはアルゴリズム2で提供される。 0.74
Note that this test actually requires a random number of samples: drawing K from a Poisson distribution ensures that the number of elements in each bin is independent, which is essential for the proof. このテストは実際にランダムなサンプル数を必要とします。Poisson分布からKを描画すると、各ビン内の要素の数が独立していることが保証されます。 0.81
We can guarantee the sample complexity of Algorithm 2 under some conditions, as outlined in the following proposition. 以下に示すように、いくつかの条件下でアルゴリズム2のサンプルの複雑さを保証できます。 0.71
Proposition 2 (Sample complexity of CI tests (Canonne 提案2(CIテストのサンプル複雑性(Canonne) 0.83
Input: A sample generator of (X, Y, Z) from a distribution P , an expected number of samples m, a threshold τ, and an independence tester Φ. 入力: 分布 P から (X, Y, Z) のサンプル生成器、期待されるサンプル数 m 、しきい値 τ 、独立性試験器 ... のサンプル生成器。 0.82
Output: true/f alse if it is believed that X ⊥⊥ Y |Z or not. 出力: true/f alse x が y |z であるか否かを問う。 0.84
Draw samples (Xi, Yi, Zi)K of samples K ∼ P oisson(m). サンプル (Xi, Yi, Zi)K はサンプル K > P oisson(m) である。 0.68
Bin the data into multisets Sz = {(Xi, Yi) : Zi = z}. データをマルチセット Sz = {(Xi, Yi) : Zi = z} に結合する。 0.84
A = 0 for z in the support of Z do A = A + |Sz|Φ(Sz) A = 0 for z in the support of Z do A = A + |Sz|*(Sz) 0.97
i=1 from P , where the number p から i=1 であり 0.68
if |Sz| ≥ 4 then もし |Sz| ≥ 4 なら 0.79
end if end for Return true if A ≤ τ and f alse otherwise. end if end for return true if a ≤ τ and f alse となる。 0.84
et al., 2018)). Suppose the independence tester Φ satisfies the following properties when given K samples of (X, Y ) from distribution P : と2018年)。 分布 P から (X, Y ) の K のサンプルを与えられたとき、独立性試験器は以下の特性を満たすと仮定する。 0.56
E[Φ] = (cid:107)P − PX ⊗ PY (cid:107)2 E[ ] = (cid:107)P − PX > PY (cid:107)2 0.95
Var[Φ] ≤ C(cid:0)E[Φ]/K + 1/K 2(cid:1) Var[ ] ≤ C(cid:0)E[ ]/K + 1/K 2(cid:1) 0.97
2 Here, PX and PY denote the marginals of P and ⊗ refers to the product measure, and C is some constant. 2 ここで、PX と PY は P の限界を表し、P と PY は積測度を表し、C は一定である。 0.78
Furthermore, let M = | supp(Z)|, and suppose for some constant β: さらに、M = | supp(Z)| とし、ある定数 β を仮定する。 0.74
(cid:18) M 1/2 (cid:18) M 1/2 0.71
2 (cid:18) M 7/8 2 (cid:18)m7/8 0.71
(cid:19)(cid:19) (cid:19)(cid:19) 0.75
, M 6/7 8/7 , M 6/7 です。 0.73
 (1) m = β max  (1) m = β 最大値 0.86
, min /(cid:112)| supp(X)|| supp(Y )| (where  is defined in Assump- 分 t/(cid:112)| supp(X)|| supp(Y )| (ここで t は Assump で定義される) 0.54
let γ = 1 − 5/2e and (cid:48) = γ = 1 − 5/2e かつ >(cid:48) = 0.83
In addition, m((cid:48))2, (m(cid:48))4 tion 1). また、 m((cid:48))2, (m)(cid:48))4 tion 1) である。 0.62
Set τ = γ M 3 rithm 2 satisfies the following properties. τ = γ M 3 rithm 2 は以下の性質を満たす。 0.79
When X ⊥⊥ Y |Z, there exists some constant C(cid:48) > 0 such that: X が Y |Z であるとき、定数 C(cid:48) > 0 が存在する。 0.82
. Then, Algo- . そして、アルゴ。 0.67
2 min (cid:16) 2分 (cid:16) 0.74
(cid:17) P (f alse) ≤ C(cid:48) (cid:32) (cid:17) P (f alse) ≤ C(cid:48) (cid:32) 0.85
β2γ2 When dT V (P,PX,Y |Z) > , for the same constant C(cid:48): β2γ2 同じ定数 C(cid:48) に対して dT V (P,PX,Y |Z) > のとき 0.65
P (true) ≤ C(cid:48) P (true) ≤ C(cid:48) 0.98
64 β2γ2 + βγ(cid:112)min(M, m) 64 β2γ2 + βγ(cid:112)min(M, m) 0.80
8 (cid:33) 8 (cid:33) 0.82
(2) (3) In Section 4, we will use Proposition 2 to determine how many samples are needed to achieve a particular confidence level. (2) (3) セクション4では、プロポジション2を使用して、特定の信頼性レベルを達成するために必要なサンプルの数を決定します。
訳抜け防止モード: (2) (3) 第4節では命題2を使用します 特定の信頼レベルを達成するために必要なサンプル数を決定する。
0.81
The parameter of importance is β, which scales the expected number of samples m and changes the confidence level. 重要なパラメータはβで、期待されるサンプルmの数をスケールし、信頼性レベルを変更する。 0.79
Additionally, we emphasize the dependence on M, the cardinality of the support of Z, which changes between iterations of the IC algorithm. さらに、我々は、ICアルゴリズムの反復間で変化するZのサポートの基数であるMへの依存を強調する。 0.68
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
3.3. Family-wise error rates and Bonferroni correction 3.3. 家族別誤差率とbonferroni補正 0.75
In the absence of a CI oracle, Step 1 of the IC algorithm requires one to conduct a family of conditional independence tests. CIオーラクルがない場合、ICアルゴリズムのステップ1では、条件付き独立テストのファミリーを実行する必要があります。 0.74
In this paper, we prove confidence levels for the successful recovery of the underlying causal structure’s pattern. 本稿では、基礎となる因果構造パターンの回復に成功するための信頼性レベルを証明します。 0.82
We do so by noting when our conditional independence tests function as a CI oracle. 条件付き独立性テストがCIオーラクルとして機能するかどうかを指摘する。 0.60
In other words, when is every conditional independence test correct? 言い換えれば、条件付き独立性テストはいつ正しいのか? 0.80
The Bonferroni correction is a union bound on the confidence of a family of tests (Miller, 1981). ボンフェロニ補正 (Bonferroni correct) は、テストの族(Miller, 1981)の信頼に縛られる連合である。 0.71
We note that the Bonferroni correction method does not require the tests to be independent, as it simply relies on the union bound. Bonferroni補正方法は、単に結合結合に依存しているため、テストを独立させる必要がないことに注意してください。 0.77
Other methods for controlling the family-wise error rate often have restrictions on the dependence between the tests (e.g. 家庭的なエラー率を制御する他の方法では、テスト間の依存性(例)に制限があることが多い。 0.65
˘Sid´ak correction or Hochberg’s procedure (Miller, 1981)), which is difficult to verify for the conditional independence tests. Sid ́ak correct or Hochberg's procedure (Miller, 1981) 条件付き独立試験の検証は困難である。 0.69
Proposition 3 (Bonferroni correction (Miller, 1981)). 命題3 (Bonferroni correct) (Miller, 1981)。 0.61
Consider a family of conditional independence tests, {CIi}i, where each test CIi has a confidence level of 1 − αi. 各テストCIiが1 − αiの信頼レベルを持つ条件付き独立テスト{CIi}iのファミリーを考えてみましょう。 0.83
Then, the family of tests has a confidence level of 1 −(cid:80) そしたら テストのファミリーは信頼度が1 −(cid:80)である 0.73
i αi. We emphasize that when the same data is used for each conditional independence test, then the outcomes of the tests will necessarily be coupled. i αi 私たちは、条件付き独立テストで同じデータが使用される場合、テストの結果が必ず結合されることを強調します。 0.77
In our setting, we assume that all data is used in every conditional independence test. 私たちの設定では、すべてのデータが条件付き独立テストで使用されると仮定します。
訳抜け防止モード: 私たちの設定では すべてのデータは条件付き独立性テストで使用される。
0.85
An alternative method would be to use each data point in exactly one conditional independence test. 別の方法は、1つの条件付き独立テストで各データポイントを使用することです。 0.74
This would ensure that the tests are independent, but the rate at which data gets ‘used up’ with this method ultimately provides worse sample complexity results, due to the large number of conditional independence tests in the IC algorithm. これはテストが独立したことを保証しますが、この方法でデータが「使用される」速度は最終的にICアルゴリズムの条件付き独立テストの多数によるより悪いサンプル複雑性の結果を提供します。 0.88
Proposition 1 implies that, should every conditional independence test yield the true result, then we will recover the causal structure’s pattern. 命題1は、すべての条件付き独立テストが真の結果をもたらす場合、因果構造のパターンを回復することを意味します。 0.78
4. Sample Complexity of Causal Discovery 4. 因果発見のサンプル複雑性 0.85
Algorithms In this section, we derive the rates for sample complexity of causal discovery algorithms. アルゴリズム このセクションでは、因果的発見アルゴリズムのサンプル複雑さの率を導き出します。 0.76
Recall that V , the nodes of our causal graph, are an index set for a collection of random variables, (Xi)i∈V . 因果グラフのノードである V は、ランダム変数 (Xi)i∈V の集合のインデックス集合である。 0.64
Let us first introduce notation to index the conditional independence tests in the IC algorithm (Algorithm 1). まず、ICアルゴリズム(Algorithm 1)における条件独立性テストのインデックス化について紹介する。 0.85
Let: 2V \{i,j} としよう。 2V \{i,j} 0.66
(4) (cid:71) (4) (cid:71) 0.82
T = {i,j}⊆V T = {i,j} =V 0.84
Note that each element of T is of the form ({i, j}, B), where B ⊆ V \ {i, j}. T の各元は形式 ({i, j}, B) であり、ここで B は V \ {i, j} である。 0.65
Thus, each element of T corresponds to a conditional independence test which may need to be run.1 したがって、Tの各要素は、実行する必要がある条件付き独立テストに対応する。 0.77
1Not every test may need to be run, based on the outcome of 1 結果に基づいて、すべてのテストを実行する必要がある場合。 0.77
First, we adapt the results in Proposition 2 to serve our purposes: for one fixed conditional independence test, we identify how many samples are needed in expectation to achieve a certain confidence level. まず第一に、私たちは提案2の結果を私たちの目的に適応させます。1つの一定の条件付き独立テストでは、特定の信頼レベルを達成するために期待するサンプルの数を特定します。
訳抜け防止モード: 第一に,提案2の結果を目的に適合させる : 1つの条件付き独立性テストについて どれだけのサンプルが 一定の信頼レベルを達成するために 期待する必要があります
0.79
Lemma 1. Fix a conditional test ({i, j}, B) ∈ T and a desired confidence level 1 − α. レマ1。 条件付きテスト ({i, j}, b) ∈ t と所望の信頼レベル 1 − α を固定する。 0.67
Suppose the expected number of samples m is greater than the cardinality of the support of B. 予想されるサンプル m の数は、B のサポートのカーディナリティよりも大きいと仮定する。 0.79
Let M = | supp(B)|. M = | supp(B)| とする。 0.84
Then, the desired confidence level can be achieved with P oisson(m) samples, where: そして、P oisson(m)サンプルを用いて所望の信頼レベルを達成することができる。 0.75
independence  16C(cid:48) 独立 16C(cid:48) 0.78
αγ((cid:48))2 16C(cid:48) αγ(cid:48) M 3/8 αγ((cid:48))8/7 M 5/14 αγ((cid:48))2 16C(cid:48) αγ(cid:48) M 3/8 αγ((cid:48))8/7 M 5/14 0.74
16C(cid:48) 16C(cid:48) 0.74
m(M, α) = if M ≤ ((cid:48))−8/3 if ((cid:48))−8/3 < M ≤ ((cid:48))−8 if M > ((cid:48))−8 m(M, α) = もし M ≤ (\(cid:48))−8/3 であるなら (\(cid:48))−8/3 < M ≤ (\(cid:48))−8 ならば M > (\(cid:48))−8 である。 0.84
Here, C(cid:48), γ, and (cid:48) are as defined in Proposition 2. ここで、C(cid:48)、γ、および s(cid:48) は命題 2 で定義される。 0.76
Proof. Using Proposition 2, it suffices to bound both the false negative rate in Equation (2) and the false positive rate in Equation (3). 証明。 命題2を用いることで、方程式(2)の偽負率と方程式(3)の偽陽性率の両方を境界付けることができる。 0.68
We can see that the false positive rate is larger than the false negative rate. 偽陽性率が偽陰性率よりも大きいことが分かります。
訳抜け防止モード: 私たちはそれを見ることができます 偽陽性率は 偽陰性率より大きい。
0.66
Since we are assuming m is greater than M, it suffices to choose β such that 64C(cid:48)/β2γ2 ≤ α/2 and 8C(cid:48)/βγ M ≤ α/2. m が M より大きいと仮定しているので、64C(cid:48)/β2γ2 ≤ α/2 と 8C(cid:48)/βγM ≤ α/2 を選択するだけで十分である。 0.67
Additionally, in the high sample regime, the latter inequality will imply the former; rearranging gives the condition: さらに、高サンプルレジームでは、後者の不等式は前者を暗示し、再配置は条件を与える。 0.62
√ β ≥ αγ(cid:112)| supp(Z)| √ β ≥ αγ(cid:112)| supp(Z)| 0.87
16C(cid:48) 16C(cid:48) 0.74
Next, noting the 3 regimes in the definition of m in Equation (1) yields the desired result. 次に、式(1)におけるmの定義における3つのレジームに注意すると、望ましい結果が得られる。 0.61
Lemma 1 tells us how many samples are needed for one test to achieve a particular confidence level. Lemma 1は、特定の信頼性レベルを達成するために1つのテストに必要なサンプルの数を示しています。
訳抜け防止モード: lemma 1 はどれだけのサンプルが あるテストが特定の信頼性レベルを達成するために必要です。
0.75
Combining Lemma 1 with the Bonferroni correction method in Proposition 3, if each test t ∈ T has confidence level 1−αt, then the t∈T αt. Lemma 1とProposition 3におけるBonferroni補正法を組み合わせると、各テスト t ∈ T が信頼レベル 1−αt を持つなら、t∈T αt となる。 0.78
By Proposition 1, this means we will recover the equivalence class of Proposition 1 では、同値クラスを回復することを意味します。 0.68
family of tests will have confidence 1−(cid:80) causal structures with probability at least 1 −(cid:80) 少なくとも1−(cid:80)の確率を持つ1−(cid:80)因果構造を持つ試験群 0.78
t∈T αt. However, if we have a target confidence level 1 − α, we must set αt for each t ∈ T . t∈T αt。 しかし、目標信頼レベル 1 − α があれば、各 t ∈ T に対して αt を設定する必要がある。 0.73
We can think of it as an α budget of uncertainty which must be divided between the tests. テスト間で分割しなければならない不確実性のα予算と考えることができる。 0.66
For each t = ({i, j}, B) ∈ T , let Mt = | supp(B)|. 各 t = ({i, j}, B) ∈ T に対して、Mt = | supp(B)| とする。 0.85
Then, for any vector of positive constants (αt)t∈T , we can define the cost maxt∈T m(Mt, αt) as the expected number of samples required for every test t ∈ T to have confidence αt. すると、任意の正の定数ベクトル (αt)thtmlt に対して、コストmaxtservlett m(mt, αt) を各テスト t ∈ t が信頼度 αt を持つのに必要なサンプルの期待数として定義することができる。 0.75
The following optimization provides the lowest expected 以下の最適化は、最も低い期待値を提供する 0.61
previous tests, but for our analysis in this paper, we assume the worst-case and suppose that every test must be run. 以前のテストだが、本論文の分析では、最悪のケースを想定し、すべてのテストを実行する必要があると仮定する。 0.68
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
number of samples for a target confidence level 1 − α: ターゲット信頼レベル 1 − α のサンプル数。 0.61
min (αt)t min (複数形 mins) 0.81
s.t. (cid:88) s.t. (cid:88) 0.75
max s∈T m(Ms, αs) max s∈T m(Ms, αs) 0.84
αt = α t∈T αt ≥ 0 for all t ∈ T αt = α すべての t ∈ t に対する tسt αt ≥ 0 0.82
equals the optimal value of Equation (5).2 Note that m(0, α0) = 16C(cid:48)/α0γ((cid:48))2. Equation (5).2 の最適値に等しい m(0, α0) = 16C(cid:48)/α0γ(*(cid:48))2。 0.88
Then, for any other M, we see the following holds by Lemma 1: そして、他の任意の M に対して、Lemma 1: による以下のホールドを見ます。 0.66
(5) α∗ M = (5) α∗ M = 0.90
α∗ 0(cid:48)M 3/8 α∗ 0((cid:48))6/7M 5/14 6/7M 5/14の3/8α/0(cid:48)です。 0.70
if M ≤ ((cid:48))−8/3 if ((cid:48))−8/3 < M ≤ ((cid:48))−8 if M > ((cid:48))−8 もし M ≤ (\(cid:48))−8/3 であるなら (\(cid:48))−8/3 < M ≤ (\(cid:48))−8 ならば M > (\(cid:48))−8 である。 0.83
α∗ 0 We can characterize solutions to this optimization with the following lemma. α∗ 0 この最適化の解を次の補題で特徴づけることができる。 0.70
Lemma 2. Let (α∗ tion (5). レマ2号。 α∗ tion (5) とする。 0.64
Then m(Mt, α∗ t ∈ T . すると m(Mt, α∗ t ∈ T となる。 0.72
t )t denote an optimal solution to Equas) for any s ∈ T and t )t は任意の s ∈ T に対して Equas に対する最適解を表し、 0.81
t ) = m(Ms, α∗ t ) = m(Ms, α∗ 0.94
Proof. Note that m(M, α) is continuous and strictly decreasing in α for any fixed M. Let T ∗ ⊆ T denote the set of tests t∗ such that m(Mt∗ , α∗ t∗ ) = maxt m(Mt, α∗ t ). 証明。 m(M, α) は任意の固定 M に対して α において連続的かつ厳密に減少していることに注意して、T (Mt , α , t ) = maxt m(Mt, α , t ) である。 0.73
Suppose for the sake of contradiction that there exists an s ∈ T such that m(Ms, α∗ t∗ ). 矛盾のために、m(Ms, α∗ t∗ ) であるような s ∈ T が存在すると仮定する。 0.82
For δ > 0, we can define (˜αt)t: δ > 0 の場合、 (\αt)t: を定義できる。 0.79
s) < m(Mt∗ , α∗ s) < m(Mt∗ , α∗ 0.96
α∗ t ˜αt = α∗ t ※αt= 0.63
t + δ/|T ∗| t − δ α∗ α∗ t + δ/|T ∗| t − δ α∗ α∗ 0.78
if t ∈ T ∗ if t = s otherwise t ∈ T ∗ が t = s でなければ 0.80
δ For maxt∈T m(Mt, α∗ t ), (α∗ δ maxt∈T m(Mt, α, t ) の場合(α) 0.83
t )t. sufficiently small, maxt∈T m(Mt, ˜αt) t) である。 十分に小さい、maxt∈T m(Mt, yαt) 0.75
< contradicting the optimality of This characterization allows us to state our theorem which gives the sample complexity of the IC algorithm in the absence of a CI oracle. <最適性に矛盾する この特徴づけにより、CIオーラクルが存在しないときにICアルゴリズムのサンプル複雑性を与える定理を述べることができる。 0.81
Theorem 1 (Sample complexity of the IC algorithm). Theorem 1 (ICアルゴリズムのサンプル複雑性)。 0.75
As before, let N = |V | denote the number of random variables considered. 前述の通り、N = |V | は考慮される確率変数の数を表す。 0.71
Let R1 = ((cid:48))−8/3 and R2 = ((cid:48))−8. R1 = (\(cid:48))−8/3 と R2 = (\(cid:48))−8 とする。 0.82
Fix any α ∈ (0, 1), and let α∗ 任意の α ∈ (0, 1) を固定し、 α∗ とする 0.81
0 solve: t∈T :Mt≤(cid:98)R1(cid:99) 0 で解ける。 t∈T :Mt≤(cid:98)R1(cid:99) 0.70
t∈T :(cid:98)R1+1(cid:99)≤Mt≤(cid:98)R2(cid:99) t∈T :(cid:98)R1+1(cid:99)≤Mt≤(cid:98)R2(cid:99) 0.66
1 + (cid:88) 1 + (cid:88) 0.82
t∈T :Mt≥(cid:98)R2+1(cid:99) t∈T :Mt(cid:98)R2+1(cid:99) 0.60
(cid:48)M 3/8 t + (cid:48)m 3/8 t + 0.83
(cid:19) ((cid:48))6/7M 5/14 (cid:19) (cid:48))6/7m5/14 0.71
t = α (6) 0γ((cid:48))2) samples, AlgoThen, given P oisson(16C(cid:48)/α∗ rithm 1, using Algorithm 2 as the conditional independence tester, recovers the correct equivalence class of causal models with probability greater than 1 − α. t = α (6) 0γ(\(cid:48))2) サンプル、algothen, given p oisson(16c(cid:48)/α∗ rithm 1 アルゴリズム2を条件付き独立テスタとして使用し、1 − α 以上の確率を持つ因果モデルの正しい同値類を回復する。 0.84
Here, γ and (cid:48) are as defined in Proposition 2. ここで γ と s(cid:48) は命題 2 で定義される。 0.81
Proof. Let (α∗ By Lemma 2, it suffices to calculate α∗ 証明。 Lemma 2 では、α を計算するのに十分である。 0.69
t )t denote an optimal solution to Equation (5). t ) 方程式 (5) に対する最適解を表す。 0.77
0, where m(0, α∗ 0) 0, ここで m(0, α∗ 0) 0.95
(cid:18) (cid:88) (cid:18)(cid:88) 0.72
α∗ 0 (cid:88) α∗ 0 (cid:88) 0.81
The desired result follows by summing these terms across the total budget constraint on α in Equation (5). 所望の結果は、これらの項を方程式 (5) において α 上の全予算制約を合計することで従う。 0.67
This bound becomes easier to interpret in the case where the variables are all have the same cardinality. この境界は、変数がすべて同じカーディナリティを持つ場合に解釈しやすくなります。
訳抜け防止モード: この境界がより簡単になります。 変数がすべて同じカーディナリティを持つ場合、解釈します。
0.68
Corollary 1. Suppose, every random variable Xi has the same number of possible values (cid:96) = | supp(Xi)|. 第1話。 任意の確率変数 Xi は同じ数の可能な値 (cid:96) = | supp(Xi)| を持つと仮定する。 0.63
Then a confidence level of 1 − α is achieved with P oisson(m) samples, where: 次に、P oisson(m) サンプルで 1 − α の信頼レベルが達成されます。 0.76
m ≥ 16C(cid:48) αγ((cid:48))2 m ≥ 16c(cid:48) αγ(\(cid:48))2 0.86
(cid:18)N (cid:19) (cid:18)N (cid:19) 0.81
2 (1 + (cid:96)3/8)N−2 2 (1 + (cid:96)3/8)N−2 0.79
Proof. This follows by bounding the term in the parentheses in Equation (6). 証明。 これは、方程式 (6) の括弧内の項を束縛することで従う。 0.64
Note that the terms within the (cid:80) sum are all upper-bounded by (cid:96)3|B|/8, where the test t = ({i, j}, B) and |B| is the number of variables in the set B. なお、 (cid:80) 和内の項はすべて (cid:96)3|B|/8 で上界であり、テスト t = ({i, j}, B) と |B| は集合 B 内の変数の数である。 0.86
Thus, we have the bound α ≤ α∗ t∈T (cid:96)3|B|/8. したがって、有界 α ≤ α → t∈T (cid:96)3|B|/8 を持つ。 0.63
The rest follows from counting the number of elements in T : α∗ bound into m(0, α∗ 残りは T : α の要素数を m(0, α) に結合して数えることに続く。 0.84
(cid:1)(1 + (cid:96)3/8)N−2. (cid:1)(1 + (cid:96)3/8)N−2。 0.71
Plugging this (cid:80) t∈T (cid:96)3|B|/8 = α∗ これをプラグする (cid:80) tservlett (cid:96)3|b|/8 = α∗ 0.53
0) yields the desired result. 0) 所望の結果を得る。 0.82
(cid:0)N 0 (cid:0)N 0 0.85
0 0 2 4.1. 0 0 2 4.1. 0.81
The effect of domain expertise ドメインの専門知識が与える影響 0.74
Now, we formalize domain expertise as a partial CI oracle. 現在、ドメインの専門知識を部分的なCIオーラクルとして形式化しています。 0.37
Intuitively, domain expertise allows us to know the outcome of some subset of conditional independence tests without using any samples. 直感的には、ドメインの専門知識は、サンプルを使わずに条件付き独立テストのサブセットの結果を知ることができる。
訳抜け防止モード: 直感的に言えば、ドメインの専門知識は サンプルを使わずに 条件付き独立テストの結果を 知るために
0.76
Thus, these terms do not enter into the Bonferroni correction evaluations of the previous section. したがって、これらの用語は、前のセクションのBonferroni補正評価に入りません。 0.65
Definition 6 (Partial CI oracle). 定義6 (Partial CI oracle)。 0.75
A partial CI oracle is specified by some subset of S ⊆ T (where T is as defined in Equation (4)). 部分的 CI オラクルは S > T の部分集合によって指定される(ただし T は方程式 (4) で定義される)。 0.76
For any ({i, j}, B) ∈ S, the partial CI oracle outputs true if Xi ⊥⊥ Xj|(Xk)k∈B and f alse otherwise. 任意の ({i, j}, b) ∈ s に対して、部分的 ci oracle が xi が xj|(xk)khtmlb かつ f alse であれば真となる。 0.81
In this formalism, it is straightforward to modify the sample complexity results from the previous section accordingly. この形式主義では、サンプルの複雑さの結果を前節から変更するのは簡単である。 0.72
Corollary 2 (Sample complexity with domain expertise). corollary 2 (ドメインの専門知識を伴うサンプル複雑性)。 0.69
Suppose we have access to a partial CI oracle, which can respond to queries S ⊆ T . 部分的なci oracleへのアクセスがあり、クエリ s と t に応答できるとします。 0.57
Let α∗ 0 solve Equation (6), only with the sums across t ∈ T \ S instead of t ∈ T . 0 は t ∈ T の代わりに t ∈ T \ S 上の和でのみ、方程式 (6) を解く。 0.81
0γ((cid:48))2) samples, AlgoThen, given P oisson(16C(cid:48)/α∗ rithm 1, using Algorithm 2 as the conditional independence tester, recovers the correct equivalence class of causal models with probability greater than 1 − α. 0γ(>(cid:48))2) サンプル、algothen, given p oisson(16c(cid:48)/α∗ rithm 1 アルゴリズム2を条件付き独立テスタとして使用し、1 − α 以上の確率を持つ因果モデルの正しい同値クラスを回復する。 0.81
of α∗ 2Here, we adopt a slight abuse of notation, noting that the value t depends only on Mt = | supp(B)| where t = ({i, j}, B). α∗ の 2ここでは、値 t が Mt = | supp(B)| ここで t = ({i, j}, B) のみに依存することに注意して、表記法のわずかな乱用を採用する。 0.81
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
This corollary holds for general partial CI oracles. この座標系は、一般的な部分的CIオラクルを表わす。 0.34
When more structure is provided, we can more explicitly calculate the bounds. より多くの構造が提供されると、境界をより明確に計算できます。 0.67
For example, the PC algorithm is based on a priori knowledge of the sparsity of the graph (Spirtes et al., 2001). 例えば、PCアルゴリズムはグラフの粗さに関する事前知識に基づいています(Spirtes et al., 2001)。 0.67
If a causal direction is known, then this also corresponds to a set of tests which we do not need to run. 因果的な方向が分かっている場合、これは我々が実行する必要のない一連のテストに対応します。 0.63
This is formalized in the following corollaries. これは以下の用語で形式化される。 0.54
Corollary 3 (Sample complexity under a sparsity prior). Corollary 3 (予備の下のサンプル複雑性)。 0.72
Suppose every random variable Xi has the same number of possible values (cid:96) = | supp(Xi)|, and we know a priori that any context (Xk)k∈B that renders two random variables Xi and Xj conditionally independent will have at most |B| ≤ R random variables. 任意の確率変数 xi が同じ可能な値 (cid:96) = | supp(xi)| を持ち、2つの確率変数 xi と xj を条件付き独立に描画する任意のコンテキスト (xk)k ajaxb が |b| ≤ r の確率変数を持つと仮定する。 0.79
Then a confidence level of 1 − α is achieved with m such that: すると、m で 1 − α の信頼レベルが達成される。 0.69
m ≥ 16C(cid:48) αγ((cid:48))2 m ≥ 16c(cid:48) αγ(\(cid:48))2 0.86
(cid:18)N (cid:19) R(cid:88) (cid:18)N (cid:19)R(cid:88) 0.81
(cid:18)N − 2 (cid:19) (cid:18)N − 2(cid:19) 0.84
2 k=0 k (cid:96)3k/8 2 k=0 k (cid:96)3k/8 0.72
Proof. This follows similarly to Corollary 1, where we take the oracle as defined on S = {({i, j}, B) ∈ T : |B| ≤ R}. 証明。 これは Corollary 1 と同様に、S = {({i, j}, B) ∈ T : |B| ≤ R} 上で定義されるようなオラクルを取る。 0.70
We observe that the growth rate of the sample complexity for the PC algorithm is much smaller than the exponential growth rate of sample complexity for the IC algorithm. 我々は,pcアルゴリズムのサンプル複雑性の増大速度は,icアルゴリズムのサンプル複雑性の指数的成長速度よりもずっと小さいことを確かめた。 0.82
We visualize this in Figure 1. これを図1に示します。 0.71
Thus, our bounds allow us to quantify the value of the sparsity prior in terms of the number of samples saved. したがって、私たちの境界は、保存されたサンプルの数の点で事前にスパーシティの値を定量化することができます。 0.61
Intuitively, as the number of nodes grows, this sparsity prior becomes more and more beneficial. 直観的には、ノードの数が増えるにつれて、このスパーシティがより有益になる。 0.56
Figure 1. The number of samples needed to guarantee a confidence level of 1 − α = 0.95 with (cid:96) = 2 and  = 0.1. 図1。 信頼レベルが 1 − α = 0.95 であることを保証するのに必要なサンプルの数は (cid:96) = 2 である。 0.79
suppose we know a priori the following set of causal dependencies: D = {(ik, jk)}k where (ik, jk) is an edge in our causal graph for each k. Then a confidence level of 1 − α is achieved with m such that: d = {(ik, jk)}k ここで (ik, jk) は各 k に対する因果グラフの辺である。
訳抜け防止モード: D = { ( ik, ik, ) 次の因果依存の集合を事前に知っているとします。 jk)}k ここで ( ik , jk ) は各 k の因果グラフのエッジである。
0.52
m ≥ 16C(cid:48) αγ((cid:48))2 m ≥ 16c(cid:48) αγ(\(cid:48))2 0.86
(cid:18)(cid:18)N (cid:18)(cid:18)N 0.78
(cid:19) 2 (cid:19) 2 0.82
(cid:19) − |D| (cid:19) -|D| 0.80
(1 + (cid:96)3/8)N−2 (1 + (cid:96)3/8)N−2 0.74
We note a few things about this model for domain expertise and our analysis. このモデルについて、ドメインの専門知識と分析に関するいくつかの点に注目します。 0.56
It assumes that the partial CI oracle merely replaces the conditional independence tests in Algorithm 1. 部分的なci oracleは、アルゴリズム1の条件付き独立テストを置き換えるだけだと仮定している。 0.67
It does not assume that any re-ordering of tests is done, in light of the results of the oracle queries. oracleクエリの結果に照らして、テストの再順序付けが行われていると仮定するものではありません。 0.67
One interpretation of this is that one does not assume the result is known until after the oracle is queried. この解釈の1つは、神託がクエリされた後に結果がわかると仮定しないということである。 0.64
If we know a priori that a test result will successfully identify a conditional independence, this will correspond to a loop break in Algorithm 1, and some tests in T will not need to be conducted. テスト結果が条件付き独立をうまく識別できるという優先順位が分かっていれば、これはアルゴリズム1のループブレークに対応し、Tのいくつかのテストを実行する必要はありません。 0.75
Furthermore, we may be able to re-order the tests to reduce the tests that should be conducted. さらに、実施すべきテストを減らすためにテストをリオーダーすることもできるかもしれません。 0.67
The reasons for analyzing sample complexity from an exante perspective are two-fold. サンプルの複雑さをexanteの観点から分析する理由は2つある。 0.77
First, it is easier to analyze, and provides a worst-case bound in the ex-post setting as well. まず、分析が簡単で、元投稿設定にバインドされた最悪のケースも提供します。 0.61
Additionally, this formalization is due in part to our motivating application. さらに、この形式化は、モチベーションのあるアプリケーションによるものです。 0.57
This analysis can identify which experiments we should conduct, from a data-efficiency perspective. この分析は、データ効率の観点から、どの実験を行うべきかを特定できます。 0.57
In practical settings, the decision to conduct an experiment must be made without knowing what the outcome of the experiment will be. 実践的な環境では、実験の結果を知らずに実験を行うという決定を下さなければならない。 0.78
A limitation of this definition is it only captures the effect of domain expertise on sample complexity. この定義の限界は、ドメインの専門知識がサンプルの複雑さに与える影響だけを捉えることです。
訳抜け防止モード: この定義の限界は ドメインの専門知識がサンプルの複雑さに与える影響のみを捉えます。
0.83
Another fashion in which this knowledge can be useful is to distinguish observationally equivalent causal graphs: some a priori knowledge could identify the true causal graph from the equivalence class of observationally equivalent graphs. この知識が有用であるもう1つの方法は、観察同値因果グラフを区別することである:いくつかの事前知識は、観測同値グラフの同値クラスから真の因果グラフを識別することができる。 0.68
This is not captured in our formalism. これは私たちの形式主義には当てはまらない。 0.59
5. Numerical Validation In this section we compare our bounds for sample complexity against results obtained by running the IC and PC algorithm on simulated data for causal graphs with different number of nodes. 5. 数値検証 このセクションでは、サンプルの複雑さの境界を、異なるノード数を持つ因果グラフのシミュレーションデータ上でICおよびPCアルゴリズムを実行して得られた結果と比較します。 0.83
For the simulations in this section, we take the causal graph of N nodes to be the graph where X1, X2, .., XN−1 are independent and are direct causes of XN . このセクションのシミュレーションでは、Nノードの因果グラフを X1, X2, .., XN−1 が独立しており、XN の直接的な原因であるグラフにします。 0.88
For the simulation, P (Xi = 0) = 0.6 for i = 1, 2, .., N − 1 and XN = X1 ∨ X2 ∨ ...XN−1. シミュレーションでは P (Xi = 0) = 0.6 for i = 1, 2, ..., N − 1 and XN = X1 , X2 , ...XN−1 である。 0.92
The causal graph is shown in Figure 2. 因果グラフは図2に示されます。 0.69
5.1. Results for IC Algorithm 5.1. ICアルゴリズムの結果 0.75
Corollary 4 (Sample complexity with a known causal direction). Corollary 4 (既知の因果方向を持つサンプル複雑性)。 0.81
Suppose every random variable Xi has the same number of possible values (cid:96) = | supp(Xi)|. 任意の確率変数 Xi が同数の可能な値 (cid:96) = | supp(Xi)| を持つと仮定する。 0.85
Furthermore, We ran the IC algorithm on data generated according to the causal graph in Figure 2. さらに 図2の因果グラフに従って生成されたデータに基づいてICアルゴリズムを実行しました。 0.60
We compare the empirical error rate from our numerical simulations with the theoret- 数値シミュレーションによる経験的誤り率と理論的誤り率を比較した。 0.75
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
Figure 2. Causal graph with N nodes used in simulations. 図2。 シミュレーションで使用されるnノードの因果グラフ。 0.75
ical error rate determined by Theorem 1 in Figure 3. 図3の Theorem 1 で決定される ical error rate 0.88
We note that our results were up to a multiplicative constant, and, when these constants were explicitly calculated, the number of samples proved to be quite conservative. 結果は乗算定数までであり,これらの定数が明示的に計算された場合,標本数は極めて保守的であることがわかった。 0.74
There are a few sources of conservativeness in our analysis. 私たちの分析には保守性の源がいくつかある。 0.67
First, the union bound used to control the family-wise error rate is conservative. 第一に、ファミリーワイズエラー率を制御するために使用される結合結合は保守的である。 0.57
Second, our analysis can only guarantee confidence when every conditional independence test is accurate; however, in practice, we may still recover the correct causal graph even when some tests fail. 第二に、条件付き独立性テストが正しい場合にのみ信頼性を保証できるが、実際には、いくつかのテストが失敗した場合でも、正しい因果グラフを回復することができる。 0.63
For example, when N = 3, if the X1 ⊥⊥ X2 test evaluates to f alse but the independence test X1 ⊥⊥ X2|X3 evaluates to true, the true causal graph will be recovered. 例えば、N = 3 の場合、X1 × X2 テストが f alse と評価されるが、独立テスト X1 × X2|X3 が true と評価すると、真の因果グラフが回復する。 0.79
However, this is difficult to use in any confidence level guarantees: it is difficult to determine which tests can fail while guaranteeing recovery of the true causal graph, especially without knowledge of the true causal structure. 真の因果グラフの回復を保証しながら、特に真の因果構造を知ることなく、どのテストが失敗するかを決定することは困難である。
訳抜け防止モード: しかし、これはどんな信頼度レベルの保証でも使うのが難しい:どのテストが失敗するかを決めるのは難しい。 真の因果グラフの回復を保証する 特に本当の因果構造を知らずに。
0.68
We note that the sample complexity rates are relatively representative of the empirical rates up to a scaling constant, which suggests that these bounds, though conservative, may still provide a useful quantification of the benefits of domain expertise. サンプルの複雑さ率は、スケール定数までの経験的率の比較的代表的であり、これらの境界は保守的であるが、ドメインの専門知識の利点の有用な定量化を提供する可能性があることを示唆している。 0.68
5.2. Results for PC Algorithm 5.2. PCアルゴリズムの結果 0.74
We conducted a similar comparison for the PC algorithm in Figure 4, compared with the theoretical rates in Corollary 3. 図4ではPCのアルゴリズムを,図3では理論的に比較した。
訳抜け防止モード: 図4で類似したPCアルゴリズムの比較を行った。 Corollary 3 の理論的レートと比較する。
0.79
Similar to the IC case, we see that the rates seem accurate up to a multiplicative constant. ICの場合と同様に、レートは乗算定数まで正確であることがわかります。 0.58
Additionally, the multiplicative constant is far better due to the sparsity prior reducing the error introduced by the union bound. さらに、結合境界によって導入された誤差を減らす前に、疎さのために乗算定数ははるかに優れています。 0.55
6. Closing Remarks In this paper, we outlined the sample complexity of the IC algorithm in the absence of a CI oracle. 6. 本論文では,CIオーラクルが存在しない場合のICアルゴリズムの複雑性について概説した。 0.79
When domain expertise or other a priori knowledge can be modeled with a partial CI oracle, we have specified the sample complexity of the IC algorithm with this side information. ドメインの専門知識やその他の優先知識を部分的なCIオーラクルでモデル化できる場合には、このサイド情報でICアルゴリズムのサンプル複雑さを指定しています。 0.71
These results were derived by combining recent bounds on the sample complexity of conditional independence testing, an analysis of the graph traversal in the IC algorithm, and family-wise error rate correction methods. これらの結果は、最近の条件付き独立試験の複雑さ、ICアルゴリズムにおけるグラフトラバーサルの解析、および家族単位の誤差率補正法を組み合わさったものである。 0.84
These sample complexity rates can serve as a guiding principle for experi- これらのサンプルの複雑さは実験の指針となりうる- 0.76
Figure 3. A comparison of the empirical error rate for our causal model using the IC algorithm, compared with our theoretical guarantees. 図3。 ICアルゴリズムを用いた因果モデルに対する経験的誤差率の比較と理論的保証との比較を行った。 0.81
The empirical rate is calculated based on 1000 trials. 実験率は1000の試験に基づいて計算される。 0.76
N represents the number of nodes in the causal graph model of Figure 2. N は図 2 の因果グラフモデルにおけるノード数を表す。 0.82
Figure 4. A comparison of the empirical error rate for our causal model using the PC algorithm with a sparsity prior of R = 1, compared with our theoretical guarantees. 図4。 r = 1以前のスパーシティを持つpcアルゴリズムを用いた因果モデルにおける経験的誤差率と理論的な保証との比較を行った。 0.78
The empirical rate is calculated based on 1000 trials. 実験率は1000の試験に基づいて計算される。 0.76
N represents the number of nodes in the causal graph model of Figure 2. N は図 2 の因果グラフモデルにおけるノード数を表す。 0.82
ment design when passively observed data is available: an experiment can be modeled as knowing the independence (or lack thereof) of two random variables conditioned on a particular context. 実験は、特定の文脈で条件付けられた2つの確率変数の独立性(またはその欠如)を知るものとしてモデル化することができる。 0.78
Thus, our results provide a quantifiable metric to evaluate which experiments (if conducted) can best improve the confidence of causal discovery tests, in the presence of both passively and actively collected data. そこで本研究では,受動的かつアクティブに収集されたデータの存在下で,どの実験が因果的発見テストの信頼性を最も高めるかを評価するための定量化可能な指標を提供する。 0.72
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
References Acharya, J., Bhattacharyya, A., Daskalakis, C., and Kandasamy, S. Learning and testing causal models with interventions. Acharya, J., Bhattacharyya, A., Daskalakis, C., and Kandasamy, S. Learning and testing causal model with interventionsを参照。 0.86
In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R。 0.84
(eds. ), Advances in Neural Information Processing Systems, volume 31, pp. (eds)。 ) 神経情報処理システムの進歩, 巻31, pp。 0.73
9447–9460, 2018. 9447–9460, 2018. 0.84
Aliferis, C. F., Statnikov, A., Tsamardinos, I., Mani, S., and Koutsoukos, X. D. Local causal and markov blanket induction for causal discovery and feature selection for classification part i: Algorithms and empirical evaluation. Aliferis, C. F., Statnikov, A., Tsamardinos, I., Mani, S., and Koutsoukos, X. D. Local causal and markov blanket induction for causal discovery and features selection for classification part i: Algorithms and empirical evaluation。 0.88
Journal of Machine Learning Research, 11(7):171–234, 2010. Journal of Machine Learning Research, 11(7):171–234, 2010。 0.94
Canonne, C. L., Diakonikolas, I., Kane, D. M., and Stewart, A. Canonne, C.L., Diakonikolas, I., Kane, D.M., and Stewart, A. 0.92
Testing conditional independence of discrete distributions. 離散分布の条件独立性をテストする。 0.76
In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 第50回ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp。 0.58
735–748, 2018. 735–748, 2018. 0.84
Glymour, C., Zhang, K., and Spirtes, P. Review of causal discovery methods based on graphical models. Glymour, C., Zhang, K. and Spirtes, P. Review of causal discovery methods based on graphical model。 0.82
Frontiers in Genetics, 10:524, 2019. The Frontiers in Genetics, 10:524, 2019。 0.84
Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G. Sample efficient active learning of causal trees. Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G。
訳抜け防止モード: Greenewald, K., Katz, D., Shanmugam, K. Magliacane, S., Kocaoglu, M., Boix Adsera, E. and Bresler, G. Sample efficient active learning of causal trees。
0.86
In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alch´e-Buc, F., Fox, E., and Garnett, R. Wallach, H., Larochelle, H., Beygelzimer, A., d'Alch ́e-Buc, F., Fox, E., and Garnett, R。 0.97
(eds. ), Advances in Neural Information Processing Systems, volume 32, pp. (eds)。 ), 神経情報処理システムの進歩, ボリューム32, pp。 0.74
14302–14312, 2019. 14302–14312, 2019. 0.84
Hoyer, P., Janzing, D., Mooij, J. M., Peters, J., and Sch¨olkopf, B. Nonlinear causal discovery with additive noise models. Hoyer, P., Janzing, D., Mooij, J.M., Peters, J., and Sch solkopf, B. 添加ノイズモデルを用いた非線形因果的発見。 0.87
In Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L. Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L。 0.77
(eds. ), Advances in Neural Information Processing Systems, volume 21, pp. (eds)。 ) 神経情報処理システムの進歩, 第21巻, pp。 0.74
689–696, 2009. 689–696, 2009. 0.84
Imbens, G. W. and Rubin, D. B. Causal Inference for Statistics, Social, and Biomedical Sciences. Imbens, G. W. and Rubin, D. B. Causal Inference for Statistics, Social, and Biomedical Sciences 0.97
Cambridge University Press, 2015. ケンブリッジ大学出版局、2015年。 0.58
Jaber, A., Zhang, J., and Bareinboim, E. Causal identification under Markov equivalence: Completeness results. Jaber, A., Zhang, J., and Bareinboim, E. Causal Identification under Markov equivalence: Completeness results。 0.85
In Chaudhuri, K. and Salakhutdinov, R. Chaudhuri, K. and Salakhutdinov, R。 0.73
(eds. ), Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. (eds)。 第36回機械学習国際会議(international conference on machine learning, volume 97, pp.)の報告 0.80
2981–2989, 2019. 2981–2989, 2019. 0.84
Kumor, D., Cinelli, C., and Bareinboim, E. Efficient identification in linear structural causal models with auxiliary cutsets. Kumor, D., Cinelli, C. and Bareinboim, E. 補助カットセットを持つ線形構造因果モデルにおける効率的な同定 0.85
In III, H. D. and Singh, A. iii, h. d. and singh, a. 0.72
(eds. ), Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. (eds)。 第37回機械学習国際会議(international conference on machine learning, volume 119, pp。 0.79
5501–5510, 2020. 5501–5510, 2020. 0.84
Lee, S. and Bareinboim, E. Causal effect identifiability under partial-observabilit y. Lee, S. and Bareinboim, E. Causal effect identifiability under partial-observabilit y 0.94
In III, H. D. and Singh, A. iii, h. d. and singh, a. 0.72
(eds. ), Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. (eds)。 第37回機械学習国際会議(international conference on machine learning, volume 119, pp。 0.79
5692–5701, 2020. 5692–5701, 2020. 0.84
Marx, A. and Vreeken, J. Marx, A. and Vreeken, J。 0.91
Testing conditional independence on discrete data using stochastic complexity. 確率的複雑性を用いた離散データの条件付き独立性検証 0.68
In Chaudhuri, K. and Sugiyama, M. m. chaudhuri, k. and sugiyama, m. 0.83
(eds. ), Proceedings of Machine Learning Research, volume 89, pp. (eds)。 ) Proceedings of Machine Learning Research, Volume 89, pp。 0.77
496–505, 2019. 496–505, 2019. 0.84
Matey Neykov, Sivaraman Balakrishnan, L. W. Minimax optimal conditional independence testing. Matey Neykov, Sivaraman Balakrishnan, L. W. Minimax 最適条件独立テスト。 0.88
arXiV, 2020. arXiV、2020年。 0.85
Meek, C. Causal inference and causal explanation with background knowledge. Meek, C. Causal inference and causal explain with background knowledge 0.78
In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI’95, pp. 第11回人工知能の不確実性会議(UAI'95, pp.)に参加して 0.63
403–410, San Francisco, CA, USA, 1995. 403-410, San Francisco, CA, USA, 1995 0.76
Morgan Kaufmann Publishers Inc. Morgan Kaufmann Publishers Inc. 0.85
Miller, R. G. J. ミラー、R.G.J。 0.60
Simultaneous Statistical Inference. Springer- 同時統計的推測。 Springer 0.77
Verlag New York, 2nd edition, 1981. Verlag New York, 2nd Edition, 1981年。 0.92
Mitrovic, J., Sejdinovic, D., and Teh, Y. W. Causal inference via kernel deviance measures. Mitrovic, J., Sejdinovic, D., and Teh, Y. W. Causal inference by kernel deviance measures。 0.89
In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R。 0.84
(eds. ), Advances in Neural Information Processing Systems, volume 31, pp. (eds)。 ) 神経情報処理システムの進歩, 巻31, pp。 0.73
6986–6994, 2018. 6986–6994, 2018. 0.84
Pearl, J. Causality: Models, Reasoning and Inference. Pearl、J.Causality:モデル、推論、推論。 0.73
Cam- bridge University Press, 2nd edition, 2013. カム ブリッジ大学出版、第2版、2013年。 0.64
Pearl, J. and Verma, T. S. A theory of inferred causation. pearl, j. and verma, t. s. a theory of inferred causation. 0.90
In Prawitz, D., Skyrms, B., and Westerst˚ahl, D. Prawitz、D.、Skyrms、B.、およびWesterst ザヘル、D.で。 0.69
(eds. ), Logic, Methodology and Philosophy of Science IX, volume 134 of Studies in Logic and the Foundations of Mathematics, pp. (eds)。 論理学、方法論、科学哲学 IX, Volume 134 of Studies in Logic and the Foundations of Mathematics, pp。 0.76
789–811. Elsevier, 1995. 789–811. 1995年、エルセヴィエ。 0.67
Schl¨uter, F. A survey on independence-based markov networks learning. Schl suter, F. 独立性に基づくマルコフネットワーク学習に関する調査 0.71
Artificial Intelligence Review, 42(4): 1069–1093, 2014. 人工知能レビュー, 42(4): 1069–1093, 2014 0.75
Shah, R. D. and Peters, J. Shah, R. D. and Peters, J. 0.98
The hardness of conditional independence testing and the generalised covariance measure. 条件付き独立性テストの難しさと一般化共分散尺度 0.78
Ann. Statist., 48(3):1514–1538, 06 2020. アン。 統計, 48(3):1514-1538, 06 2020。 0.68
Shimizu, S., Hoyer, P. O., Hyv¨arinen, A., and Kerminen, A. 清水, S., Hoyer, P. O., Hyv sarinen, A., Kerminen, A。 0.75
A linear non-gaussian acyclic model for causal discovery. 因果発見のための線形非ガウス非巡回モデル 0.71
J. Mach. Learn. J. Mach 学ぶ。 0.72
Res., 7:2003–2030, 2006. 2006年7月7日 - 2030年。 0.51
Spirtes, P., Glymour, C., and Scheines, R. Causation, Pre- Spirtes, P., Glymour, C., and Scheines, R. Causation, Pre- 0.96
diction, and Search. MIT Press, 2nd edition, 2001. 辞書と検索。 MIT Press, 2nd Edition, 2001年。 0.66
Sun, X., Janzing, D., Sch¨olkopf, B., and Fukumizu, K. A kernel-based causal learning algorithm. Sun, X., Janzing, D., Sch solkopf, B. and Fukumizu, K. A kernel-based causal learning algorithm。 0.97
In Proceedings of the 24th International Conference on Machine Learning, pp. 第24回In Proceedings of the 24th International Conference on Machine Learning, pp. 0.86
855–862, 2007. 855–862, 2007. 0.84
Verma, T. and Pearl, J. Verma, T. and Pearl, J。 0.91
An algorithm for deciding if a set of observed independencies has a causal explanation. 観測された無依存な集合が因果的説明を持つかどうかを決定するアルゴリズム。 0.63
In Dubois, D., Wellman, M. P., D’Ambrosio, B., and Smets, P. ドゥブロワ、D.、Wellman、M.P.、D’Ambrosio、B.、およびSmets、P.で。 0.75
(eds. ), Uncertainty in Artificial Intelligence, pp. (eds)。 ) 人工知能の不確実性, pp。 0.74
323– 330. Morgan Kaufmann, 1992. 323– 330. モーガン・カウフマン、1992年。 0.72
英語(論文から抽出)日本語訳スコア
On the Sample Complexity of Causal Discovery and the Value of Domain Expertise 因果的発見のサンプル複雑さとドメインエキスパートの価値について 0.80
Wooldridge, J. M. Introductory Econometrics: A Modern Wooldridge, J. M. Introductory Econometrics: A Modern 0.98
Approach. Cengage Learning, 7th edition, 2019. アプローチ。 Cengage Learning, 7th edition, 2019。 0.77
Zhang, K. and Hyv¨arinen, A. Zhang, K. and Hyv sarinen, A. 0.90
On the identifiability of the post-nonlinear causal model. 非線型因果モデルの同定可能性について 0.63
In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp. 第25回人工知能の不確実性会議の議事録, pp。 0.59
647–655, 2009. 647–655, 2009. 0.84
Zhang, K., Peters, J., Janzing, D., and Sch¨olkopf, B. Kernelbased conditional independence test and application in causal discovery. Zhang, K., Peters, J., Janzing, D., Sch solkopf, B. Kernelによる条件付き独立試験と因果発見への応用 0.90
In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pp. 第27回人工知能の不確実性会議の議事録, pp。 0.56
804–813, 2011. 804–813, 2011. 0.84
Zhang, Y., Zhang, Z., Liu, K., and Qian, G. An improved iamb algorithm for markov blanket discovery. Zhang、Y.、Zhang、Z.、Liu、K.、Qian、G. Markovブランケット発見のための改良されたiambアルゴリズム。
訳抜け防止モード: Zhang, Y., Zhang, Z., Liu, K. そして Qian, G. Markov ブランケット発見のための改良された iamb アルゴリズム。
0.92
Journal of Computers, 5(11):1755–1761, 2010. Journal of Computers, 5(11):1755–1761, 2010年。 0.86
                     ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。