論文の概要、ライセンス

# (参考訳) 非凸問題におけるトラップ回避 [全文訳有]

Avoiding Traps in Nonconvex Problems ( http://arxiv.org/abs/2106.05206v1 )

ライセンス: CC BY 4.0
Sean Deyo and Veit Elser(参考訳) 反復射影法は、制約集合が凸でないときに非解に閉じ込められることがある。 この動作を避けるために2種類のパラメータが利用可能であり、本研究は両方の例を示す。 ハイパーパラメータと呼ばれる最初のパラメータには、イテレーションルール自体の定義に現れるパラメータが含まれています。 第2の種は、制約集合の定義におけるメトリックパラメータを含み、解決すべき問題が2つ以上の変数を持つ場合に生じる特徴である。 例を通して、両パラメータを適切に調整し、観察された振る舞いをヒューリスティックに解釈することの重要性を示す。

Iterative projection methods may become trapped at non-solutions when the constraint sets are nonconvex. Two kinds of parameters are available to help avoid this behavior and this study gives examples of both. The first kind of parameter, called a hyperparameter, includes any kind of parameter that appears in the definition of the iteration rule itself. The second kind comprises metric parameters in the definition of the constraint sets, a feature that arises when the problem to be solved has two or more kinds of variables. Through examples we show the importance of properly tuning both kinds of parameters and offer heuristic interpretations of the observed behavior.
公開日: Wed, 9 Jun 2021 16:47:53 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
1 2 0 2 n u J 1 2 0 2 n u J 0.85
9 ] . C O h t a m 9 ] . C O h t a m 0.85
[ 1 v 6 0 2 5 0 [ 1 v 6 0 2 5 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
AVOIDING TRAPS IN NONCONVEX PROBLEMS 非凸問題におけるトラップの回避 0.45
SEAN DEYO1,∗, VEIT ELSER1 SEAN DEYO1,∗,VEIT ELSER1 0.84
1Department of Physics, Cornell University, Ithaca, NY, USA 1 ニューヨーク州イタカのコーネル大学物理学部 0.59
Abstract. Iterative projection methods may become trapped at non-solutions when the constraint sets are nonconvex. 抽象。 反復射影法は、制約集合が凸でないときに非解に閉じ込められることがある。 0.59
Two kinds of parameters are available to help avoid this behavior and this study gives examples of both. この動作を避けるために2種類のパラメータが利用可能であり、本研究は両方の例を示す。 0.78
The first kind of parameter, called a hyperparameter, includes any kind of parameter that appears in the definition of the iteration rule itself. ハイパーパラメータと呼ばれる最初のパラメータには、イテレーションルール自体の定義に現れるパラメータが含まれています。
訳抜け防止モード: ハイパーパラメータと呼ばれる最初の種類のパラメータには、あらゆる種類のパラメータが含まれています。 イテレーションルール自体の定義に現れます。
0.82
The second kind comprises metric parameters in the definition of the constraint sets, a feature that arises when the problem to be solved has two or more kinds of variables. 第2の種は、制約集合の定義におけるメトリックパラメータを含み、解決すべき問題が2つ以上の変数を持つ場合に生じる特徴である。 0.88
Through examples we show the importance of properly tuning both kinds of parameters and offer heuristic interpretations of the observed behavior. 例を通して、両パラメータを適切に調整し、観察された振る舞いをヒューリスティックに解釈することの重要性を示す。 0.67
Keywords. Projection methods; Fixed-point algorithms; Nonconvex problems; Logical satisfiability; Dominating sets; Machine learning. キーワード。 投影法、固定点アルゴリズム、非凸問題、論理満足性、支配集合、機械学習。 0.74
1. INTRODUCTION Iterative algorithms whose elementary operations are projections to constraint sets perform well on many nonconvex problems for which one does not have the convergence guarantees one has in convex problems. 1. 導入 基本操作が制約集合への射影である反復アルゴリズムは、凸問題において収束保証を持たない多くの非凸問題に対してうまく機能する。 0.71
For some combinatorially hard problems these algorithms routinely outperform state-of-the-art algorithms that find solutions by exhaustive search [1]. 組合せ的に難しい問題に対して、これらのアルゴリズムは、徹底的な探索 [1] で解を求める最先端のアルゴリズムを常に上回る。 0.58
This success, or the apparent ability of the projection-based search to very significantly reduce the size of the space being searched, is poorly understood. この成功や、投射に基づく検索が検索対象の空間の大きさを大幅に減らすという明らかな能力は、あまり理解されていない。 0.71
The standard criteria for evaluating iterative projection algorithms in the convex case do not apply in the nonconvex case. 凸の場合において反復射影アルゴリズムを評価するための標準基準は、凸でない場合には適用されない。 0.63
The amount of time the algorithm spends refining a solution, once its locally convex basin has been encountered, is negligible compared to the time needed to find the basin. アルゴリズムが解の精製に費やす時間は、その局所的な凸盆地に遭遇すると、盆地を見つけるのに必要な時間と比べて無視できる。 0.60
Efficiency in basin discovery completely overshadows the benefits of good convergence within the basin. 盆地発見の効率性は盆地内の良好な収束の利点を完全に覆している。 0.73
Iterative projection algorithms usually follow a fixed-point principle, where fixed-points imply a solution, but these algorithms may still get trapped on non-solutions in a dynamic sense [2]. 反復射影アルゴリズムは通常、固定点が解を示唆する固定点原理に従うが、これらのアルゴリズムは動的意味では非解に閉じ込められる。 0.71
When this happens, the iterations meander indefinitely within a small domain far from a true fixed point. これが起こると、反復は真の固定点から遠く離れた小さな領域内で無限に蛇行する。 0.56
Eliminating or mitigating this behavior by tuning the parameters of the algorithm is the focus of this paper. アルゴリズムのパラメータをチューニングしてこの振る舞いを除去または緩和することが本論文の焦点である。 0.76
Most iterative projection algorithms have parameters that apply to the general case, independent of the application’s constraint sets. ほとんどの反復プロジェクションアルゴリズムは、アプリケーションの制約セットとは独立して、一般的なケースに適用されるパラメータを持つ。 0.70
For such parameters we use the machine learning term “hyperparameter.” Relaxation parameters are examples of hyperparameters. このようなパラメータには、"ハイパーパラメータ"という機械学習用語を使用します。 0.70
Another type of parameter has only come to light more recently, in applications that require multiple kinds of variables [3]. 別のタイプのパラメータは、複数の種類の変数[3]を必要とするアプリケーションにおいて、最近になってしか光らない。 0.77
These applications have variable-scaling freedom that is not a geometrical isometry and therefore changes the algorithm through its effect on the projections. これらの応用は幾何学的等長法ではない可変スケール自由度を持ち、それゆえ射影への影響によってアルゴリズムを変化させる。 0.63
We refer to such parameters as “metric parameters.” このようなパラメータを「メトリックパラメータ」と呼ぶ。 0.82
∗Corresponding author. E-mail addresses: sjd257@cornell.edu (S. Deyo), ve10@cornell.edu (V. Elser). 共著者。 メールアドレス: sjd257@cornell.edu (S. Deyo), ve10@cornell.edu (V. Elser)。 0.67
Submitted June 10, 2021 2021年6月10日提出 0.71
1 1 0.85
英語(論文から抽出)日本語訳スコア
2 S. DEYO, V. ELSER 2 S. DEYO, V. ELSER 0.87
2. HYPERPARAMETERS AND METRIC PARAMETERS 2. ハイパーパラメータおよびメトロパラメータ 0.65
One of the best known hyperparameters is the relaxation that is often applied to the Douglas- 最もよく知られているハイパーパラメータの1つは、しばしばダグラスに適用される緩和である。 0.55
Rachford iteration [4] Rachford 反復[4] 0.79
x 7→ (1 − β/2) x + (β/2) RB(RA(x)). x 7→ (1 − β/2) x + (β/2) RB(RA(x))。 0.92
(2.1) Here RA and RB are the reflectors for the constraint sets A and B. (2.1) ここで、RAとRBは制約集合A,Bの反射体である。 0.75
The hyperparameter β is the same parameter that independently was deemed important when this iteration was proposed — by an engineer unaware of Douglas-Rachford — for the phase retrieval application [5]. ハイパーパラメータ β は、位相検索アプリケーション [5] に対して、ダグラス・ラフフォードの知らないエンジニアによって提案された時、独立して重要なパラメータである。 0.71
To make the point that the scope of hyperparameters is broad, we give an example in section 3 of a very different generalization of Douglas-Rachford, in which tuning a hyperparameter is critical for success. ハイパーパラメータの範囲が広いことを指摘するために、ダグラス・ラッチフォードの全く異なる一般化の第3節において、ハイパーパラメーターのチューニングが成功に不可欠である例を示す。 0.69
In imaging applications [6], or even sudoku [7], where there is just one kind of pixel or cell, the question of metric parameters never came up. 画像アプリケーション [6] や1種類のピクセルやセルしか存在しないsudoku [7] では、メトリックパラメータの問題は決して生じなかった。 0.60
An application where introducing metric parameters makes sense is non-negative matrix factorization (NMF) [8]. 計量パラメータの導入が理にかなう応用は非負行列分解 (NMF) [8] である。 0.79
In NMF one seeks a low-rank factorization of a rectangular non-negative matrix Z = XY , where the factors are themselves non-negative. NMF では、正方形の非負行列 Z = XY の低ランク分解を求め、その因子はそれ自体が非負である。 0.62
The rows of Z may be interpreted as data vectors that can be expressed as non-negative mixtures, given by X , of a set of non-negative features, the rows of Y . z の行は y の行である非負の特徴の集合の x によって与えられる非負の混合として表現できるデータベクトルとして解釈できる。 0.71
NMF is non-unique with respect to rescaling (X → X D, Y → D−1Y , arbitrary diagonal and positive D). NMF は再スケーリング(X → X D, Y → D−1Y , 任意の対角線と正の D)に関して非特異である。 0.74
To remove this ambiguity and also to make the problem compact, we can choose to impose a norm on the columns of X or the rows of Y . この曖昧さを排除し、問題をコンパクトにするために、X の列や Y の行にノルムを課すことを選ぶことができる。 0.66
If we decide to normalize the features (Y ), what setting of the norm do we choose and why is that a choice of metric? 特徴(y)を正規化すると決めた場合、標準はどのような設定で選択し、なぜそれがメトリクスの選択なのか? 0.76
To motivate the term “metric,” consider the standard distance that would be used in defining メトリクス”という言葉をモチベーションにするために、定義に使用される標準距離を考える 0.75
the projections for the NMF application: NMF アプリケーションのプロジェクション: 0.54
d(cid:0)(X ,Y ), (X ′,Y ′)(cid:1) =qkX − X ′k2 d(cid:0)(X ,Y ), (X ′,Y ′)(cid:1) =qkX − X ′k2 0.98
2 + kY −Y ′k2 2. 2 + kY −Y ′k2。 0.92
(2.2) Now, if we chose to impose normalization on each row vector y of Y , say kyk2 = η, we could alternatively work with the rescaled variables ˜Y = Y /η, normalization constraint k ˜yk2 = 1, and the distance (2.2) さて、もし y の各行ベクトル y に正規化を課す、例えば kyk2 = η を課すならば、再スケールされた変数 :y = y /η 、正規化制約 k syk2 = 1 と距離を代用することができる。 0.76
d(cid:0)(X , ˜Y ), (X ′, ˜Y ′)(cid:1) =qkX − X ′k2 d(cid:0)(x , sy ), (x ′, sy ′)(cid:1) = qkx − x ′k2 0.88
2 + η2k ˜Y − ˜Y ′k2 2. 2 + η2k >Y − >Y ′k2 2。 0.63
(2.3) This rewriting by a parameterized distance provides an interpretation of the norm parameter η. (2.3) このパラメータ化距離による書き換えはノルムパラメータηの解釈を提供する。 0.81
Consider the projection to the bilinear constraint, X ˜Y = Z/η. 双線型制約への射影を考えれば、X は Z/η である。 0.59
From the distance (2.3) we see that for small η the ˜Y variables (features) are more compliant than X (mixtures), and we should expect that product-constraint inconsistencies are resolved mostly by changing the features. 距離 (2.3) からすると、小さなη に対して、オイY変数 (features) は X (mixtures) よりも忠実であることが分かる。
訳抜け防止モード: 距離 (2.3 ) から見ると、 小さめのηの場合、 yY 変数 (特徴 ) は X (mixs ) よりも忠実である。 プロダクト - 制約の不整合は、主に機能の変更によって解決される、と期待するべきです。
0.63
The opposite, or more reliance on changing the mixtures, is expected for large η. 逆、あるいは混合物の変更への依存は大きなηに対して期待される。 0.73
NMF is one of the earliest techniques of machine learning, and we anticipate that variabletype metric sensitivity will grow in relevance as projection methods find their way into this domain1. NMFは機械学習の最も初期の手法の1つであり、射影法がこの分野に進出するにつれて、可変型計量感度は関連性が高くなると予想する。 0.69
In particular, splitting methods lend themselves naturally to optimization on networks, where variables appear on both nodes and edges of the network and are clearly dissimilar. 特に、分割メソッドは、ネットワークのノードとエッジの両方に変数が現れ、明らかに似ていないネットワークの最適化に自然に役立ちます。 0.75
1. The term “parameter” is potentially confusing in the machine learning context. 1. パラメータ”という言葉は、機械学習の文脈で混乱している可能性がある。 0.74
For example, the weight parameters of a neural network that are learned from data are variables from the perspective of the optimization algorithm. 例えば、データから学習されるニューラルネットワークの重みパラメータは、最適化アルゴリズムの観点から変数である。 0.66
The latter may use metric parameters to more efficiently optimize the weight variables. 後者は計量パラメータを使って重み変数をより効率的に最適化することができる。 0.69
英語(論文から抽出)日本語訳スコア
AVOIDING TRAPS 3 3. 回避トラップ 3 3. 0.72
HYPERPARAMETERS ハイパーパラメーター 0.22
A tuneable double-reflector algorithm. チューニング可能なダブルリフレクタアルゴリズム。 0.64
In this section we consider a generalization of the Douglas-Rachford iteration that is very different from the standard relaxation (2.1) : この節では、標準緩和 (2.1) とは全く異なるダグラス・ラフフォード反復の一般化を考える。 0.74
x 7→ DRn[δ](x) = x 7→DRn[δ](x) = 0.81
1 1 + n n ∑ r=0 1 1 + n n ‐r=0 0.76
(RA[δ] ◦ RB[δ])r(x) . (RA[δ] > RB[δ])r(x)。 0.67
(3.1) The number of double reflections, n, is one of the algorithm’s hyperparameters. (3.1) 二重反射数 n はアルゴリズムのハイパーパラメータの1つである。 0.73
However, we will see that this algorithm only succeeds when the reflectors are themselves parameterized, しかし、このアルゴリズムが成功するのは、リフレクタ自体がパラメータ化されているときのみである。 0.57
Ri[δ](x) = (2 − δ) Pi(x) − (1 − δ) x , Ri[δ](x) = (2 − δ) Pi(x) − (1 − δ) x , 0.82
(3.2) and are made contractive with a positive setting of the hyperparameter δ. (3.2) そして、ハイパーパラメータδの正の設定と収縮する。 0.67
The original DouglasRachford iteration is recovered for n = 1 and δ = 0 and will be referred to as DR1[0]. 最初のdouglasrachford反復は n = 1 と δ = 0 に対して回収され、dr1[0] と呼ばれる。 0.76
The idea behind (3.1) is that the double reflector acts as the identity when x is near a feasible point, and therefore the average of any number of double reflections fixes x. 3.1) の背後にある考え方は、ダブルリフレクターが x が実現可能な点に近いときに同一性として作用し、したがって任意の数のダブルリフレクターの平均が x を固定するということである。 0.60
On the other hand, multiple (n > 1) applications of the double reflector might be better at ejecting x from a trap when it is not near a feasible point. 一方、 (n > 1) 二重反射体の複数の応用は、実現可能な点に近づかないときにトラップから x を射出する方がよいかもしれない。 0.78
Through elementary analysis and numerical experiments we will argue that there is an optimal δ∗ such that when δ > δ∗, and the reflections are too contractive, the iterations become trapped at non-solutions, while for δ < δ∗ the iterate diffuses too freely to notice even the true solutions. 基本解析と数値実験を通じて、δ > δ∗ と反射が収縮しすぎるとき、反復は非解に閉じ込められ、δ < δ∗ に対して、反復拡散は真の解に気づかないほど自由すぎるという最適 δ∗ が存在すると論じる。 0.78
The algorithm works best when δ is tuned to the dynamical transition point δ∗. このアルゴリズムは δ が動的遷移点 δ∗ にチューニングされるときに最もうまく働く。 0.81
Hard feasibility problems, including the one we feature below, can often be formulated where one constraint set, say A, is discrete and the other, B, is a hyperplane. 以下に示すようなハードファシビリティ問題を含むハードファシビリティ問題は、1つの制約集合、例えば A が離散であり、もう1つの制約集合 B が超平面であるときにしばしば定式化される。 0.65
Traps arise when a point a ∈ A is very close to B, that is, when the distance ∆ = ka − bk, to the proximal point b = PB(a) on the hyperplane, is very small. 軌道は、点 a ∈ A が B に非常に近いとき、すなわち、超平面上の近点 b = PB(a) への距離が非常に小さいときに生じる。
訳抜け防止モード: トラップは、点 a ∈ A が B に非常に近いときに生じる。 すなわち、距離 t = k − bk であるときである。 超平面上の近点 b = PB(a) へ。 非常に小さいです
0.78
The local trapping/escaping behavior is analyzed by the dynamics just along the line defined by the proximal points a ∈ A, b ∈ B. 局所トラップ/エスケープ挙動は、近位点 a ∈ a, b ∈ b によって定義される直線に沿ったダイナミクスによって解析される。 0.74
With x as the (1D) coordinate along this line, and x を (1D) 座標としてこの線に沿って、そして 0.83
we find where 見つけました どこに 0.61
PA(x) = 0, PB(x) = −∆ , PA(x) = 0, PB(x) = − , 0.84
DRn[δ](x) = γx + c , DRn[δ](x) = γx + c , 0.85
γ = 1 − n(1 − q) − q(1 − qn) γ = 1 − n(1 − q) − q(1 − qn) である。 0.90
(1 + n)(1 − q) (1 + n)(1 − q) 0.85
q = (1 − δ)2 q = (1 − δ)2 0.85
c = (1 − γ)(cid:18) 1 − δ c = (1 − γ)(cid:18) 1 − δ 0.97
δ (cid:19) ∆ . δ (cid:19)。 0.79
(3.3) (3.4) (3.3) (3.4) 0.78
For comparison, represents a step-wise escape, where O(1/∆) iterations are needed before x has changed by O(1) in order that PA(x) is no longer the original point a of the trap. 比較のために ステップワイズエスケープを表しており、ここでは O(1/) の繰り返しが O(1) によって変化し、PA(x) がもはやトラップの原点 a ではないために必要となる。 0.80
DR1[0](x) = x + ∆ DR1[0](x) = x + ... 0.91
(3.5) (3.5) 0.78
英語(論文から抽出)日本語訳スコア
4 S. DEYO, V. ELSER 4 S. DEYO, V. ELSER 0.87
Since 0 < γ < 1 for 0 < δ < 1, iteration (3.4) looks problematic because there is always a 0 < γ < 1 for 0 < δ < 1 であるため、常に a が存在するので問題視される(3.4)。 0.77
(non-solution) fixed point: x∗ = (非溶解)定点 x∗ = 0.67
c 1 − γ =(cid:18) 1 − δ c 1 − γ =(cid:18) 1 − δ 0.88
δ (cid:19) ∆ . δ (cid:19)。 0.79
(3.6) However, (3.6) should be seen as instructions on the proper use of the algorithm. (3.6) しかし、(3.6)はアルゴリズムの適切な使用の指示と見なすべきである。 0.82
In any application there will be a smallest ∆ that poses the greatest trapping risk. どんなアプリケーションでも、最大のトラッピングリスクをもたらす最小の s が存在するだろう。 0.68
But by setting δ = δ∗ = O(∆), the fixed point x∗ of the 1D dynamics is sufficiently far from the trap that PA(x∗) will be different from the original trapping point a. しかし、δ = δ∗ = O( ) を設定することで、1次元力学の固定点 x∗ は、PA(x∗) が元のトラップ点 a と異なるようなトラップから十分に離れている。 0.70
Since c ∼ n ∆ for δ → 0, a single iteration of DRn is roughly the same as n iterations of DR1, although both schemes require n double-reflector computations. δ → 0 に対して c は n であるから、DRn の 1 つの反復は DR1 の n 個の反復とほぼ同じであるが、どちらのスキームも n 個の二重反射子計算を必要とする。 0.65
Experiments with logical satisfiability. 論理的に満足できる実験。 0.73
To illustrate the effect of the hyperparameter δ in a setting with potentially many traps, we turn to the logical satisfiability problem (SAT). 潜在的に多くのトラップを持つ環境でのハイパーパラメータδの効果を説明するために、論理的充足可能性問題(SAT)に目を向ける。 0.67
In SAT we have a set C of clauses and a set V of variables. SAT には節の集合 C と変数の集合 V がある。 0.65
Thinking of these as vertices of a bipartite graph G, the search variables E in our constraint formulation correspond to edges c → v, where c ∈ C and v ∈ V . これらを二成分グラフ g の頂点として考えると、我々の制約定式化における探索変数 e は、c ∈ c と v ∈ v の辺 c → v に対応する。 0.72
In the SAT interpretation, the variable-vertices v incident on a particular c in G correspond to the Boolean variables that participate in one clause of a logical formula in conjunctive normal form. sat解釈において、g の特定の c 上の変数変換 v は、結合正規形式における論理式の一節に属するブール変数に対応する。 0.68
The clause itself is a disjunction 節そのものは、譲歩です 0.49
where the x are Boolean variables, n◦ specifies whether to apply negation, and yc is the Boolean value of clause c. The object in SAT is to find an assignment to the x such that the conjunction x がブール変数である場合、n は否定を適用すべきかどうかを指定し、yc は節 c のブール値である。
訳抜け防止モード: x がブール変数である場合、n\ は否定を適用するかどうかを指定する。 ycは節cのブール値です satのオブジェクトは x への代入を見つけるには
0.65
yc = _v∈V : c→v ∈ E yc = _vservletv : c→v ∈ e 0.76
nc→v ◦ xc→v nc→v > xc→v 0.57
(3.7) yc ^c∈C (3.7) yc ^c・C 0.65
(3.8) is true. The set of Boolean variables xc→v incident on the same v (but appearing in different clauses c) should all be equal. (3.8) 本当だ 同じ v 上のブール変数 xc→v の入射(ただし異なる節 c に現れる)の集合はすべて等しくなければならない。 0.67
However, in the two-constraint formulation [9] to which we turn next, these are treated as independent in one of the constraints. しかし、次に曲がる2-constraint式 [9] では、制約の1つでこれらは独立として扱われる。 0.75
The two constraint sets live in a space of dimension |E|. 2つの制約集合は次元 |E| の空間に存在する。 0.73
Set A is discrete and imposes the truth of each clause (otherwise the conjunction (3.8) is false). 集合 A は離散であり、各節の真理を課す(そうでなければ接続 (3.8) は偽である)。 0.68
We encode TRUE and FALSE for the Boolean variables as respectively x = +1 and x = −1 and use multiplication by n = −1 for negation: ブール変数に対して TRUE と FALSE をそれぞれ x = +1 と x = −1 とエンコードし、否定のために n = −1 の乗法を用いる。 0.75
A : ∀ c → v ∈ E : xc→v ∈ {−1, 1} a: c → v ∈ E : xc→v ∈ {−1, 1} 0.79
∀ c ∈ C : c ∈ C である。 0.63
+1 ∈ [v∈V : c→v ∈ E +1 ∈ [v~V : c→v ∈ E 0.75
nc→v xc→v Because the A constraint imposes the discreteness of the Boolean variables we are free to use the following relaxed, continuous constraint for B: nc→vxc→v A 制約はブール変数の離散性を強制するので、B に対して以下の緩和された連続的な制約を自由に使用できる。 0.65
B : ∀ v ∈ V : ∃ ¯xv ∈ R : b: また、v ∈ r は、v ∈ r である。 0.68
∀ (c ∈ C : c → v ∈ E) : xc→v = ¯xv . (c ∈ C : c → v ∈ E) : xc→v = .xv )。 0.87
(3.9) We consider a hard instance of 3-SAT, where each clause involves exactly three variables and there are altogether |V | = 500 Boolean variables in the logical formula. (3.9) それぞれの節が正確に3つの変数を含み、論理式に完全に |V | = 500 ブール変数が存在する3-SAT の難解な例を考える。 0.79
The number of clauses |C| = 2100 was tuned so that a typical random instance has roughly even odds of being c| = 2100 の節の数は、典型的なランダムなインスタンスがおおよそ奇数であるように調整された 0.78
英語(論文から抽出)日本語訳スコア
AVOIDING TRAPS 5 satisfiable [10] (and this is true of our instance). 回避トラップ 5 満足できる[10] (これは私たちの例に当てはまります)。 0.71
All our results will be for iteration DR3, for which the number of double reflections (n = 3) is large enough that a transition in behavior with δ is easy to discern. すべての結果は反復 DR3 であり、二重反射数(n = 3) はδ による振舞いの遷移が容易に識別できるほど大きい。 0.68
To visualize the results, we store the time series of the |E| search variables in a matrix, where each row specifies a point in R|E|. 結果を視覚化するために、|E| 探索変数の時系列を行列に格納し、各行が R|E| の点を特定する。 0.77
We then find the principal component axes for this matrix and project each row onto the first two principal components to obtain a 2-dimensional plot of the search as a function of time. 次に、この行列の主成分軸を見つけ、各行を最初の2つの主成分に射影し、時間の関数として探索の2次元プロットを得る。 0.78
Since we are projecting points with root-mean-square distance ルート平均平方距離を持つ射影点であるため 0.62
O(p|E|), we also divide the principal components by p|E| to normalize the length scale in O(p|E|) も主成分を p|E| で割って長さスケールを正規化する。 0.68
the 2D plots. Alongside each PCA time series we provide the time series of the constraint error ∆ = |PA(x) − PB(x)| for the points x generated by the DR3 iteration. 2Dプロット。 各PCA 時系列と共に、DR3 反復によって生成される点 x に対して、制約誤差 > = |PA(x) − PB(x)| の時系列を提供する。 0.72
The results are shown in Figure 1. 結果は図1に示されています。 0.78
When δ = 0.001 (top plots of Fig 1), the search jumps around aimlessly with large ∆ and never finds a solution. δ = 0.001 (図 1 のトッププロット) のとき、探索は意図せず大きな s で飛び回り、解を見つけることはない。 0.70
We interpret this as small δ not being contractive enough: When δ is small, each reflection Ri(x) is almost the same as the pure reflection 2Pi(x) − x and the algorithm never allows itself to fall into a basin of lower ∆. δ が小さければ、それぞれの反射 Ri(x) は純粋な反射 2Pi(x) − x とほとんど同じであり、アルゴリズムはそれ自身を下方 δ の接点に落ちることを許さない。
訳抜け防止モード: これを十分収縮しない小さなδと解釈する : いつ δ は小さい。 それぞれの反射 Ri(x ) は純粋な反射 2Pi(x ) − x とほとんど同じである アルゴリズムは 決して 下位の階層に落ちないようにします
0.78
When δ = 0.02 (bottom plots of Fig 1), the algorithm quickly gets trapped on a non-solution and remains there for the rest of the search. δ = 0.02 (fig 1 のボトムプロット) のとき、アルゴリズムはすぐに非解に閉じ込められ、残りの探索のためにそこに残る。 0.74
Even though ∆ is small, the algorithm never finds a solution. このアルゴリズムは小さいが、解を見つけることは決してない。 0.52
We interpret this as large δ being too contractive: the algorithm gets stuck in the first basin it finds, even though that basin likely does not contain a solution. 私たちはこれを大きすぎる δ と解釈する: アルゴリズムは、解を含まない可能性が高いにもかかわらず、最初の盆地で立ち往生する。 0.68
The intermediate choice δ = 0.005 (middle plots of Fig 1) seems to be just right. 中間選択 δ = 0.005 (Fig 1) の中間プロット) はちょうど正しいようである。 0.84
The algorithm now appears to start exploring a basin once or twice but only stays for a few hundred iterations before wandering to another basin. このアルゴリズムは現在、盆地を1回か2回探索しているように見えるが、数百回の反復しか残っていない。 0.66
After about 3 × 103 iterations it finds a basin that has a solution and converges toward it. 約3×103の反復の後、解を持ち、それに向かって収束する盆地を見つける。 0.69
4. METRIC PARAMETERS 4. メトリックパラメータ 0.69
Metric parameters, unlike hyperparameters, are special for each intended application and should always be considered when there is more than one type of variable. ハイパーパラメータとは異なり、メトリックパラメータはそれぞれのアプリケーションに特有であり、複数の変数が存在する場合に常に考慮すべきである。 0.83
Below we give two examples, both involving applications where the variables take discrete values and live on a network. 下記の例では、変数が離散値を取るアプリケーションとネットワーク上のアプリケーションという2つの例を示します。 0.64
As with hyperparameters, the settings of the metric parameters makes all the difference between an algorithm that never finds solutions and one that does so consistently. ハイパーパラメータと同様に、メトリックパラメータの設定は、解を見つけることのできないアルゴリズムと、それと一貫して行うアルゴリズムとのすべての違いをもたらす。 0.72
Often a metric parameter will not have an obvious interpretation, or will have non-obvious interactions with the other metric parameters. しばしば、メトリックパラメータは明確な解釈を持たず、または他のメトリックパラメータと非オブザーブな相互作用を持つ。 0.75
Tuning these metric parameters can be done by hand and is informed by appropriate diagnostics that go beyond the standard “success rate” statistic. これらのパラメータのチューニングは手作業で行うことができ、標準的な「成功率」統計を超える適切な診断によって通知される。
訳抜け防止モード: これらのパラメータのチューニング 手動で行うことができ 適切な診断によって 標準的な“成功率”統計を超えます。
0.81
However, an automated procedure to expedite this process is desirable, especially when the number of metric parameters is large. しかし、特にメトリックパラメータの数が大きい場合には、このプロセスを迅速化する自動手順が望ましい。 0.79
We use a scheme where the current status of the search informs the rule for the parameter updates, and apply these updates adiabatically so as not to upend the fixed-point properties of the algorithm being used. 提案手法では,現在の検索状況がパラメータ更新のルールを通知し,使用中のアルゴリズムの不動点特性をアップアップしないよう,これらの更新を適用している。 0.85
Our metric parameter update rule is based on the following heuristic. 我々のパラメータ更新ルールは以下のヒューリスティックに基づいている。 0.69
We want to prevent the algorithm from getting stuck on a partial solution, wherein some variables hardly change between the A and B projections while others are changing very much. いくつかの変数はAとBの射影の間でほとんど変化しないが、他の変数は非常に変化している。
訳抜け防止モード: アルゴリズムが部分的な解決策で行き詰まるのを防ぎたいのです。 いくつかの変数はAとBのプロジェクションの間でほとんど変化しないが、他の変数は非常に変化している。
0.62
We avoid this by giving a smaller metric parameter to the variables that are hardly changing, thereby lowering the penalty for changing them when the next projection comes, and vice versa for variables that change too much. 我々は、変化がほとんどない変数に対してより小さなメトリックパラメータを与えることにより、次のプロジェクションが来たときに変更のペナルティを低くし、その逆の変数が過度に変化するのを避ける。 0.82
To be precise, suppose we partition the variables into k types, with metric parameters η1, η2, ... ηk. 正確には、変数をパラメータ η1, η2, ... ηk で k 型に分割すると仮定する。 0.76
Let li denote the number of variables of type i, so that the complete variable vector can li は i 型の変数の数を表し、完全な変数ベクトルが出来るようにする。 0.79
英語(論文から抽出)日本語訳スコア
6 S. DEYO, V. ELSER 6 S. DEYO, V. ELSER 0.87
r o r r e r o r e である。 0.77
r o r r e r o r e である。 0.77
r o r r e r o r e である。 0.77
0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.42
0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.42
0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 0.42
0 2 × 103 0 0 2 × 103 0 0.85
2 × 103 0 2 × 103 2 × 103 0 2 × 103 0.85
δ = 0.001 δ = 0.001 δ = 0.001 δ = 0.001 0.78
4 × 103 6 × 103 4 × 103 6 × 103 0.85
iteration δ = 0.005 繰り返しδ = 0.005 0.77
4 × 103 6 × 103 4 × 103 6 × 103 0.85
iteration δ = 0.02 反復 δ = 0.02 0.77
8 × 103 8 × 103 8 × 103 8 × 103 0.85
2 # t n e n o p m o c l a p i c n i r p 2 # t n e n o p m o c l a p i c n i r p 0.85
0.3 0.2 0.1 0.3 0.2 0.1 0.59
0.0 −0.1 −0.2 0.0 −0.1 −0.2 0.51
0.6 0.4 0.2 0.6 0.4 0.2 0.59
0.0 −0.2 2 # 0.0 −0.2 2 # 0.64
t n e n o p m o c l a p i c n i r p t n e n o p m o c l a p i c n i r p 0.85
2 # t n e n o p m o c l a p i c n i r p 2 # t n e n o p m o c l a p i c n i r p 0.85
0.4 0.3 0.2 0.4 0.3 0.2 0.59
0.1 0.0 −0.1 0.1 0.0 −0.1 0.55
−0.3 −0.2 principal component #1 −0.3 −0.2 主成分#1 0.56
−0.1 0.0 δ = 0.005 −0.1 0.0 δ = 0.005 0.61
−0.8 −0.6 −0.4 −0.2 −0.8 −0.6 −0.4 −0.2 0.35
0.0 principal component #1 0.2 0.0主成分#1 0.2 0.69
δ = 0.02 4 × 103 δ = 0.02 4 × 103 0.82
6 × 103 iteration 6 × 103 イテレーション 0.66
8 × 103 −0.4 8 × 103 −0.4 0.66
−0.2 0.2 principal component #1 −0.2 0.2主成分#1 0.64
0.0 0.4 10000 0.0 0.4 10000 0.68
8000 6000 4000 8000 6000 4000 0.85
2000 3000 2500 2000 3000 2500 0.85
2000 1500 1000 2000 1500 1000 0.85
500 10000 8000 500 10000 8000 0.85
6000 4000 2000 6000 4000 2000 0.85
FIGURE 1. Plots of the constraint error kPA(x) − PB(x)k (left column) and the iterate x (right column) of the DR3 algorithm applied to an instance of 3-SAT. 図1に示す。 制約誤差 kPA(x) − PB(x)k (左列) とDR3 アルゴリズムの反復 x (右列) のプロットは 3-SAT のインスタンスに適用される。 0.58
The three rows correspond to the reflectors being insufficiently contractive (top), too contractive (bottom), and a setting of δ in which the search succeeds (middle). 3つの行は、リフレクタが不十分な収縮性(トップ)、過剰収縮性(ボット)、探索が成功するδ(中間)に対応する。 0.61
The plots on the right show the iterate x projected into a 2D space by PCA. 右のプロットは、PCAによって2次元空間に射影された反復 x を示している。 0.64
These data are plotted in increments of 10 iterations up to a maximum of 104 iterations, with the color bar indicating the iteration number. これらのデータは10回のイテレーションで最大104回のイテレーションまでプロットされ、カラーバーがイテレーション番号を示している。 0.72
be written as a concatenation x = (x1, x2, ..., xk), where x1 is a vector of length l1 and so on. 連結 x = (x1, x2, ..., xk) と書くと、x1 は長さ l1 のベクトルなどである。 0.75
The projections are made using the distance function 投影は距離関数を使って行われます 0.84
In each iteration, we compute the rms error 各イテレーションで rms エラーを計算します 0.68
k ∑ i=1 i kxi − x′ η2 k ※i=1 i kxi − x′ η2 0.73
d(x, x′) =vuut εi =qkPA(x)i − PB(x)ik2/li d(x, x′) =vuut εi =qkPA(x)i − PB(x)ik2/li 0.87
ik2. (4.1) ik2。 (4.1) 0.79
(4.2) (4.2) 0.78
英語(論文から抽出)日本語訳スコア
AVOIDING TRAPS 7 ♕ 回避トラップ 7 ♕ 0.72
♕ ♕ ♕ ♕ FIGURE 2. ♕ ♕ ♕ ♕ 図2。 0.79
Five queens “dominating” the 8 × 8 chess board; that is, each unoccupied square is attacked by a queen. 5人の女王が8×8のチェス盤を「支配」している。
訳抜け防止モード: 5人の女王が8×8のチェス盤を「支配」 つまり、各無人の広場は、女王によって攻撃されます。
0.67
The domination number of the order 8 queens’ graph is 5 because this is not possible with fewer queens. 位数 8 のクイーングラフの支配数は 5 である、なぜならこれはより少ないクイーンでは不可能であるからである。 0.63
for each variable type. We then compare each εi to the average ε = q 1 変数タイプごとに。 次に、各 εi を平均 ε = q 1 と比較する。 0.76
metric parameters according to metric (複数形 metrics) 0.58
k ∑i ε2 i and adjust the ε2。 私と調整して 0.71
Alternatively, since only the relative weights of the variable types matter, one can set η1 = 1 and take あるいは、変数型の相対的な重みだけが問題となるので、η1 = 1 と take を設定できる。 0.71
ηi → ηi (1 + α(εi/ε1 − 1)) ηi → ηi (1 + α(εi/ε1 − 1)) 0.82
(4.4) ηi → ηi (1 + α(εi/ε− 1)) . (4.4) ηi → ηi (1 + α(εi/ε− 1) である。 0.74
(4.3) for i > 1. (4.3) i > 1 の場合。 0.77
Automatically updating the metric parameters in this fashion encourages the smaller εi’s to become larger and vice versa, which leads to the εi’s being highly correlated, which in turn generally leads to more successful searching. この方法で自動的にパラメーターを更新することで、より小さなεiがより大きくなり、その逆も大きくなり、εiは高い相関関係を持ち、一般的にはより成功した探索につながる。 0.71
This approach also replaces the problem of tuning some (possibly large) number of metric parameters with the simpler question of choosing a value of α. このアプローチはまた、いくつかの(おそらく大きな)計量パラメータをαの値を選択するというより単純な問題にチューニングする問題を置き換える。 0.77
One must have α ≪ 1 in order to make the metric parameter updates adiabatic and thereby preserve the local convergence properties of the algorithm. 計量パラメータを断熱的に更新し、アルゴリズムの局所収束特性を保存するために、α は 1 でなければならない。
訳抜け防止モード: 1 は α > 1 の順でなければならない to make the metric parameter updates adiabatic and makes keep the local convergence properties of the algorithm。
0.87
One also wants α ≫ 1/N, where N is the total number of iterations to be run, so as to accomplish the desired tuning within the intended length of the run. ここで N は実行すべきイテレーションの総数であり、実行の意図した長さ内で所望のチューニングを達成する。
訳抜け防止モード: また、 N が実行すべき繰り返しの総数である α × 1 / N も求めている。 意図した走行距離内で 所望のチューニングを達成するためです
0.74
Accordingly, for large N there can be a rather generous range of α that will work. したがって、大きな N に対して、働く α のかなり寛大な範囲が存在する。 0.78
Experiments. For the following experiments we use the relaxed Douglas-Rachford algorithm (2.1). 実験。 次の実験では、緩和されたダグラス・ラフフォードアルゴリズム(2.1)を用いる。 0.70
In each example we first choose a value of the hyperparameter β that works for that particular problem (β = 0.5 for the dominating sets example, β = 0.8 for the Boolean generative networks example), then choose a challenging instance of the problem and demonstrate the benefits of tuning the metric parameters while keeping the hyperparameter fixed. それぞれの例において、まず、その特定の問題に対して作用するハイパーパラメータβの値を選択する(支配集合の例ではβ = 0.5、ブール生成ネットワークの例ではβ = 0.8)。
訳抜け防止モード: それぞれの例では、その特定の問題(支配集合の例に対して β = 0.5)に作用するハイパーパラメータ β の値を選択する。 ブール生成ネットワークの例 ) β = 0.8 ならば、問題の挑戦的な例を選ぶ。 利益を証明し パラメータを調整し ハイパーパラメータを固定します
0.88
Experiments with dominating sets. 集合を支配する実験。 0.77
Consider a graph G with vertices V and (undirected) edges E. A subset D ⊂ V dominates G if for every vertex i ∈ V either i ∈ D or there exists an adjacent vertex j such that (i, j) ∈ E and j ∈ D. Finding dominating sets of minimum size |D| is a well known NP-hard problem. i ∈ d の任意の頂点 i ∈ v に対して、あるいは (i, j) ∈ e と j ∈ d が隣接する頂点 j が存在して、最小サイズ |d| の支配集合を見つけることは、よく知られたnp-ハード問題である。
訳抜け防止モード: 頂点 V と頂点 V を持つグラフ G を考える。 (無向) すべての頂点 i ∈ V に対して A が G を支配している。 i ∈ D のどちらか あるいは、 ( i, j ) ∈ E であるような隣接する頂点 j が存在する。 j ∈ D の検索 最小サイズの集合を支配下に置く D| はよく知られた NP 問題である。
0.78
Chess players will recognize the configuration shown in Figure 2 チェスプレーヤーは図2に示す構成を認識します 0.77
英語(論文から抽出)日本語訳スコア
8 S. DEYO, V. ELSER 8 S. DEYO, V. ELSER 0.87
active metric parameter tuning アクティブメトリックパラメータチューニング 0.76
1.0 0.9 0.8 1.0 0.9 0.8 0.59
η 0.7 0.6 0.5 η 0.7 0.6 0.5 0.65
0.4 0 100000 0.4 0 100000 0.76
200000 iteration 200000 イテレーション 0.66
300000 400000 300000 400000 0.85
FIGURE 3. Time series of the metric parameter η when tuned automatically in ten trials of finding a dominating set for the order 12 queens’ graph. 図3 メトリックパラメータηの時系列は、オーダー12クイーンズグラフの優位集合を見つけるための10回の試行で自動的にチューニングされる。 0.61
Each curve terminates when the algorithm finds a solution, demarcated by an X. 各曲線は、アルゴリズムが解を見つけ、Xで区切られたときに終わる。 0.74
Note that the tuning consistently leads to η ≈ 0.5. 音色は η 0.5 となることに注意。 0.59
as an instance of a dominating set. 支配セットのインスタンスとして。 0.59
Here the squares of the board are graph vertices and two squares are “connected” by an edge if a queen placed on one attacks the other. ここでは、ボードの正方形はグラフ頂点であり、2つの正方形は、一方の女王が他方を攻撃した場合、エッジによって“接続”される。
訳抜け防止モード: ボードの正方形はグラフ頂点で 2つの正方形は、一方の女王が他方を攻撃した場合、エッジによって“接続”される。
0.72
The domination number of this particular board/graph is |D| = 5 because the five queens attack all the other squares and this is not possible with fewer queens. このボード/グラフの支配数は |D| = 5 であるため、5つのクイーンが他のすべての正方形を攻撃し、より少ないクイーンでは不可能である。
訳抜け防止モード: このボード/グラフの支配数は |D| = 5 である。 五つの女王は 他の四角を攻撃し より少ない女王では不可能だ
0.75
That a vertex may be dominated either by itself or an adjacent vertex calls for two types of variable in a constraint formulation. 頂点はそれ自体によって支配されるか、隣接する頂点が制約の定式化において2種類の変数を呼び出します。
訳抜け防止モード: 頂点はそれ自体または隣接する頂点によって支配されるかもしれない 制約の定式化で2種類の変数を呼び出す。
0.76
A metric parameter should be introduced to control their relative “weight.” Our formulation uses vertex variables yi, i ∈ V and two variables for each edge (i, j) ∈ E: xi→ j and x j→i. 我々の定式化では、各辺 (i, j) ∈ e: xi→j と xj→i に対して頂点変数 yi, i ∈ v と2つの変数を用いる。
訳抜け防止モード: 相対的な"重み"を制御するためにメートル法パラメータを導入する必要がある。 我々の定式化は頂点変数 yi, i ∈ V と各辺 ( i, j ) ∈ E : xi→ j と x j→i の2つの変数を使用する。
0.70
We denote the set of doubled edges E2. 二重辺 E2 の集合を表す。 0.59
One can think of xi→ j as a copy of vertex i that vertex j uses to express its domination status. xi→j を頂点 j がその支配状態を表現するのに使用する頂点 i のコピーと考えることができる。 0.70
Since there are only two variable types, a single metric parameter η suffices to characterize the weight of the vertex variables relative to the edge variables. 2つの変数タイプしか存在しないため、単一のメトリックパラメータηは、頂点変数のエッジ変数に対する重みを特徴付けるために十分である。 0.80
Constraint A demands that every vertex is either selfdominating or is dominated by at least one adjacent vertex via an incident edge, with at most |D| vertices being self-dominating, while constraint B demands that all edge variables agree with their associated vertex variable: 制約 a は、すべての頂点が自己支配的であるか、または入射エッジを介して隣接する少なくとも1つの頂点によって支配されるように要求し、少なくとも |d| 頂点は自己支配であり、制約 b は、すべての辺変数が対応する頂点変数と一致するように要求する。 0.54
A : B : ∀ j → i ∈ E2 : a: b: J → i ∈ E2 : 0.72
x j→i ∈ {0, 1} , x j→i ∈ {0, 1} , 0.98
∀ i ∈ V : I ∈ V である。 0.64
∑ i ∈ V I ∈ V である。 0.65
yi/η ≤ |D| yi/η ≤ |D| 0.59
, yi ∈ {0,η} ∧ yi/η + ∑ j→i , yi ∈ {0,η} > yi/η + > j→i 0.85
x j→i ≥ 1 , x j→i ≥ 1 , 0.88
∀ j → i ∈ E2 : J → i ∈ E2 : 0.62
x j→i = y j/η . x j→i = y j/η 。 0.68
Projections to both constraint sets is an easy computation. 両方の制約集合への射影は簡単な計算である。 0.60
Constraint A is slightly non-local in that all the vertices need to be ranked by their distance to yi = η over yi = 0 when selecting the optimal subset of size |D|. 制約 A は、大きさ |D| の最適部分集合を選択するとき、すべての頂点は yi = η よりも yi = 0 までの距離でランク付けする必要があるという点においてわずかに非局所的である。 0.59
英語(論文から抽出)日本語訳スコア
AVOIDING TRAPS 9 FIGURE 4. 回避トラップ 9 図4。 0.66
Network architecture (left) that takes 7 Boolean inputs and outputs 14 Boolean data; there is also an intermediate layer that holds 14 Boolean values. 7つのBoolean入力を受け、14個のBooleanデータを出力するネットワークアーキテクチャ(左)。
訳抜け防止モード: 7個のBoolean入力を受け取り14個のBooleanデータを出力するネットワークアーキテクチャ(左) また、14のブール値を保持する中間層が存在する。
0.82
The trained BGN (right) is a logical circuit that uses relatively few of the available network edges as wires. 訓練されたBGN(右)は、利用可能なネットワークエッジの比較的少ない部分をワイヤとして使用する論理回路である。 0.71
All the nodes not in the input layer apply OR to the wires incident from below. 入力層にない全てのノードは、下から入ってくるワイヤにORを適用する。 0.69
Training also determines the placement of the NOT gates, which are indicated by red wires. トレーニングはまた、赤いワイヤーで示されるNOTゲートの配置を決定する。 0.64
Figure 3 plots the progress of the metric parameter as the algorithm searches for a dominating set of size |D| = 6 for the queens’ graph of order 12. 図3は、アルゴリズムが位数12のクイーンズグラフに対して、サイズ |d| = 6 の支配的な集合を探索するときに、メトリックパラメータの進行をプロットする。 0.75
Each curve in the figure terminates when the algorithm finds a solution. 図の各曲線は、アルゴリズムが解を見つけると終了する。 0.74
The average number of iterations required for this collection of trials was about 2 × 105; for comparison, the same algorithm with no metric parameter tuning often fails to find a solution after 106 iterations. この試行の収集に必要な平均的な反復回数は約2×105であり、比較すると、パラメータのチューニングがない同じアルゴリズムは106回の反復で解を見つけるのに失敗することが多い。 0.73
Note that the metric parameter consistently tunes itself to a value near 0.5. メトリックパラメータは一貫して0.5に近い値にチューニングされる。 0.79
For other problems the optimal parameter is in general something else, but the benefit of letting the weights tune themselves is that the user need not change any settings in order to solve another instance (apart from increasing the maximum number of iterations for harder instances). 他の問題に対して、最適なパラメータは一般的に別の何かである。しかし、重み付けを自分自身にチューニングさせる利点は、ユーザが他のインスタンスを解決するためにいかなる設定も変更する必要がなくなることである。 0.71
Experiments with Boolean generative networks. boolean生成ネットワークによる実験。 0.86
Our second example of automated metric parameter tuning is unsupervised machine learning with a Boolean generative network, or BGN [11]. 自動メトリックパラメータチューニングの第2の例は、ブール生成ネットワーク(bgn [11])を使用した教師なし機械学習です。 0.68
The data in this application consist of a set of D Boolean strings of length N, and the network is tasked with discovering a Boolean circuit that generates the strings from a smaller number M < N of Boolean “latent variables” whose values for each data string are unknown. このアプリケーション内のデータは、長さnのdブール文字列のセットで構成されており、ネットワークは、各データ文字列の値が未知なブール “latent variable” のより小さい数 m < n から文字列を生成するブール回路を発見する。 0.74
Figure 4 compares a network before and after training. 図4はトレーニング前後のネットワークを比較します。 0.86
Nodes of the network are arranged in layers and initially each node can potentially receive input from any node in the layer below. ネットワークのノードはレイヤに配置され、まず各ノードは下のレイヤの任意のノードから入力を受け取ることができる。 0.80
However, the data come with the promise or hypothesis that they can be generated with only NOT and 2-input OR gates. しかし、データは not と 2-input あるいは gate だけで生成できるというpromise または hypothesis を伴っている。 0.77
Through training the network must therefore discover which of the many edges are utilized in the circuit, that is, the “wires” of the circuit, and whether the Boolean value is to be negated when traversing the wire. それゆえ、ネットワークは、回路においてどのエッジが使われているか、すなわち、回路の「ワイヤ」、およびワイヤを横切る際にブール値が否定されるかどうかを検出する必要がある。 0.76
The truth value at a node i of the BGN is encoded by a variable yi at that node and also by copies of that truth value on all its out-edges, xi→ j. BGN のノード i における真理値は、そのノードにおける変数 yi と、そのすべての外縁 xi → j 上の真理値のコピーによって符号化される。 0.83
These two variable types have the same interpretation they had in the dominating set application and serve to localize the constraints. これら2つの変数型は、支配的なセットアプリケーションと同じ解釈を持ち、制約をローカライズするのに役立ちます。 0.67
However, by the uni-directional nature of the BGN logic, there is no need to have a second variable on each edge. しかし、BGN論理の一方向性により、各エッジに2番目の変数を持つ必要はない。
訳抜け防止モード: しかし、ユニ-方向性のBGN論理により。 必要ありません それぞれのエッジに2番目の変数があります
0.77
Just as with dominating sets, the semantic equivalence of the x and y variables does not imply metrical equivalence and we control their relative scale with metric parameters θ and η. 支配集合と同様に、x と y 変数の意味同値は計量同値を意味するものではなく、計量パラメータθ と η でそれらの相対スケールを制御する。 0.77
The relevance of metric parameters in BGNs is made especially obvious when we also consider the variables wi→ j used to encode whether an edge i → j of the network is a wire and if BGNsにおける計量パラメータの関連性は、ネットワークのエッジ i → j がワイヤであるかどうかを符号化するのに使われる変数 wi → j を考えるとき、特に明らかとなる。 0.82
英語(論文から抽出)日本語訳スコア
10 S. DEYO, V. ELSER 10 S. DEYO, V. ELSER 0.87
w2 (- ,ω ( ,ω w2 (- ,ω ( ,ω 0.83
(0,0 w1 FIGURE 5. (0,0 W1 図5 0.61
A 2D space (w1, w2) is required to encode the three possible states of edges in a BGN. 2次元空間 (w1, w2) は、BGN内のエッジの3つの状態を符号化するために必要である。
訳抜け防止モード: 2次元空間 (w1, w2 ) が必要となる。 エッジの3つの状態をBGNにエンコードする。
0.78
The red and blue points correspond to edges utilized as wires with and without negation; the open circle encodes the absence of a wire. 赤と青の点は、ワイヤとして使われるエッジにネゲーションなしで対応し、開円はワイヤの欠如をエンコードする。 0.71
Two metric parameters, σ and ω, define the isosceles geometry of the states. 2つの計量パラメータ σ と ω は、状態の等長幾何学を定義する。 0.75
so, its negation state. つまり、その否定状態です。 0.73
To encode the three states of an edge as three points we should use a 2D space to make available the most general metrical relationship among the states. エッジの3つの状態を3つの点として符号化するためには、2次元空間を使って状態間の最も一般的な計量関係を利用できるようにする。
訳抜け防止モード: 辺の3つの状態を3つの点として符号化する 2次元の空間を 国家間の最も一般的な計量関係を利用可能にする。
0.69
Not only is the wire-status of an edge semantically distinct from the truth states it operates on, the existence of a wire (on the edge) should have independence, metrically, over its two negation states. エッジのワイヤー統計は、それが作用する真理状態とは意味的に異なるだけでなく、(エッジ上の)ワイヤーの存在はその2つの否定状態に対して独立性を持つべきである。 0.72
These considerations are addressed by encoding the wire states by the vertices of an isosceles triangle as shown in Figure 5. これらの考察は、図5に示すように、等長三角形の頂点によるワイヤー状態の符号化によって解決される。
訳抜け防止モード: これらの考慮事項は 図5に示すように、等角三角形の頂点によるワイヤ状態の符号化
0.80
The metric parameter ω now controls the distance between presence and absence of a wire, while σ controls the distance between the presence and absence of a NOT. 計量パラメータωは、ワイヤの存在と不在の間の距離を制御し、σはNOTの存在と不在の間の距離を制御している。 0.78
In order to solve the problem we create a copy of the network for each of the D data strings. この問題を解決するために、各Dデータ文字列のネットワークのコピーを作成します。 0.70
One of the constraints is that the choice of wire states is the same across all copies of the network. 制約の1つは、ネットワークの全コピー間でワイヤ状態の選択が同じであるということである。 0.76
The states (truth values) of the nodes will in general be different, as they depend on each instantiation of the network through the data string. ノードの状態(真値)は、データ文字列を介してネットワークの各インスタンス化に依存するため、一般的に異なるものになる。 0.74
It often happens that certain nodes and edges in the network are more important than others. ネットワーク内の特定のノードやエッジが他のノードよりも重要であることがよくある。 0.71
For instance, nodes in different layers or having different in- or out-degrees could play markedly different roles. 例えば、異なるレイヤのノードや異なるイングレードまたはアウトグレードを持つノードは、著しく異なる役割を演じることができる。 0.55
It is natural then to let the metric parameters be different for every node and edge in the network, promoting ω, σ, θ, and η to ωi→ j, σi→ j, θi→ j, and ηi. 計量パラメータがネットワーク内のすべてのノードとエッジで異なり、ω, σ, θ, η を ωi→j, σi→j, θi→j, ηi へと促進することは自然である。 0.84
Finally, one could also argue that the D data strings have differing inherent difficulty and deserve suitably tuned metric parameters applied to their copies of the network. 最後に、Dデータ文字列は固有の難易度が異なり、ネットワークのコピーに適用されたパラメータを適切に調整する価値があるとも主張できる。 0.69
Instead of a single ωi→ j parameter for edge i → j there would then be parameters ωd, i→ j for d = 1, . 辺 i → j の単一の ωi→ j パラメータの代わりに、パラメータ ωd, i→ j が d = 1 に対して存在する。 0.85
. . , D and similarly for the other variable types. . . , d および他の変数型も同様である。 0.84
Below we refer to these refinements of metric parameter tuning as by “type,” “network location,” and “data item.” We compared the different degrees of metric parameterization on a synthetic data set generated by the circuit in Figure 4 with M = 7 inputs and N = 14 outputs. 以下は「タイプ」、「ネットワーク位置」、「データ項目」によるパラメータチューニングの洗練について述べ、図4の回路で生成された合成データセットのパラメータ化の度合いをM = 7入力とN = 14出力と比較した。
訳抜け防止モード: 以下は、メトリックパラメータチューニングのこれらの改良を“タイプ”と呼ぶ。 ネットワークの位置」と「データ項目」は、図4の回路が生成する合成データ集合上で、m = 7の入力とn = 14の出力とで異なるメトリックパラメータ化の度合いを比較した。
0.84
For training we used all D = 87 unique data strings generated by this circuit and initialized the variables (on nodes and edges of the complete architecture) to random values selected in the ranges of the four “type” parameters (ω, σ, θ, η). トレーニングでは、この回路で生成されたD = 87個のデータ列を全て使用し、変数(完全なアーキテクチャのノードとエッジ)を4つの"タイプ"パラメータ(ω, σ, θ, η)の範囲で選択されたランダム値に初期化した。 0.79
Solutions (circuits) were only required to generate all D data strings for some setting of the M inputs. 解(回路)は、M入力のいくつかの設定のためにすべてのDデータ文字列を生成するためにのみ必要であった。 0.60
Typically the solution circuits additionally generated strings not among the D data strings, though never a set of size 2M. 典型的には、解回路はDデータストリングの中にない文字列を生成するが、サイズは2Mではない。 0.67
Figure 6 plots the time series of the constraint errors for each of the four variable types — εw1, εw2, εx, εy — for each of the four degrees of metric parameter tuning. 図6は、4つの変数タイプ(εw1, εw2, εx, εy)のそれぞれに対する4つのパラメータチューニングのそれぞれに対する制約エラーの時系列をプロットする。 0.83
The top left plot is for the naive choice of metric parameters with no tuning; that is, we set σ = ω = θ = η = 1 and take α = 0 in (4.3). すなわち、σ = ω = θ = η = 1 とし、α = 0 in (4.3) とする。
訳抜け防止モード: 左上のプロットは、チューニングなしのメトリックパラメータのナイーブな選択のためのものです。 σ = ω = θ = η = 1 とする。 α = 0 in (4.3 ) とする。
0.77
The constraint error for w2 quickly drops to zero, but the others stay at roughly constant nonzero values. w2 の制約誤差はすぐにゼロに落ちるが、他の値は概してゼロではない値に留まる。 0.71
Clearly this search is stuck on a non-solution. 明らかにこの検索は非解決に留まっている。 0.72
In the top right plot, we again initialize the metric parameters to 1 but now we set α = 10−4 to allow the four parameters to be slowly tuned as the search progresses. 右上のプロットでは、再びパラメータを 1 に初期化するが、α = 10−4 を設定し、探索が進むにつれて4つのパラメータをゆっくりと調整できるようにする。 0.77
One can see that the search does 検索が可能であることが分かる 0.80
英語(論文から抽出)日本語訳スコア
0.30 0.25 0.20 0.30 0.25 0.20 0.59
r o r r e r o r e である。 0.77
0.15 0.10 0.05 0.15 0.10 0.05 0.59
0.00 0.30 0.25 0.00 0.30 0.25 0.59
0.20 r o r r e 0.20 r o r e である。 0.68
0.15 0.10 0.05 0.15 0.10 0.05 0.59
0.00 0 20000 0.00 0 20000 0.76
AVOIDING TRAPS 11 none 回避トラップ 11 なし 0.65
by type w1 w2 x y by‐type w1 w2 x y 0.78
w1 w2 x y by type and location w1 w2 x y タイプと場所によって 0.76
w1 w2 x y w1 w2 x y w1 w2 x y w1 w2 x y 0.84
by type, location, and data item タイプ、場所、データ項目によって 0.82
40000 60000 40000 60000 0.85
iteration 80000 イテレーション 80000 0.66
100000 0 20000 100000 0 20000 0.85
40000 iteration 40000 イテレーション 0.66
60000 80000 60000 80000 0.85
100000 FIGURE 6. Time series of the constraint errors for the BGN problem with four levels of metric parameter tuning. 100000 図6 メトリックパラメータチューニングの4つのレベルを持つbgn問題の制約誤差の時系列。 0.67
Top left: no tuning. 左上:チューニングなし。 0.55
Top right: tuning by variable type. 右上: 変数型によるチューニング。 0.61
Bottom left: tuning by type and location within the network. 左下: ネットワーク内のタイプとロケーションによるチューニング。 0.69
Bottom right: tuning by type, location, and data item. Bottom right: タイプ、ロケーション、データ項目によるチューニング。 0.66
The four errors in each plot are those of the four variable types described in the text. 各プロットの4つの誤りは、テキストに記述された4つの変数の型である。 0.71
not get stuck the way it did with α = 0. α = 0 の場合のように立ち往生しない。 0.73
In the bottom left plot, we promote ω to ωi→ j, σ to σi→ j, and so on, to allow the metric parameters to vary also by location within the network. 左側のプロットでは、ω を ωi→j に、σ を σi→ j に促進し、計量パラメータがネットワーク内の位置によっても変化するようにする。 0.71
We still initialize the parameters to 1 and use α = 10−4. パラメータを1に初期化し、α = 10−4を使用する。 0.78
This search is even more effective, with the four constraint errors strongly correlated. この探索はさらに効果的で、4つの制約誤差は強く相関している。 0.69
It terminates early because it finds a solution after about 4 × 104 iterations. 約 4 × 104 回の反復の後に解が見つかるため、早期に終了する。 0.71
Finally, in the bottom right we go one step further, promoting ωi→ j to ωd, i→ j, σi→ j to σd, i→ j, and so on, to allow the metric parameters to vary by data item as well. 最後に、右下のほうでは、ωi→j を ωd, i→j, σi→j を σd, i→j などへ促進し、計量パラメータをデータ項目によっても変化させる。 0.71
As always we initialize the metric parameters to 1, and we still use α = 10−4. いつものように、計量パラメータを 1 に初期化し、α = 10−4 を使用する。 0.72
The search is better than it was with no tuning, but not much better than tuning by type and not as effective as tuning by type and location. 検索はチューニングなしで行うよりも優れているが、型によるチューニングよりは優れており、型と位置によるチューニングほど効果的ではない。 0.72
Even though the four plots in Figure 6 only show a single example of a search for each level of tuning, the examples chosen are representative: Tuning by type and location consistently outperforms the other approaches. 図6の4つのプロットは、チューニングの各レベルを検索する単一の例しか示していませんが、選択した例は次のとおりです。 0.60
We have also tried other tuning combinations, such as by type and data item but not location, and the performance is similar to that of tuning by type, location, and data item. また、タイプやデータ項目によるチューニングの組み合わせも試しましたが、位置ではなく、タイプ、位置、データ項目によるチューニングと同じようなパフォーマンスを実現しています。 0.69
Evidently adding more metric parameters is not always better. より多くのメトリックパラメータを追加するのが必ずしも良いとは限らない。 0.53
Tuning by location was helpful in this example, but tuning by data item was not. この例ではロケーションによるチューニングが有効だったが、データ項目によるチューニングは役に立たなかった。 0.57
One possible interpretation of these results is that metric parameters have tangible effects only when they target systematic or structural properties of the variables. これらの結果の考えられる解釈の1つは、メトリックパラメータが変数の体系的または構造的性質を対象とする場合にのみ具体的効果を持つということである。 0.60
The nodes of the BGN distinguish themselves by their in- and out-degrees, and also their distance from data constraints (imposed only at the output layer). bgnのノードは、自身のin-degreeとout-degreesと、データ制約(出力層のみ)との距離によって区別される。 0.68
We should therefore expect a metric-tuning benefit based on したがって、メトリックチューニングの利点を期待すべきである。 0.53
英語(論文から抽出)日本語訳スコア
12 S. DEYO, V. ELSER 12 S. DEYO, V. ELSER 0.87
network location just as for the more obvious case of variables distinct by type (node vs. edge). 型によって異なる変数(ノード対エッジ)のより明確な場合と同様に、ネットワークロケーション。 0.80
In the case of variables differing only by the data index, the structural bias is much weaker. データインデックスによってのみ異なる変数の場合、構造バイアスはより弱い。 0.63
For most of these variables the structural difference is only indirect, through the fixed-value data constraints at the output nodes. これらの変数のほとんどの場合、構造的差は出力ノードの固定値データ制約を通して間接的にのみ発生する。 0.71
An alternative viewpoint is that metric parameters facilitate symmetry breaking behavior. 別の見方として、メートル法パラメータは対称性の破れ行動を促進する。 0.56
For example, it may be important that nodes within the same layer are able to develop unique characteristics, even while the associated node and edge variables have a permutation symmetry. 例えば、同じ層内のノードが、関連するノードとエッジ変数が置換対称性を持つにもかかわらず、ユニークな特性を発達させることが重要である。 0.76
Likewise, some data items might pose a greater challenge to the circuit than others, and the metric parameters of their associated variables would serve to break that form of permutation symmetry. 同様に、いくつかのデータ項目は回路に他のものよりも大きな課題を生じさせ、関連する変数の計量パラメータは置換対称性の形式を破るのに役立つ。 0.83
Although our survey of results is far from comprehensive, the absence of a noticeable benefit from tuning by data index leads us to believe that the structural hypothesis is better supported than symmetry breaking. 結果のサーベイは包括的ではないものの、データインデックスによるチューニングによる明らかなメリットの欠如は、構造仮説が対称性の破れよりも優れていると信じている。 0.74
5. CONCLUSIONS 5. コンキュレーション 0.67
We suspect that quite a few applications of iterative projection methods on nonconvex problems may have been abandoned because of a failure to recognize a sensitivity to parameters. 非凸問題に対する反復射影法の適用が、パラメータに対する感度の認識に失敗したために放棄された可能性がある。 0.68
Even in the case of hyperparameters, a setting in a range that is “safe” with respect to local convergence (where the constraints may be approximated as convex) overlooks the fact that these parameters also have a profound effect on the global characteristics of the search. ハイパーパラメータの場合でさえ、局所収束(凸として近似されるかもしれない)に関して「安全」な範囲における設定は、これらのパラメータが探索のグローバルな特性にも深い影響を与えるという事実を無視する。 0.82
We saw an example of this in the Douglas-Rachford generalization of section 3, where the contractivity δ needs to be tuned to a sweet spot for effective search. ダグラス・ラッチフォード(douglas-rachford)による第3節の一般化では、契約率 δ を実効探索のためにスイートスポットに調整する必要がある。 0.54
The tuning of metric parameters is equally important in applications where there is a rescaling freedom among variables not subject to symmetry. メトリックパラメータのチューニングは、対称性に従わない変数間で再スケーリングの自由度があるアプリケーションでも同様に重要である。 0.78
Such applications, without the translation or permutation symmetries of phase retrieval or a sudoku puzzle, are relatively new for iterative projection methods. このような応用は、相検索や数独パズルの変換や置換対称性がなければ、反復射影法は比較的新しいものである。 0.65
Recognizing the role of the metric in such applications, and not arbitrarily assigning 1 as the relative scale, is an important first step. このようなアプリケーションにおけるメトリックの役割を認識し、相対的なスケールとして1を任意に割り当てないことは、重要な第一歩です。 0.70
One can tune the metric parameters by hand, but here we have introduced a method for updating them automatically based on constraint errors. 手動でパラメータをチューニングできますが、ここでは制約エラーに基づいて自動的にパラメータを更新する方法を紹介します。
訳抜け防止モード: メトリックパラメータを手でチューニングできます。 しかし,ここでは制約エラーに基づいて自動的に更新する手法を導入した。
0.79
This approach is particularly useful when there are many metric parameters to tune. このアプローチは、チューニングすべきメトリックパラメータが多数ある場合に特に有用である。 0.75
Acknowledgments The authors thank Avinash Mandaiya for noticing the two variable types in the dominating set problem and Jim Sethna for useful conversations. Avinash Mandaiya氏(リンク)は、支配的なセット問題における2つの変数タイプに気付き、Jim Sethna氏(リンク)は有益な会話に感謝している。
訳抜け防止モード: Avinash Mandaiya氏に感謝する 支配的集合問題における2つの変数型と有用な会話のためのJim Sethnaに気づく。
0.79
REFERENCES [1] V. Elser, The complexity of bit retrieval, IEEE Transactions on Information Theory 64.1 (2017), 412-428. 参考 [1] V. Elser, The complexity of bit search, IEEE Transactions on Information Theory 64.1 (2017), 412-428。 0.71
[2] F.J.A. Artacho, J.M. F.J.A。 アルタチョ j. m. 0.60
Borwein, and M.K. ボルウィンとm.k. 0.50
Tam, Global behavior of the Douglas–Rachford method for a non- 非-に対するダグラス・ラフフォード法のタム、大域的挙動 0.56
convex feasibility problem, Journal of Global Optimization 65.2 (2016), 309-327. convex feasibility problem, Journal of Global Optimization 65.2 (2016), 309-327。 0.93
[3] V. Elser, Matrix product constraints by projection methods, Journal of Global Optimization 68.2 (2017), [3] v. elser, matrix product constraints by projection methods, journal of global optimization 68.2 (2017)
訳抜け防止モード: [3 ] V. Elser, Matrix product constraints by projection method, Journal of Global Optimization 68.2 (2017),
0.92
329-355. [4] F.J.A. 329-355. F.J.A. 0.71
Artacho, R. Campoy, and M.K. Artacho、R. Campoy、M.K. 0.85
Tam, The Douglas–Rachford algorithm for convex and nonconvex Tam, the Douglas–Rachford algorithm for convex and nonconvex 0.98
feasibility problems, Mathematical Methods of Operations Research 91.2 (2020), 201-240. 実現可能性問題、数理操作方法 91.2 (2020), 201-240。 0.67
[5] J.R. Fienup, Phase retrieval algorithms: a comparison, Applied optics 21.15 (1982), 2758-2769. 5] j.r. fienup, phase search algorithms: a comparison, applied optics 21.15 (1982), 2758-2769。 0.86
[6] V. Elser, T.-Y. V. Elser, T.-Y. 0.71
Lan, and T. Bendory, Benchmark problems for phase retrieval, SIAM Journal on Imaging Lan, and T. Bendory, Benchmark problem for phase retrieve, SIAM Journal on Imaging 0.88
Sciences 11.4 (2018), 2429-2455. 11.4(2018年)、2429-2455頁。 0.37
[7] F.J.A. Artacho, J.M. F.J.A. アルタチョ j. m. 0.61
Borwein, and M.K. ボルウィンとm.k. 0.50
Tam, Recent results on Douglas–Rachford methods, Serdica Math- Tam, recent results on Douglas–Rachford method, Serdica Math- 0.90
ematical Journal 39.3-4 (2013), 313-330. ematical Journal 39.3-4 (2013), 313-330。 0.72
英語(論文から抽出)日本語訳スコア
AVOIDING TRAPS 13 [8] V. Elser, Learning without loss, arXiv preprint arXiv:1911.00493 (2019). 回避トラップ 13 V. Elser, Learning without Los, arXiv preprint arXiv:1911.00493 (2019) 0.70
[9] S. Gravel, and V. Elser, Divide and concur: A general approach to constraint satisfaction, Physical Review E [9]S.グレーベルとV.エルサー,ディバイド,コンクル:制約満足度に対する一般的アプローチ,物理レビューE 0.74
78.3 (2008), 036706. 78.3 (2008), 036706. 0.96
[10] D. Mitchell, B. Selman, and H. Levesque, Hard and easy distributions of SAT problems, AAAI Vol. 10] D. Mitchell, B. Selman, H. Levesque, Hard and easy distributions of SAT problem, AAAI Vol。 0.84
92 (1992). 92 (1992). 0.85
[11] V. Elser, Reconstructing cellular automata rules from observations at nonconsecutive times, arXiv preprint V. Elser, Reconstructing cellular automation rules from Observation at nonconsecutive time, arXiv preprint 0.67
arXiv:2012.02179 (2020). arXiv:2012.02179 (2020)。 0.66
                           ページの最初に戻る

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