論文の概要、ライセンス

# (参考訳) ハダマールの力と製品の混合物の同定 [全文訳有]

Hadamard Powers and the Identification of Mixtures of Products ( http://arxiv.org/abs/2101.11688v1 )

ライセンス: CC BY 4.0
Spencer L. Gordon, Leonard J. Schulman(参考訳) 行列のアダマール力は、その列の部分集合のすべてのアダマール積からなる行列である。 我々は,ハダマールパワーがフルカラムランクのときに関するいくつかの結果を得る。 この問題は次の問題の中心である: 2進確率変数の一覧に$k$の積分布の混合を与えられた場合、$X_1,\ldots,X_n$は、その確率モデルを$X_i$の合同統計量から特定できる。

The Hadamard Power of a matrix is the matrix consisting of all Hadamard products of subsets of its rows. We obtain several results concerning when a Hadamard Power has full column rank. This question in turn is central to the following problem: given a mixture of $k$ product distributions on a list of binary random variables $X_1,\ldots,X_n$, can the probability model be identified from the joint statistics of the $X_i$.
公開日: Wed, 27 Jan 2021 21:07:54 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n a J 1 2 0 2 n a J 0.85
7 2 ] G L . 7 2 ] G L。 0.81
s c [ 1 v 8 8 6 1 1 sc [ 1 v 8 8 6 1 1 0.68
. 1 0 1 2 : v i X r a . 1 0 1 2 : v i X r a 0.85
Hadamard Powers and the Identification of Mixtures of Products ハダマールの力と製品の混合物の同定 0.77
Spencer L. Gordon∗ Spencer L. Gordon∗ 0.78
Leonard J. Schulman† レオナルド・J・シュルマン 0.41
January 29, 2021 2021年1月29日 0.76
Abstract The Hadamard Power of a matrix is the matrix consisting of all Hadamard products of subsets of its rows. 概要 行列のアダマール力は、その列の部分集合のすべてのアダマール積からなる行列である。 0.52
We obtain several results concerning when a Hadamard Power has full column rank. 我々は,ハダマールパワーがフルカラムランクのときに関するいくつかの結果を得る。 0.64
This question in turn is central to the following problem: given a mixture of k product distributions on a list of binary random variables X1, . この問題は次の問題の中心である: 二つの確率変数 X1, のリスト上の k 個の積分布の混合を与えられる。 0.72
. . , Xn, can the probability model be identified from the joint statistics of the Xi. . . Xn は、Xi の共同統計から確率モデルを特定することができる。 0.79
Introduction 1 The Hadamard product for row vectors u = (u1, . はじめに 1 行ベクトル u = (u1, .) の Hadamard 積。 0.66
. . , uk), v = (v1, . . . , uk), v = (v1, 。 0.82
. . , vk) is the mapping (cid:12) : Rk × Rk → Rk given by . . , vk) は写像 (cid:12) : Rk × Rk → Rk である。 0.85
u (cid:12) v := (u1v1, . u (cid:12) v := (u1v1, 。 0.74
. . , ukvk) . . 略称:ukvk)。 0.73
The identity for this product is the all-ones vector 1. この積の恒等式は全単ベクトル 1 である。 0.66
We associate with vector v the linear operator v(cid:12) = diag(v), a k × k diagonal matrix, so that 我々はベクトル v と線形作用素 v(cid:12) = diag(v), a k × k 対角行列を関連付ける。 0.77
u · v(cid:12) = v (cid:12) u. u · v(cid:12) = v (cid:12) u。 0.89
Throughout this paper m is a real matrix with row set [n] := {1, . この論文を通して m は行集合 [n] := {1, を持つ実行列である。 0.75
. . , n} and column set [k]; write mi for a row and mj for a column. . . , n} and column set [k]; write mi for a row and mj for a column. 0.84
Definition 1. The Hadamard Power of m, written H(m), is the 2n × k matrix with rows mS for all S ⊆ [n], where, for S = {i1, . 定義1。 H(m) と書かれた m のハダマール力(英語版)(Hadamard Power of m)は、2n × k 行列(英語版)であり、S = {i1, . に対してすべての S に対して mS 行を持つ。
訳抜け防止モード: 定義1。 H(m ) と書かれる m のアダマール力は、すべての S > [ n ] に対して行 mS を持つ 2n × k 行列である。 ここで , for S = { i1 , .
0.77
. . , i(cid:96)}, mS = mi1 (cid:12) ··· (cid:12) mi(cid:96); equivalently mj For a matrix Q and nonempty sets R of rows and C of columns, let Q|C columns and rows (with either index omitted if all rows or columns are retained). . . i(cid:96)}, mS = mi1 (cid:12) · ... (cid:12) mi(cid:96); 等価な mj 行列 Q および非空集合 R の行と列 C に対して、Q|C 列と行 (すべての行または列が保持されている場合はインデックスが省略される) を許可する。 0.81
R be the restriction of Q to those r は q のそれらへの制限である 0.72
S =(cid:81) S =(cid:81) 0.88
i∈S mj i . i∈S mj 私は... 0.51
(In particular m∅ = 1.) (特に m は 1 である)。 0.74
Motivated by the problem of source identification of a mixture of product distributions on binary random variables (see Section 5), we are interested in the following two questions: (1) If H(m) has full column rank, must there exist a subset R of the rows, of bounded size, such that H(m|R) has full column rank? 1) h(m) が全列ランクを持つならば、h(m|r) が全列ランクを持つような有界サイズの行の部分集合 r が存在しなければならないか?
訳抜け防止モード: 二元確率変数上の積分布の混合の情報源同定の問題に動機づけられた(第5節参照) 以下の2つの質問に興味がある: ( 1 ) H(m ) が完全列ランクである場合。 行の集合 R が存在しなければならず、有界な大きさである。 H(m|R ) が完全列ランクを持つような?
0.79
(2) In each row of m, assign distinct colors to the distinct real values. (2) m の各行において、異なる色を異なる実値に割り当てる。 0.71
Is there a condition on the coloring that ensures H(m) has full column rank? H(m) が全列ランクであることを保証する色付けに条件はあるか? 0.85
In answer to the first question we show in Section 2: Theorem 2. 最初の質問に答えるために、セクション2: Theorem 2で示します。 0.83
If H(m) has full column rank then there is a set R of no more than k − 1 of the rows of m, such that H(m|R) has full column rank. H(m) が全列ランクを持つとき、m の行の k − 1 以上の集合 R が存在し、H(m|R) が全列ランクを持つ。 0.71
∗ † Engineering and Applied Science, California Institute of Technology, slgordon@caltech.edu . ∗ † engineering and applied science, california institute of technology, slgordon@caltech.edu .(英語) 0.80
Engineering and Applied Science, California Institute of Technology, schulman@caltech.edu . engineering and applied science, california institute of technology, schulman@caltech.edu .(英語) 0.74
Research supported in part by 部分的に支持された研究 0.70
NSF grant CCF-1909972. NSFはCF-1909972を付与する。 0.47
1 1 0.85
英語(論文から抽出)日本語訳スコア
Considering the more combinatorial second question, observe that if m possesses two identical columns then the same is true of H(m), and so it cannot be full rank. より組合せ的な第二の質問を考えると、m が 2 つの同一の列を持つならば H(m) は同値であり、従って完全階数ではない。 0.73
Extending this further, suppose there are three columns C in which only one row r has more than one color. これを拡張して、ある列 r が 1 つ以上の色を持つ列 C が 3 つあると仮定する。 0.80
Then Rowspace H(m|C) is spanned by 1|C and r|C, so again H(m) cannot be full rank. このとき、ロー空間 H(m|C) は 1|C と r|C で表されるので、再び H(m) はフルランクにはならない。 0.63
Motivated by these necessary conditions, set: これらの必要な条件により動機付けられるもの 0.56
Definition 3. For a matrix Q let NAE(Q) be the set of nonconstant rows of Q (NAE=“not all equal”); let ε(Q|C) = |NAE(Q|C)| − |C|; and let ε(Q) = minC(cid:54)=∅ ε(Q|C). 定義3。 行列 Q に対して、NAE(Q) を Q (NAE= “not all equal”) の非定数列の集合とし、ε(Q|C) = |NAE(Q|C)| − |C| とし、ε(Q) = minC(cid:54)= ε(Q|C) とする。 0.79
If ε(Q) ≥ −1 we say Q satisfies the NAE condition. ε(Q) ≥ −1 であれば、Q は NAE 条件を満たす。 0.80
In answer to the second question we have the following: 2つ目の質問に対する答えは次のとおりです。 0.70
Theorem 4. If m satisfies the NAE condition then (a) There is a restriction of m to some k − 1 rows R such that ε(m|R) = −1. 理論4。 m が NAE 条件を満たすと (a) ε(m|R) = −1 となるような k − 1 行 R に対する m の制限が存在する。 0.73
(b) H(m) is full column rank. (b) H(m) は全列ランクである。 0.83
(As a consequence also H(m|R) is full column rank.) (その結果、H(m|R)もフルカラムランクとなる。) 0.84
Apparently the only well-known example of the NAE condition is when m contains k−1 rows which are identical and whose entries are all distinct. NAE条件の唯一のよく知られた例は、m が同一でエントリがすべて異なる k−1 行を含む場合である。 0.75
Then the vectors m∅, m{1}, m{1,2}, . すると、ベクトル m , m{1}, m{1,2}, が成り立つ。 0.87
. . , m{1,...,k−1} form a nonsingular Vandermonde matrix. . . , m{1,...,k−1} は非特異なヴァンダーモンド行列を形成する。 0.79
This example shows that the bound of k − 1 in (a) is best possible. この例は (a) における k − 1 の有界が最良であることを示す。 0.81
For another example in which the NAE condition ensures that rank H(m) = k, take the (k − 1)-row matrix with mj i = 1/2 for i > j. NAE条件がランク H(m) = k を保証している別の例では、mj i = 1/2 の (k − 1)-ロー行列を i > j に対して取る。 0.84
Here the NAE condition is only minimally satisfied, in that for every (cid:96) ≤ k there are (cid:96) columns C s.t. ここで NAE 条件は最小限に満たされ、すべての (cid:96) ≤ k に対して (cid:96) 列 C s.t が存在する。 0.75
ε(m|C) = −1. ε(m|C) = −1。 0.81
For k > 3 the NAE condition is no longer necessary for H(m) to have full column rank. k > 3 の場合、H(m) が全列ランクを持つために NAE 条件はもはや不要である。 0.82
E.g., for k = 2(cid:96), the (cid:96) × k “Hamming matrix” mj i = (−1)ji where j is an (cid:96)-bit string j = (j1, . 例えば、k = 2(cid:96) に対して、 (cid:96) × k “Hamming matrix” mj i = (−1)ji は (cid:96)-ビット文字列 j = (j1, ) である。 0.88
. . , j(cid:96)), forms H(m) = the Fourier transform for the group (Z/2)(cid:96) (often called a Hadamard matrix), which is invertible. . . , j(cid:96)) は H(m) = フーリエ変換 (Z/2)(cid:96) (しばしばハダマール行列と呼ばれる) を形成し、可逆である。 0.82
Furthermore, almost all (in the sense of Lebesgue measure) (cid:100)lg k(cid:101) × k matrices m form a full-rank H(m). さらに、ほとんどすべての(ルベーグ測度という意味で) (cid:100)lg k(cid:101) × k 行列 m はフルランク h(m) を形成する。 0.68
(This is because det H(m) is a polynomial in the entries of m, and the previous example shows the polynomial is nonzero.) (これはデット h(m) が m の成分の多項式であり、前者は多項式が 0 でないことを示すからである)。 0.73
Despite this observation, the Vandermonde case, in which k − 1 rows are required, is very typical, as it is what arises in H(m) for a mixture model of observables Xi that are iid conditional on a hidden variable. この観察にもかかわらず、k − 1 行が要求されるヴァンダーモンドの場合は非常に典型的であり、これは隠れた変数上で条件付きである観測可能な Xi の混合モデルに対して H(m) で生じるものである。 0.82
i = 1 for i ≤ j and mj i ≤ j と mj に対する i = 1 0.89
2 Some Theory for Hadamard Products, and a Proof of Theorem 2 For v ∈ Rk and U a subspace, extend the definition v(cid:12) to 2 Hadamard プロダクトのための理論、および v ∈ Rk および U の部分空間に対する定理 2 の証明は、定義 v(cid:12) を v(cid:12) に拡張する。 0.72
and introduce the notation v(cid:12)(U ) = {u · v(cid:12) : u ∈ U} 表記法を導入し v(cid:12)(U ) = {u · v(cid:12) : u ∈ U} 0.83
v ¯(cid:12)(U ) = span{U ∪ v(cid:12)(U )}. v (cid:12)(U ) = span{U ) v(cid:12)(U )}。 0.82
We want to understand which subspaces U are invariant under v ¯(cid:12). どの部分空間 U が v の下で不変であることを理解したい(cid:12)。 0.62
Let v have distinct values λ1 > . v に異なる値 λ1 > を持つ。 0.77
. . > λ(cid:96) for (cid:96) ≤ k. Let the polynomials pv,i (i = 1, . . . > λ(cid:96) for (cid:96) ≤ k. 多項式 pv,i (i = 1, ) とする。 0.84
. . , (cid:96)) of degree (cid:96)− 1 be the Lagrange interpolation polynomials for these values, so pv,i(λj) = δij (Kronecker delta). . . 次数 (cid:96) の (cid:96)− 1 はこれらの値のラグランジュ補間多項式なので、pv,i(λj) = δij (クロネッカーデルタ) である。 0.82
Let B(v) denote the partition of [k] into blocks B(v)(i) = {j : vj = λi}. B(v) は[k] のブロック B(v)(i) = {j : vj = λi} への分割を表す。 0.81
Let V(i) be the space spanned by the elementary basis vectors in B(v)(i), and P(i) the projection onto V(i) w.r.t. V(i) を B(v)(i) における基本基底ベクトルで表される空間とし、P(i) を V(i) w.r.t への射影とする。 0.88
standard inner product. 標準的な内部プロダクト。 0.65
We have the matrix equation algebra, which we denote AB(v). 行列方程式がある 代数学では ab(v) と表記される。 0.59
The identity of the algebra is I =(cid:80) P(i). 代数の恒等式は I = (cid:80) P(i) である。 0.73
pv,i(v(cid:12)) = P(i). pv,i(v(cid:12)) = P(i)。 0.89
The collection of all linear combinations of the matrices P(i) is a commutative algebra, the B(v) projection 行列 P(i) のすべての線型組合せの集合は可換代数 B(v) 射である 0.66
Definition 5. A subspace of Rk respects B(v) if it is spanned by vectors each of which lies in some V(i). 定義5。 Rk の部分空間は B(v) を、そのそれぞれがいくつかの V(i) に属するベクトルにまたがるならば尊重する。 0.77
2 2 0.85
英語(論文から抽出)日本語訳スコア
j(cid:54)=i V(j). j(cid:54)=i V(j)。 0.88
Lemma 6. Subspace U⊥ respects B(v) if U does. 第6回。 部分空間 U は U が成り立つと B(v) を尊重する。 0.58
For U respecting B(v) write U = span((cid:83) U(i)) for U(i) ⊆ V(i). B(v) に関して U に対して U = span((cid:83) U(i)) と書く。 0.66
Let D(i) = (U(i))⊥ ∩ V(i). d(i) = (u(i))) を v(i) とする。 0.71
Then (U(i))⊥ = D(i) ⊕(cid:76) Proof. すると (U(i)) = D(i) > (cid:76) が証明される。 0.75
In general, (span(W ∪ W (cid:48)))⊥ = W ⊥ ∩ W (cid:48)⊥. 一般に、 (span(W ) W (cid:48)) ) = W (W ) W (cid:48) である。 0.85
So U⊥ =(cid:84)(U(i))⊥ =(cid:76) D(i). よって U は =(cid:84)(U(i)) は =(cid:76) D(i) となる。 0.74
Lemma 7. Subspace U respects B(v) iff U =(cid:76)(P(i)U ). 第7回。 部分空間 U は B(v) iff U =(cid:76)(P(i)U を尊重する。 0.68
are necessarily orthogonal, U =(cid:76) V (cid:48) U =(cid:76) V (cid:48) である。 0.66
Proof. (⇐): Because this gives an explicit representation of U as a direct sum of subspaces each restricted to (i) ⊆ V(i); since these subspaces some V(i). 証明。 これは u を部分空間の直和として明示的な表現を与えるからであり、各部分空間は v(i) と v(i) に制限されるからである。 0.64
(⇒): By definition U is spanned by some collection of subspaces V (cid:48) (i). 定義により、u は部分空間 v (cid:48) (i) のいくつかの集合にまたがる。 0.70
Moreover, since P(i) annihilates V(j), j (cid:54)= i, and is the identity on V(i), さらに、P(i) は V(j), j (cid:54)= i を消滅させるので、V(i) 上の正体である。 0.78
it follows that each V (cid:48) それぞれの V (cid:48) に従う。 0.76
(i) = P(i)U . (i) = p(i)u である。 0.81
Theorem 8. Subspace U is invariant under v ¯(cid:12) iff U respects B(v). 理論8。 部分空間 U は b(v) を iff U が尊重する v(cid:12) の下で不変である。 0.62
Proof. (⇐): It suffices to show U⊥ is invariant under v ¯(cid:12). 証明。 注: U が v の下で不変であることを示すのに十分である(cid:12)。 0.62
By the previous lemma, it is equivalent to suppose 前の補題では、それは仮定と等価である 0.58
that U⊥ respects B(v). は B(v) を尊重する。 0.75
So let d ∈ U⊥ and write d = (cid:80) di, di ∈ D(i). よって d ∈ U と書けば d = (cid:80) di, di ∈ D(i) となる。 0.87
Then v (cid:12) di = λidi ∈ D(i). このとき v (cid:12) di = λidi ∈ D(i) となる。 0.72
So v (cid:12) d =(cid:80) v (cid:12) di ∈(cid:76) D(i) = U⊥. したがって v (cid:12) d = (cid:80) v (cid:12) di ∈ (cid:76) D(i) = U となる。 0.80
In particular for a = P(i). 特に a = P(i) に対して。 0.81
So U ⊇ (cid:76)(P(i)U ). 以下 (cid:76)(p(i)u) である。 0.66
On the other hand, since (cid:80) P(i) = I, U = ((cid:80) P(i))U ⊆(cid:76)(P(i)U ). 一方、 (cid:80) P(i) = I であるから、U = ((cid:80) P(i)) U (cid:76)(P(i)U ) となる。 0.87
So U =(cid:76)(P(i)U ). したがって、U = (cid:76)(P(i)U )。 0.71
Now apply Lemma 7. 今Lemma 7を適用します。 0.54
(⇒): If U = v ¯(cid:12)(U ) then these also equal v ¯(cid:12)(v ¯(cid:12)(U )), etc., so U is an invariant space of AB(v), meaning, aU ⊆ U for any a ∈ AB(v). U = v s(cid:12)(U ) ならば、これらも v s(cid:12)(v s(cid:12)(U )) 等であり、したがって U は任意の a ∈ AB(v) に対する AB(v) の不変空間である。 0.77
The symbol ⊂ is reserved for strict inclusion. 記号は、厳格に包含される。 0.58
Lemma 9. If S, T ⊆ [n] and Rowspace H(m|S) ⊂ Rowspace H(m|S∪T ), then there is a row t ∈ T such that Rowspace H(m|S) ⊂ Rowspace H(m|S∪{t}). レマ9。 S と T と Rowspace H(m|S) と Rowspace H(m|S) が成り立つと、Rowspace H(m|S) と Rowspace H(m|S\{t}) が成り立つ列 t ∈ T が存在する。 0.72
Proof. Without loss of generality S, T are disjoint. 証明。 一般性 S が失われなければ、T は非随伴である。 0.59
Let T (cid:48) ⊆ T be a smallest set s.t. T を最小集合 s.t とする(cid:48)。 0.80
∃S(cid:48) ⊆ S s.t. S (cid:48) ^ S s.t。 0.70
mS(cid:48) (cid:12) mT (cid:48) /∈ Rowspace H(mS). mS(cid:48) (cid:12) mT (cid:48) /∈ Rowspace H(mS)。 0.83
Select any t ∈ T (cid:48) and write mS(cid:48) (cid:12) mT (cid:48) = mS(cid:48) (cid:12) mT (cid:48)−{t} (cid:12) mt. 任意の t ∈ T (cid:48) を選択し、 mS(cid:48) (cid:12) mT (cid:48) = mS(cid:48) (cid:12) mT (cid:48)−{t} (cid:12) mt と書く。 0.78
By minimality of T (cid:48), mS(cid:48) (cid:12) mT (cid:48)−{t} ∈ Rowspace H(mS). T (cid:48) の最小性により、mS(cid:48) (cid:12) mT (cid:48)−{t} ∈ Rowspace H(mS) となる。 0.78
But then mS(cid:48) (cid:12) mT (cid:48) ∈ Rowspace H(mS∪{t}), so Rowspace H(m|S) ⊂ Rowspace H(m|S∪{t}). しかし、mS(cid:48) (cid:12) mT (cid:48) ∈ Rowspace H(mS){t}) なので、Rowspace H(m|S) > Rowspace H(m|S){t} である。 0.80
Theorem 2 is now a consequence of Lemma 9. 理論2は現在、Lemma 9の結果です。 0.64
It follows from Theorem 2 that we can check whether rank H(m) = k in time O(n)k by computing rank H(m|S) Theorem 2 から、計算ランク H(m|S) で時 O(n)k のランク H(m) = k を確認することができる。 0.77
for each S ∈(cid:0) [n] 各 S ∈(cid:0) [n] に対して 0.79
(cid:1). k−1 (cid:1)。 k−1 0.68
3 Combinatorics of the NAE Condition: Proof of Theorem 4 (a) Recall we are to show: 4 (a): If ε(m) ≥ −1 then m has a restriction to some k − 1 rows on which ε = −1. 3 Combinatorics of the NAE Condition: Proof of Theorem 4 (a) Recall we are show: 4 (a): If ε(m) ^ − 1 then m has a limit to some k − 1 rows which ε = −1。 0.79
Proof. We induct on k. The (vacuous) base-case is k = 1. 証明。 k 上の(空でない)基底ケースは k = 1 である。 0.65
For k > 1, we induct on n, with base-case n = k− 1. k > 1 に対して、n を基本ケース n = k− 1 で導出する。 0.80
Supposing the Theorem fails for k, k > 1, let m be a k-column counterexample with least n. Necessarily every row is in NAE(m), and n > k − 1 ≥ 1. k > 1 の定理を仮定すると、m を少なくとも n の k-列逆例とし、必然的にすべての行は nae(m) にあり、n > k − 1 ≥ 1 である。 0.79
We will show m has a restriction m(cid:48) to n − 1 rows, for which ε(m(cid:48)) ≥ −1; this will imply a contradiction because, by minimality of m, m(cid:48) has a restriction to k − 1 rows on which ε = −1. m が n − 1 行に制限 m(cid:48) を持つことを示し、そこで ε(m(cid:48)) である。これは、m(cid:48) の最小値により、 ε = −1 の k − 1 行に制限があることから、矛盾を意味する。 0.85
If ε(m) ≥ 0 then we can remove any single row of m and still satisfy ε ≥ −1. ε(m) ≥ 0 であれば、任意の m の行を取り除いて ε ≥ −1 を満たすことができる。 0.84
Otherwise, ε(m) = −1, so there is a nonempty S such that |NAE(m|S)| = |S| − 1; choose a largest such S. It cannot be that S = [k] (as then n = k − 1). そうでなければ、ε(m) = −1 なので、 |NAE(m|S)| = |S| − 1; が最大の S を選択するような空でない S が存在する。
訳抜け防止モード: そうでなければ、ε(m ) = −1 となる。 空でない S が存在して |NAE(m|S)| = |S| − 1 となる。 S = [ k ] ( ならば n = k − 1 ) は成り立たない。
0.82
Arrange the rows NAE(m|S) as the bottom |S| − 1 rows of the matrix. 列 NAE(m|S) を行列の底 |S| − 1 行として配置する。 0.83
As discussed earlier, for the NAE condition one may regard the distinct real values in each row of m simply as distinct colors; relabel the colors in each row above NAE(m|S) so the color above S is called “white.” (There need be no consistency among the real numbers called white in different rows.) 先述したように、NAE条件では、m の各行の異なる実値を単に異なる色とみなすことができる; NAE(m|S) 上の各行の色を緩和するので、S 上の色は「白」と呼ばれる(異なる行で白と呼ばれる実数の間に整合性は必要ない)。 0.83
See Figure 1. 3 図1参照。 3 0.78
英語(論文から抽出)日本語訳スコア
Figure 1: Argument for Theorem 4 (a). 図1: Theorem 4(a)の議論。 0.73
Upper-left region is white. Entries (t, f (t)) are not white. 左上は白。 エントリ (t, f (t)) は白色ではない。 0.64
R(cid:48)(cid:48) R(cid:48)(cid:48) 0.78
Due to the maximality of |S|, there is no white rectangle on (cid:96) columns and n − |S| − (cid:96) + 1 rows inside m|[k]−S [n]−NAE(m|S ) for any (cid:96) ≥ 1. |S| の最大性のため、任意の (cid:96) ≥ 1 に対して (cid:96) 列と n − |S| − (cid:96) + 1 行の内、m|[k]−S [n]−NAE(m|S ) に白色長方形は存在しない。 0.79
That is to say, if we form a bipartite graph on right vertices corresponding to the columns [k] − S, and left vertices corresponding to the rows [n] − NAE(m|S), with non-white cells being edges, then any subset of the right vertices of size (cid:96) ≥ 1 has at least (cid:96) + 1 neighbors within the left vertices. つまり、列 [k] − s に対応する右頂点上に二分グラフを形成し、非白セルがエッジである行 [n] − nae(m|s) に対応する左頂点を形成すると、サイズ (cid:96) ≥ 1 の右頂点の任意の部分集合は、左頂点内に少なくとも (cid:96) + 1 の近傍を持つ。 0.84
By the induction on k (since S (cid:54)= ∅), for the set of columns [k] − S there is a set R(cid:48)(cid:48) of k − |S| − 1 rows such that ε(m|[k]−S ) = −1. k 上の帰納法 (s (cid:54)= s) により、列 [k] − s の集合に対して ε(m|[k]−s ) = −1 となる k − |s| − 1 行の集合 r(cid:48)(cid:48) が存在する。 0.84
Together with the rows of NAE(m|S) this amounts to at most k − 2 rows, so since n ≥ k, we can find two rows outside this union; delete either one of them, leaving a matrix m(cid:48) with n − 1 rows. NAE(m|S) の行とともに、これはほとんどの k − 2 行に等しいので、n は k の外側にある2つの列を見つけることができる; どちらかの列を削除し、行列 m(cid:48) を n − 1 行で残す。 0.78
This matrix has the rows NAE(m|S) at the bottom, and n − |S| remaining rows which we call R(cid:48). この行列は下部にNAE(m|S) 行を持ち、R(cid:48) と呼ぶ n − |S| 残行を持つ。 0.82
The lemma will follow by showing that ε(m(cid:48)) ≥ −1. 補題は ε(m(cid:48)) ≥ −1 を示すことによって従う。 0.68
In m(cid:48), the induced bipartite graph on right vertices [k]− S and left vertices R(cid:48) has the property that any right subset of size (cid:96) ≥ 1 has a neighborhood of size at least (cid:96) in R(cid:48). m(cid:48) において、右頂点 [k]− s と左頂点 r(cid:48) 上の誘導二部グラフは、サイズ (cid:96) ≥ 1 の任意の右部分集合が少なくとも大きさの近傍(cid:96)を持つ性質を持つ(cid:48)。 0.81
Applying Hall’s Marriage Theorem, there is an injective f : [k] − S → R(cid:48) employing only edges of the graph. ホールの結婚定理を適用すると、グラフの辺のみを用いる単射 f : [k] − s → r(cid:48) が存在する。 0.76
Now consider any set of columns T , T = T1 ∪ T2, T1 ⊆ [k] − S, T2 ⊆ S. We need to show that ε(m|T ) ≥ −1. さて、任意の列集合 T , T = T1 > T2, T1 > [k] − S, T2 > S を考えると、ε(m|T ) ≥ −1 が成り立つ。 0.81
Let R1 = NAE(m|T1 ) ∩ R(cid:48)(cid:48), R2 = NAE(m|T2) ⊆ NAE(m|S), and note that |R1| ≥ |T1| − 1, |R2| ≥ |T2| − 1. R1 = NAE(m|T1 ) > R(cid:48)(cid:48) R2 = NAE(m|T2) > NAE(m|S) とし、 |R1| ≥ |T1| − 1, |R2| ≥ |T2| − 1 とする。 0.72
If T2 = ∅ we simply use R1. T2 = * ならば、単に R1 を使う。 0.70
Likewise if T1 = ∅, we use R2. 同様に、T1 = y ならば R2 を使う。 0.75
If both T1 and T2 are nonempty, NAE(m|T2) ⊆ NAE(m|S), and |NAE(m|T2)| ≥ |T2|−1. T1 と T2 の両方が空でないなら、NAE(m|T2) は NAE(m|S) と |NAE(m|T2)| ≥ |T2|−1 である。 0.63
Now use the matching f . マッチする f を使用します。 0.64
The set of rows f (T1) lies in R(cid:48) and is therefore disjoint from NAE(m|T2). 行 f (T1) の集合は R(cid:48) にあり、したがって NAE(m|T2) と非結合である。 0.66
Moreover since T2 (cid:54)= ∅, every entry (t, j) for t ∈ T2, j ∈ R(cid:48) is white. さらに T2 (cid:54)= s であるため、t ∈ T2 に対するすべてのエントリ (t, j) は、j ∈ R(cid:48) は白である。 0.78
On the other hand due to the construction of f , for every t ∈ T1 the entry (t, f (t)) is non-white. 一方、f の構成のため、すべての t ∈ T1 に対して、エントリ (t, f (t)) は非白色である。 0.81
Therefore every row in f (T1) is in NAE(m|T1∪T2). したがって、f(T1) のすべての行は NAE(m|T1) である。 0.67
So |NAE(m|T1∪T2 )| ≥ |T2|− 1 +|T1|. したがって |NAE(m|T1\T2 )| ≥ |T2|− 1 +|T1| となる。 0.44
Thus ε(m(cid:48)) ≥ −1. したがって ε(m(cid:48)) ≥ −1 である。 0.70
4 From NAE to Rank: Proof of Theorem 4 (b) Recall we are to show: 4 (b): H(m) has full column rank if ε(m) ≥ −1. 4 NAE to Rank: Proof of Theorem 4 (b) Recall to show: 4 (b): H(m) が ε(m) ≥ −1 であれば、全列ランクを持つ。 0.83
4 ST2NAE(m| )SR2[k] - ST1R1R'R''R1f(T )1m'mf 4 ST2NAE(m| )SR2[k] - ST1R1R'R''R1f(T)1mf 0.79
英語(論文から抽出)日本語訳スコア
Proof. The case k = 1 is trivial. 証明。 ケース k = 1 は自明である。 0.70
Now suppose k ≥ 2 and that Theorem 4 (b) holds for all k(cid:48) < k. Any constant rows of m affect neither the hypothesis nor the conclusion, so remove them, leaving m with at least k − 1 rows. ここで k ≥ 2 と Theorem 4 (b) がすべての k(cid:48) < k に対して成り立つことを仮定すると、m の任意の定数列は仮説にも結論にも影響しない。
訳抜け防止モード: ここで k ≥ 2 と Theorem 4 ( b ) がすべての k(cid:48 ) < k に対して成り立つことを仮定する。 仮説も結論も無い だから取り除け m を少なくとも k − 1 行で残す。
0.74
Now pick any set, C, of k − 1 columns of m. By Theorem 4 (a) there are some k − 2 rows of m, call them R(cid:48), on which ε(m|C R(cid:48)) = −1. 定理 4 (a) によって、いくつかの k − 2 個の m の列が存在し、それらを R(cid:48) と呼び、ε(m|C R(cid:48)) = −1 である。 0.79
Let v be a row of m outside R(cid:48). v を r(cid:48) の外の m の行とする。 0.76
Call the rows of m apart from v, R(cid:48)(cid:48). m の行を v, r(cid:48)(cid:48) から切り離す。 0.79
Since R(cid:48)(cid:48) contains R(cid:48), by induction dim Rowspace H(m|C R(cid:48)(cid:48) ) = k − 1. R(cid:48)(cid:48) は R(cid:48) を含むので、誘導的 dim Rowspace H(m|C R(cid:48)(cid:48) ) = k − 1 である。 0.74
Therefore U := Rowspace H(m|R(cid:48)(cid:48)) ⊆ Rk is of dimension at least k − 1. したがって U := Rowspace H(m|R(cid:48)(cid:48)) \ Rk は少なくとも k − 1 の次元である。 0.84
We claim now that dim U = k. Suppose to the contrary that dim U = k − 1. dim U = k とは反対に dim U = k − 1 と仮定する。 0.63
If v(cid:12)(U ) ⊆ U then as proven earlier in Theorem 8, U respects i=1 U(i) with U(i) = P(i)U(i). もし v(cid:12)(U ) U が定理 8 より早く証明されたならば、U は U(i) = P(i) U(i) で i=1 U(i) を尊重する。 0.83
So there is some i0 for which U(i0) ⊂ V(i0); specifically, U(i) = V(i) for all i (cid:54)= i0, and dim U(i0) = dim V(i0) − 1. よって、ある i0 に対して、U(i0) = V(i0); すなわち、すべての i (cid:54)= i0 に対して U(i) = V(i) であり、 dim U(i0) = dim V(i0) − 1 である。 0.86
Since |B(v)(i0)| < k, we know by induction that the rows of H(m) span V(i0). B(v)(i0)| < k であるため、誘導によって H(m) の列が V(i0) にまたがっていることが分かる。 0.74
Thus in fact U = Rk. 実際、U = Rk である。 0.70
(Further detail for the last step: let w ∈ Rk. (最後のステップについては、w ∈ Rk とする。) 0.69
Since the rows of H(m) span V(i0), there is a w(cid:48) ∈ Rowspace H(m) s.t. H(m) の行が V(i0) をまたぐので、w(cid:48) ∈ Rowspace H(m) s.t が存在する。 0.84
P(i0)w(cid:48) = P(i0)w. Moreover since U(i) = V(i) for all i (cid:54)= i0, there is a w(cid:48)(cid:48) ∈ U s.t. P(i0)w(cid:48) = P(i0)w また、すべての i (cid:54) = i0 に対して U(i) = V(i) であるため、w(cid:48)(cid:48) ∈ U s.t が存在する。 0.81
w(cid:48)(cid:48) = (I − P(i0))(w − w(cid:48)). w(cid:48)(cid:48) = (I − P(i0))(w − w(cid:48)) 0.93
Then w(cid:48) + w(cid:48)(cid:48) ∈ Rowspace H(m), and w(cid:48) + w(cid:48)(cid:48) = w.) すると w(cid:48) + w(cid:48)(cid:48) ∈ Rowspace H(m) と w(cid:48) + w(cid:48)(cid:48) = w となる。 0.84
B(v). Since v is nonconstant, B(v) is a partition of [k] into (cid:96) ≥ 2 nonempty blocks B(v)(i), and U =(cid:76)(cid:96) B(v)。 v は非安定であるため、B(v) は [k] を (cid:96) の 2 個の非空ブロック B(v)(i) と U =(cid:76)(cid:96) に分割する。 0.80
5 Motivation Consider observable random variables X1, . 5 動機 観測可能なランダム変数 X1 を考える。 0.69
. . , Xn that are statistically independent conditional on H, a hidden random variable H supported on {1, . . . H 上で統計的に独立な条件を持つ Xn は、{1, でサポートされる隠れたランダム変数 H である。 0.81
. . , k}. . . k} である。 0.82
(See causal diagram.) X1 (因果図参照) X1 0.68
X2 H ··· Xi X2 H ··· xi 0.72
··· Xn The most fundamental case is that the Xi are binary. ··· Xn 最も基本的なケースは Xi がバイナリであることである。 0.70
Then we denote mj parameters are m along with a probability distribution (the mixture distribution) π = (π1, . 次に、mj パラメータを確率分布 (混合分布) π = (π1, ) と共に m とする。 0.85
. . , πk) on H. Finite mixture models were pioneered in the late 1800s in [13, 14]. . . H. Finite混合モデルのπkは1800年代後半に[13, 14]で開拓された。 0.84
The problem of learning such distributions has drawn a great deal of attention. このような分布を学習する問題は大きな注目を集めている。 0.77
For surveys see, e.g., [5, 17, 11, 12]. 調査は[5, 17, 11, 12]を参照してください。 0.77
For some algorithmic papers on discrete Xi, see [9, 4, 7, 2, 6, 1, 15, 10, 3, 8]. 離散 Xi に関するアルゴリズム的な論文については [9, 4, 7, 2, 6, 1, 15, 10, 3, 8] を参照。 0.87
The source identification problem is that of computing (m, π) from the joint statistics of the Xi. 情報源同定問題は、Xi の合同統計量から計算する(m, π)問題である。 0.68
Put another way, the problem is to invert the multilinear moment map 別の言い方をすれば、問題は多重線型モーメントマップを反転させることです 0.58
i = Pr(Xi = 1|H = j). i = Pr(Xi = 1|H = j)。 0.96
The model µ : (m, π) → R2[n] µ(m, π)S = Pr(XS = 1) where S ⊆ [n], XS = モデル μ : (m, π) → R2[n] μ(m, π)S = Pr(XS = 1) である。
訳抜け防止モード: モデル μ : (m, π ) → R2[n ] μ(m, π)S = Pr(XS = 1 ) ここで、S は [n ] , XS = である。
0.74
= mS · π(cid:62) = mS · π (cid:62) 0.93
(cid:89) i∈S (cid:89) i∈S 0.69
Xi The last line shows the significance of H(m) to mixture model identification, since mj xi 最後の行は混合モデル同定におけるH(m)の重要性を示す。 0.68
S = Pr(XS = 1|H = j). S = Pr(XS = 1|H = j)。 0.96
Connection to rank H(m). ランク h(m) への接続。 0.76
In general µ is not injective (even allowing for permutation among the values of H). 一般に μ は単射ではない(H の値間の置換も許す)。 0.66
For instance it is clearly not injective if m has two identical columns (unless π places no weight on those). 例えば、m が 2 つの同一の列を持つ場合、これは明らかに単射ではない(π がそれらに重みを付けない限り)。 0.59
More generally, and assuming all πj > 0, it cannot be injective unless H(m) has full column rank. より一般に、すべての πj > 0 を仮定すると、h(m) が全列ランクでない限り、単射ではない。 0.70
One sufficient condition for injectivity, due to [16], is that there be 2k − 1 “separated” observables Xi; Xi is separated if all mj i are distinct, or in our terminology, if no color recurs in mi. 16] によるインジェクティビティの十分条件の一つは、2k − 1 の「分離」可観測値 xi が存在することである; xi はすべての mj i が異なる場合、あるいは我々の用語において mi に色が再帰しない場合、分離される。
訳抜け防止モード: インジェクティビティに対する1つの十分な条件は [16 ] である。 2k − 1 “ split ” observables Xi ; Xi が分離された場合 全てのmj iは別物 または用語では miで色が逆転しないなら
0.83
(Further [8], one can lower bound the distance between µ(m, π) and any µ(m(cid:48), π(cid:48)) in terms of mini,j |mj i | and the distance between (m, π) and (m(cid:48), π(cid:48)).) ([8]の場合、μ(m, π) と任意の μ(m(cid:48)), π(cid:48)) の間の距離をmini,j |mj i | と (m, π) と (m(cid:48), π(cid:48)) の間の距離で下限することができる)。 0.90
A weaker sufficient condition for injectivity of µ, due to [8], is that for every i ∈ [n] there exist two disjoint sets A, B ⊆ [n] − {i} such that H(m|A) and H(m|B) have full column rank. 8] による μ の射影に対するより弱い十分条件は、すべての i ∈ [n] に対して H(m|A) と H(m|B) が完全な列ランクを持つ2つの不整合集合 A, B ・ [n] − {i} が存在することである。 0.80
(It is not known whether two disjoint such A, B are strictly necessary, but the implied n ≤ 2k − 1 is in general best possible [15].) (二つの非連結 A, B が厳密に必要かどうかは不明であるが、インプリッド n ≤ 2k − 1 は一般に可能な [15] である)。 0.85
i − mj(cid:48) i − mj(cid:48) 0.92
5 v v } }   ( ( * * 5 v v } } は ( * * ) である。 0.82
英語(論文から抽出)日本語訳スコア
References [1] A. Anandkumar, D. Hsu, and S. M. Kakade. 参考文献 [1] A. Anandkumar, D. Hsu, S. M. Kakade。 0.78
A method of moments for mixture models and hidden 混合モデルと隠蔽モデルのためのモーメントの一手法 0.71
Markov models. In Proc. マルコフモデル。 Proc。 0.55
25th Ann. Conf. on Computational Learning Theory, pages 33.1–33.34, 2012. 25歳。 Conf on Computational Learning Theory, pages 33.1–33.34, 2012 0.60
[2] K. Chaudhuri and S. Rao. [2]K.ChaudhuriとS.Rao。 0.74
Learning mixtures of product distributions using correlations and independence. 相関と独立性を用いた製品分布の学習混合 0.88
In Proc. 21st Ann. Proc。 第21回。 0.53
Conf. on Computational Learning Theory, pages 9–20, 2008. Conf on Computational Learning Theory, ページ 9–20, 2008。 0.71
[3] S. Chen and A. Moitra. [3]S. ChenとA. Moitra。 0.86
Beyond the low-degree algorithm: mixtures of subcubes and their applications. 低次アルゴリズムを超えて:サブキューブの混合とその応用。 0.72
In Proc. 51st Ann. Proc。 第51話。 0.48
ACM Symp. on Theory of Computing, pages 869–880, 2019. ACMシンプ。 on Theory of Computing, page 869–880, 2019。 0.79
[4] M. Cryan, L. Goldberg, and P. Goldberg. 4] M. Cryan、L. Goldberg、P. Goldberg。 0.83
Evolutionary trees can be learned in polynomial time in the 進化的な木は多項式時間で学べます。 0.71
two state general Markov model. 2つの状態一般マルコフモデル。 0.67
SIAM J. Comput., 31(2):375–397, 2001. SIAM J。 計算、31(2):375-397, 2001。 0.72
Prev. FOCS ’98. 前。 FOCS ’98。 0.66
[5] B. S. Everitt and D. J. 5] B.S. EverittとD.J。 0.84
Hand. Mixtures of discrete distributions, pages 89–105. 手。 離散分布の混合、89-105ページ。 0.77
Springer Netherlands, Dordrecht, 1981. オランダの春。 1981年、ヨルダン。 0.54
[6] J. Feldman, R. O’Donnell, and R. A. Servedio. 6] J. Feldman、R. O’Donnell、R. A. Servedio。 0.83
Learning mixtures of product distributions over discrete 離散上の製品分布の混合学習 0.89
domains. SIAM J. ドメイン。 SIAM J。 0.74
Comput., 37(5):1536–1564, 2008. 37(5):1536-1564, 2008年。 0.76
[7] Y. Freund and Y. Mansour. 7] Y. FreundとY. Mansour。 0.85
Estimating a mixture of two product distributions. 2つの製品分布の混合物を推定する。 0.73
In Proc. 12th Ann. Proc。 第12回。 0.56
Conf. on Computational Learning Theory, pages 183–192, July 1999. Conf on Computational Learning Theory, page 183–192, July 1999 0.68
[8] S. L. Gordon, B. Mazaheri, Y. Rabani, and L. J. Schulman. 8] S. L. Gordon、B. Mazaheri、Y. Rabani、L. J. Schulman。 0.87
Source identification for mixtures of product 製品の混合物のソース識別 0.91
distributions. arXiv:20x, 2020. 分布。 arXiv:20x, 2020。 0.72
[9] M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie. 9] M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, L. Sellie. 0.98
On the learnability of discrete 離散性の学習性について 0.53
distributions. In Proc. 26th Ann. 分布。 Proc。 第26代。 0.61
ACM Symp. on Theory of Computing, pages 273–282, 1994. ACMシンプ。 on Theory of Computing, ページ273-282, 1994。 0.79
[10] J. Li, Y. Rabani, L. J. Schulman, and C. Swamy. 10] J. Li、Y. Rabani、L. J. Schulman、C. Swamy。 0.87
Learning arbitrary statistical mixtures of discrete 離散の任意の統計混合を学習する 0.75
distributions. In Proc. 47th Ann. 分布。 Proc。 第47代。 0.62
ACM Symp. on Theory of Computing, pages 743–752, 2015. ACMシンプ。 on Theory of Computing, page 743–752, 2015 0.77
[11] B. G. Lindsay. 11] B.G. Lindsay。 0.86
Mixture models: theory, geometry and applications. 混合モデル:理論、幾何学および適用。 0.81
In NSF-CBMS regional conference NSF-CBMS地域会議 0.87
series in probability and statistics, pages i–163. 確率と統計のシリーズ、i-163のページ。 0.77
JSTOR, 1995. 1995年、JSTOR。 0.79
[12] G. J. McLachlan, S. X. Lee, and S. I. Rathnayake. 12] G. J. McLachlan、S. X. Lee、S. I. Rathnayake。 0.84
Finite mixture models. Annual Review of Statistics 有限混合モデル。 統計学の年次研究 0.70
and Its Application, 6(1):355–378, 2019. そしてその応用は6(1):355–378, 2019。 0.81
[13] S. Newcomb. 13] S.ニューコーム。 0.73
A generalized theory of the combination of observations so as to obtain the best result. 最良の結果を得るために観測の組み合わせに関する一般化された理論。 0.87
American Journal of Mathematics, 8(4):343–366, 1886. The American Journal of Mathematics, 8(4):343–366, 1886 0.93
[14] K. Pearson. K・ピアソン (K. Pearson)。 0.61
Contributions to the mathematical theory of evolution III. 進化の数学的理論への貢献III。 0.76
Philosophical Transactions of the Royal Society of London (A. の哲学的取引。 ロンドン王立協会(royal society of london)所属。 0.69
), 185:71–110, 1894. ), 185:71–110, 1894. 0.82
[15] Y. Rabani, L. J. Schulman, and C. Swamy. 15] Y. Rabani、L.J. Schulman、C. Swamy。 0.85
Learning mixtures of arbitrary distributions over large discrete 大離散上の任意の分布の学習混合 0.85
domains. In Proc. ドメイン。 Proc。 0.60
5th Conf. on Innovations in Theoretical Computer Science, pages 207–224, 2014. 第5回。 on Innovations in Theoretical Computer Science, Page 207–224, 2014 0.73
[16] B. Tahmasebi, S. A. Motahari, and M. A. Maddah-Ali. 16] B. Tahmasebi、S. A. Motahari、M. A. Maddah-Ali。 0.80
On the identifiability of finite mixtures of IEEE International Symposium on Information Theory (ISIT) 2018 and ieee international symposium on information theory (isit) 2018, and the identififiability of finite mixtures of ieee international symposium on information theory (isit) 0.64
finite product measures. arXiv:1807.05444v1, 2018. 有限な製品測定。 arXiv:1807.05444v1, 2018 0.65
[17] D. M. Titterington, A. F. M. Smith, and U. E. Makov. 17] D. M. Titterington、A. F. M. Smith、U. E. Makov。 0.84
Statistical Analysis of Finite Mixture Distributions. 有限混合分布の統計的解析 0.74
John Wiley and Sons, Inc., 1985. John Wiley and Sons, Inc., 1985年。 0.90
6 6 0.85
             ページの最初に戻る

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