論文の概要、ライセンス

# (参考訳) 弾性距離の早期放棄と刈り取り [全文訳有]

Early Abandoning and Pruning for Elastic Distances ( http://arxiv.org/abs/2102.05221v1 )

ライセンス: CC BY 4.0
Matthieu Herrmann and Geoffrey I. Webb(参考訳) 弾性距離は時系列分析の重要なツールです。 簡単な実装では、o(n2)スペースと時間の複雑さが必要であり、多くのアプリケーションが長いシリーズにスケールするのを防ぐ。 これらのアプリケーションのスピードアップに費やす多くの作業は、主に下限の開発に費やされており、与えられたしきい値を超えるとコストのかかる距離計算を避けることができる。 このしきい値はまた、距離自体の計算を早期に放棄することができる。 DTW用に開発された別のアプローチは、計算の一部をプルークするものである。 これらの技法は互いに直交している。 本研究では,早期放棄とプルーニングを緊密に統合する新しい総合戦略である「EAPruned」を開発する。 提案手法をDTW, CDTW, WDTW, ERP, MSM, TWEに適用し, NN1のようなシナリオの大幅な高速化を示す。 プルーニングはまた、いくつかの距離に対してかなりのスピードアップを示し、すべてのペアワイズ距離が必要なクラスタリングのようなアプリケーションにより、早期放棄は適用されない。 時系列分類のための新しいC++ライブラリの一部として、使用しやすいPython/Numpyバインディングとともに実装をリリースします。

Elastic distances are key tools for time series analysis. Straightforward implementations require O(n2)space and time complexities, preventing many applications from scaling to long series. Much work hasbeen devoted in speeding up these applications, mostly with the development of lower bounds, allowing to avoid costly distance computations when a given threshold is exceeded. This threshold also allows to early abandon the computation of the distance itself. Another approach, developed for DTW, is to prune parts of the computation. All these techniques are orthogonal to each other. In this work, we develop a new generic strategy, "EAPruned", that tightly integrates pruning with early abandoning. We apply it to DTW, CDTW, WDTW, ERP, MSM and TWE, showing substantial speedup in NN1-like scenarios. Pruning also shows substantial speedup for some distances, benefiting applications such as clustering where all pairwise distances are required and hence early abandoning is not applicable. We release our implementation as part of a new C++ library for time series classification, along with easy to usePython/Numpy bindings.
公開日: Wed, 10 Feb 2021 02:13:27 GMT

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

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Early Abandoning and Pruning for Elastic Distances 弾性距離の早期放棄と刈り取り 0.63
Matthieu Herrmann, Geoffrey I. Webb Matthieu Herrmann, Geoffrey I. Webb 0.97
Monash University, Australia オーストラリア・モナシュ大学 0.69
{matthieu.herrmann,ge off.webb}@monash.edu {matthieu.herrmann,ge off.webb}@monash.edu 0.67
1 2 0 2 b e F 0 1 1 2 0 2 b e F 0 1 0.85
] G L . ] G L。 0.79
s c [ 1 v 1 2 2 5 0 sc [ 1 v 1 2 2 5 0 0.68
. 2 0 1 2 : v i X r a . 2 0 1 2 : v i X r a 0.85
Abstract Elastic distances are key tools for time series analysis. 概要 弾性距離は時系列分析の重要なツールです。 0.62
Straightforward implementations require O(n2) space and time complexities, preventing many applications from scaling to long series. 簡単な実装では、o(n2)空間と時間の複雑さが必要であり、多くのアプリケーションが長いシリーズにスケールするのを防ぐ。 0.58
Much work has been devoted in speeding up these applications, mostly with the development of lower bounds, allowing to avoid costly distance computations when a given threshold is exceeded. 多くの作業は、主に低い境界の開発で、これらのアプリケーションのスピードアップに費やされており、特定のしきい値を超えるとコストのかかる距離計算を避けることができます。 0.67
This threshold also allows to early abandon the computation of the distance itself. このしきい値はまた、距離自体の計算を早期に放棄することができる。 0.71
Another approach, developed for DTW, is to prune parts of the computation. DTW用に開発された別のアプローチは、計算の一部をプルークするものである。 0.63
All these techniques are orthogonal to each other. これらの技法は互いに直交している。 0.63
In this work, we develop a new generic strategy, “EAPruned”, that tightly integrates pruning with early abandoning. 本研究では,新しい汎用戦略である「EAPruned」を開発し,早期放棄とプルーニングを緊密に統合する。 0.70
We apply it to DTW, CDTW, WDTW, ERP, MSM and TWE, showing substantial speedup in NN1-like scenarios. 提案手法をDTW, CDTW, WDTW, ERP, MSM, TWEに適用し, NN1のようなシナリオの大幅な高速化を示す。 0.68
Pruning also shows substantial speedup for some distances, benefiting applications such as clustering where all pairwise distances are required and hence early abandoning is not applicable. プルーニングはまた、いくつかの距離に対してかなりのスピードアップを示し、すべてのペアワイズ距離が必要なクラスタリングのようなアプリケーションにより、早期放棄は適用されない。 0.55
We release our implementation as part of a new C++ library for time series classification, along with easy to use Python/Numpy bindings. 時系列分類のための新しいC++ライブラリの一部として実装をリリースし、Python/Numpyバインディングを使いやすくしました。 0.73
1 Introduction Elastic distances are important tools for time series classification [30], clustering [12], outlier detection [2] and similarity search [26]. はじめに 弾性距離は時系列分類[30],クラスタリング[12],異常検出[2],類似性探索[26]にとって重要なツールである。 0.70
An elastic distance computes a similarity score, lower scores indicating greater similarity. 弾性距離は類似度スコアを計算し、より類似度の高い低いスコアを示す。 0.59
This property makes them fit for nearest neighbor classifiers, which have historically been a preferred approach to time series classification. この性質は、時系列分類において歴史的に好ましいアプローチである近隣の分類器に適合する。 0.80
Dynamic Time Warping (DTW) is a widely used elastic distance, introduced in 1971 by [21, 20] along with its constrained variant CDTW. ダイナミック・タイム・ワーピング (dynamic time warping, dtw) は、1971年に [21, 20] によって導入された弾性距離である。 0.73
While state of the art classifiers are now significantly more accurate than simple nearest neighbor classifiers, some utilize elastic distances in more sophisticated ways [14, 15, 16, 24]. アート分類器の状態は、単純な近辺の分類器よりもかなり正確になったが、より洗練された方法で弾性距離を利用する(14,15,16,24]。 0.72
Two key strategies that have been developed for speeding up elastic distance computations are pruning and early abandoning. 弾性距離計算を高速化するために開発された2つの重要な戦略はプルーニングと早期放棄である。 0.67
Pruning identifies and saves computation of parts of the cost matrix that cannot be on the optimal path (see Section 2). プルーニングは最適経路に到達できないコスト行列の一部の計算を識別し保存する(第2節参照)。 0.67
Early abandoning comes in two kinds. 早期放棄は2種類あります。 0.68
The first one, “computation abandoning”, terminates computation when some internal variable exceeds a threshold. 最初の「計算放棄」は、内部変数がしきい値を超えると計算を終了します。 0.77
The second one, “lower bounding”, first computes a lower bound (an approximated minimal score), and then only proceeds to compute the actual score if the lower bound is below a threshold. 2番目の「より低い境界」は、まず下限(近似された最小スコア)を計算し、その後、下限がしきい値を下回っている場合にのみ実際のスコアを計算します。 0.77
Early abandoning is useful in applications such as nearest neighbor search for which it is possible to derive thresholds above which the precise score is not relevant. 早期放棄は、正確なスコアが関連していない上記のしきい値を引き出すことができる最も近い隣探索などのアプリケーションで有用である。 0.78
In this paper we develop a new strategy, “EAPruned”, that tightly integrates pruning and early abandoning. 本稿では,刈り取りと早期放棄を緊密に統合する新しい戦略である「EAPruned」を開発する。 0.79
We investigate its effectiveness with six key elastic distances. 6つの主要な弾性距離でその有効性を調べます。 0.53
To enable fair comparison, we implemented several versions of the distances in C++ and compared their run times using NN1 classification over the UCR archive (in its 85 univariate datasets version). 公平な比較を可能にするため、我々はC++でいくつかのバージョンを実装し、UMCアーカイブ上のNN1分類(85の単変量データセットバージョン)を用いて実行時間を比較した。 0.62
We show that EAPruned offers significant speedups: around 7.62 times faster then a simple implementation, and around 2.88 times faster than an implementation 私たちはeaprunedが大きなスピードアップを提供していることを示しています: 実装の約7.62倍、実装の約2.88倍です。
訳抜け防止モード: EAPrunedは7.62倍高速で簡単な実装を実現しています。 実装の約2.88倍の速度で
0.61
∗ This research has been supported by Australian Research Council grant DP210100072. ∗ この研究は、オーストラリア研究評議会がDP210100072を認可している。 0.74
1 1 0.85
英語(論文から抽出)日本語訳スコア
with the usual computation abandoning scheme. いつもの計算放棄スキームで。 0.58
We also show, in the cases of DTW and CDTW, that lower bounding is complementary to EAPruned. 我々はまた、DTWおよびCDTWの場合、下境界はEAPrunedと相補的であることを示した。 0.71
The rest of this paper is organised as follows. 本論文の残りは以下のとおり整理される。 0.74
The section 2 presents the background on ensemble classifiers that lead us to consider a given set of elastic distances. セクション2はアンサンブル分類器の背景を示し、それによって与えられた弾性距離の集合を考える。 0.72
It then presents these elastic distances and highlights their common structure. そして、これらの弾性距離を示し、それらの共通構造を強調する。 0.60
The section 3 presents EAPruned itself. セクション3はEAPruned自身を提示する。 0.69
We then present our experimentation results in the section 4, and conclude section 5. 次に、実験結果をセクション4で発表し、セクション5で結論付けます。 0.73
2 Background and Related Work In this paper, we only consider univariate time series, although our technique is applicable to multivariate series. 2 背景と関連作業 本論文では,本手法が多変量系列に適用可能であるが,一変時間系列のみを検討する。 0.77
Any mention of “series” or “times series” should be understood as “univariate time series”. シリーズ」や「時系列」のあらゆる言及は「一様時系列」と解釈されるべきである。 0.67
We usually denote series with the letters Q (for a query), C (for a candidate), S, T and U , and their length with the letter L (using subscript such as LS to disambiguate the lengths of different series). 通常は、Q の文字(クエリー)、C の文字(候補)、S の文字、T の文字、U の長さを L の文字で表す(LS のようなサブスクリプトを使って異なる列の長さを曖昧にする)。 0.71
Subscripts Ci are used to distinguish multiple candidates. サブスクリプト Ci は複数の候補を区別するために使用される。 0.54
The elements s1, s2, . 要素 s1, s2, . 0.93
. . sLS are the elements of the series S = (s1, s2, . . . sLS は系列 S = (s1, s2, .) の要素である。 0.85
. . sLS ). The element si is understood to be the i-th element of S, with 1 ≤ i ≤ LS. . . sLS)。 元 si は 1 ≤ i ≤ LS を持つ S の i 番目の元であると理解される。
訳抜け防止モード: . . sLS)。 si 要素が理解される 1 ≤ i ≤ LS を持つ S の i 番目の元となる。
0.81
2.1 The Recent History of Ensemble Classifiers 2.1 アンサンブル分類器の歴史 0.78
Ensemble classifiers have recently revolutionized time series classification. エンサンブル分類器は最近時系列分類に革命をもたらした。 0.51
The “Elastic Ensemble” (“EE”, see [14]), introduced in 2015, was one of the first classifiers to be consistently more accurate than NN1-DTW over a wide variety of tasks. 2015年に導入された "Elastic Ensemble"("EE"参照[14])は、さまざまなタスクにおいてNN1-DTWよりも一貫して正確である最初の分類器の1つです。 0.81
EE combines eleven NN1 classifiers based on eleven elastic distances (presented sections 2.3 and 2.5). EEは11の弾性距離(現在のセクション2.3と2.5)に基づいてNN1分類器を結合する。 0.58
Most elastic distances have parameters. ほとんどの弾性距離はパラメータを持つ。 0.69
At train time, EE fine tunes them using cross validation. 列車の時、EEはクロスバリデーションを使ってそれらを微調整します。 0.42
At test time, the query’s class is determined through a majority vote between the component classifiers. テスト時には、クエリのクラスはコンポーネントの分類子間の多数決によって決定される。 0.84
“Proximity Forest” (“PF”, see [16]) uses the same set of distance measures as EE, but deploys them for nearest neighbor tests between a single exemplar of each class within an ensemble of random trees. プロキシミティフォレスト(「PF」)は、EEと同じ距離測度を使用していますが、ランダムな木のアンサンブル内の各クラスの単一の例間で、最も近い隣り合うテストのためにそれらを展開します。
訳抜け防止モード: プロキシミティフォレスト」(「PF」参照[16])はEEと同じ距離測度を使用します。 しかし、ランダムツリーのアンサンブル内の各クラスの単一の例間の最も近い隣り合ったテストのためにそれらを展開します。
0.81
Both EE and PF solely work in the time domain, leading to poor accuracies when discriminant features are in other domains. EEとPFはどちらもタイムドメインでのみ動作するため、差別的特徴が他のドメインにある場合の精度は低下します。 0.65
This was addressed by their respective evolution into “HIVE-COTE” (“HC”, see [15]) and “TSCHIEF” (see [24]), combining more classifiers working in different domains (interval, shapelets, dictionary and spectral, see [15] for an overview). これはそれぞれの進化によって"HIVE-COTE"(HC、[15]参照)と"TSCHIEF"([24]参照)に対処され、異なるドメインで作業するより多くの分類器(インターバル、シェープレット、辞書、スペクトル、概要は[15]参照)を組み合わせたものだ。 0.78
While EE provided a qualitative jump in accuracy, it did so at the cost of a quantitative jump in computation time. eeは精度を定性的に向上させたが、計算時間の定量的なジャンプを犠牲にしていた。 0.65
For example, [29] reports 17 days to learn and classify the UCR archive’s ElectricDevice benchmark ([4]). 例えば、[29] は ucr archive の electricdevice benchmark ([4]) を学習し分類するのに 17 日かかると報告している。 0.79
Indeed, in their simplest forms and given series of length L, elastic distances have O(L2) space and time complexities. 実際、それらの最も単純な形式と与えられた長さ L の列において、弾性距離は O(L2) 空間と時間複雑性を持つ。
訳抜け防止モード: 実際、それらの最も単純な形式と与えられた長さ L, 弾性距離は O(L2 ) 空間と時間複雑性を持つ。
0.80
This is only compounded by an extensive search of the best possible parametrization through leave-one-out cross validation. これは、休暇ワンアウトクロスバリデーションを通じて可能な限り最高のパラメータ化の広範な検索によってのみ合成されます。 0.45
For a training set of N times series, searching among M parameters (M = 100 for EE), EE has a training time complexity in O(M.N 2.L2). N 時間系列のトレーニングセットでは、M パラメータ (M = 100 for EE) を探索するが、EE は O(M.N 2.L2) においてトレーニング時間の複雑さを持つ。 0.77
HIVE-COTE not only expands on EE, it actually embeds it as a component – or did. HIVE-COTEはEE上に拡張するだけでなく、実際にコンポーネントとして組み込む。 0.75
Recently, EE was dropped from HIVE-COTE (see [1]) because of its computational cost. 近年、計算コストのため、EEはHIVE-COTE([1]参照)から姿を消した。 0.66
Doing so caused an average drop of 0.6% in accuracy, and beyond a 5% drop on some datasets (tested on the UCR archive). これにより、精度は平均0.6%低下し、一部のデータセット(UCRアーカイブでテストされている)では5%低下した。 0.74
The authors considered that it was a fair price to pay for the resulting speedup (the authors only report that the new version is “significantly faster”). 著者は、その結果のスピードアップを支払うのは公正な価格であると考えました(著者は、新しいバージョンが「大幅に高速」であるとのみ報告しています)。 0.69
2.2 Early Abandoning and Pruning 2.2 早期放棄と切開 0.74
A double buffer technique [18] overcomes the space complexity, but the time complexity remains challenging. ダブルバッファ手法[18]は空間の複雑さを克服するが、時間的複雑さは依然として困難である。 0.67
Luckily, nearest neighbor search opens the door to early abandoning strategies. 幸運にも、最も近い隣人の捜索は早期に戦略を放棄する扉を開く。 0.60
When searching for the nearest neighbor of a query Q under a distance D, we sequentially check Q against each candidate Ci from a database. 距離DでクエリQの最も近い近傍を探索すると、データベースから各候補Ciに対して順次Qをチェックする。
訳抜け防止モード: 距離Dの下でクエリQの最も近い隣人を探すとき データベースから各候補の Ci に対して Q を順次チェックします。
0.82
Let S be the current nearest neighbor of Q. S を Q の現在の最も近い近傍とする。 0.81
Early abandoning encompasses a set of techniques that abort before actually completing the computation D(Q, Ci) if they can determine that D(Q, Ci) > D(Q, S) (i.e. 初期の放棄は、D(Q, Ci) > D(Q, S) を決定できるならば、実際に計算を完了する前に中止した一連のテクニックを含んでいる(つまり、D(Q, Ci)。 0.76
Ci cannot be the nearest neighbor). Ciは最も近い隣人ではありません)。 0.69
The two main kinds of early abandoning techniques are “lower bounding” and “computation abandoning”. 早期放棄技術の2つの主な種類は、「より低い境界」と「計算放棄」です。 0.74
2 2 0.85
英語(論文から抽出)日本語訳スコア
Lower bounding employs lower bounds lb such that lb(Q, Ci) ≤ D(Q, Ci). 下界は lb(Q, Ci) ≤ D(Q, Ci) となるような下界 lb を用いる。 0.71
It follows that if lb(Q, Ci) > D(Q, S) then D(Q, Ci) > D(Q, S), i.e. lb(Q, Ci) > D(Q, S) ならば、D(Q, Ci) > D(Q, S) となる。
訳抜け防止モード: lb(Q, Ci ) > D(Q, S ) ならば D(Q, S ) である。 Ci ) > D(Q、S)、すなわち。
0.83
we do not need to compute D(Q, Ci) if the lower bound is already above D(Q, S). 下限が既に D(Q, S) 以上であれば、D(Q, Ci) を計算する必要はありません。 0.79
This allows to discard Ci even before starting to compute D(Q, Ci). これにより、D(Q, Ci)の計算を始める前にCiを破棄することができる。 0.67
To be effective, lower bounds must be computationally cheap while remaining as “tight” as possible, i.e. 有効にするためには、低い境界は可能な限り「タイト」として残りながら計算的に安価でなければならない。 0.62
as close as possible to the actual result of the distance. 距離の実際の結果に 可能な限り近づきます 0.65
Lower bounding is shown to significantly speedup classification [10, 29] and similarity search [19]. 下限は分類 [10, 29] と類似性検索 [19] の大幅な高速化を示す。 0.87
Lower bounds have mainly been developed for DTW and CDTW, the most common being LB Kim and LB Keogh [23, 10]. 下限は主にDTWとCDTWのために開発され、最も一般的なのはLB KimとLB Keogh [23, 10]である。 0.80
They also exist for other elastic distances [29], and remain an active field of research. それらは他の弾性距離 [29] においても存在し、活発な研究分野である。 0.75
The second way to early abandon is to stop the computation of D(Q, Ci) itself. 早期に放棄する第2の方法は、D(Q, Ci) 自体の計算を止めることである。 0.78
We can give an intuition of how this works without diving into the details yet. 詳細に目を通すことなく、この方法の直感を与えることができます。 0.54
While computing D(Q, Ci), a minimum value v ≤ D(Q, Ci) is maintained. D(Q, Ci)を演算する際、最小値 v ≤ D(Q, Ci) が維持される。 0.80
The value v usually starts at 0 and increases toward D(Q, Ci). 値 v は通常 0 から始まり、D(Q, Ci) に向かって増加する。 0.84
If (and as soon as) v > D(Q, S), then D(Q, Ci) > D(Q, S), allowing to abandon the computation. もし (そしてすぐに) v > D(Q, S) ならば、D(Q, Ci) > D(Q, S) となり、計算を放棄することができる。 0.83
Finally, recent progress has been made on the DTW distance. 最後に、DTW距離の最近の進歩が行われています。 0.74
PrunedDTW [25] computes DTW while avoiding computation of some alignments that cannot be on an optimal path [19], and was subsequently extended to incorporate early abandoning [26]. PrunedDTW [25] は、最適経路[19]に存在しないアライメントの計算を避けながらDTWを計算し、その後、早期放棄[26]を組み込むように拡張された。 0.72
2.3 Elastic Distances with a Common Structure 2.3 共通構造を持つ弾性距離 0.85
EE uses eleven elastic distances. EEは11の弾性距離を使用する。 0.65
This section examines DTW, CDTW, WDTW, MSM, and TWE, the computations of which follow a similar pattern and can be sped up by a common strategy. このセクションでは、DTW、CDTW、WDTW、MSM、およびTWEについて検討します。
訳抜け防止モード: 本項ではDTW, CDTW, WDTW, MSMについて検討する。 そしてその計算方法であるTWE 同様のパターンに従えば 共通の戦略によって 追い上げられます
0.75
DDTW, DCTW and DWDTW are respectively DTW, CDTW and WDTW applied to the derivative of the series [11]. DDTW、DCTW、DWDTWはそれぞれ、シリーズ[11]の誘導体に適用されるDTW、CDTW、WDTWである。 0.75
We do not examine these variants in this paper, but we note that they automatically benefit from our strategy. この論文ではこれらの変種について検討していませんが、私たちの戦略から自動的に恩恵を受けることに留意します。
訳抜け防止モード: 本論文ではこれらの変種について検討しない。 しかし 戦略によって 自動的に利益が得られます
0.65
The two remaining distances, LCSS and SQED, are examined in section 2.5. LCSSとSQEDの2つの残りの距離は、セクション2.5で調べられます。 0.66
All the distances compute an alignment cost between two series. すべての距離は2シリーズ間のアライメントコストを計算する。 0.77
For most distances, this alignment cost depends on a cost “cost” function used between elements of the series. ほとんどの距離において、このアライメントコストは、シリーズの要素間で使用されるコスト “コスト” 関数に依存する。 0.75
The squared Euclidean distance is often used, and this is the cost we use in all our implementations. 正方形のユークリッド距離はしばしば使用され、これはすべての実装で使用されているコストです。 0.69
However, other cost functions are possible, such as the L1 norm. しかし、L1ノルムのような他のコスト関数も可能である。 0.73
2.3.1 Dynamic Time Warping 2.3.1ダイナミックタイムワーピング 0.60
The Dynamic Time Warping (DTW) distance was first introduced in 1971 by Sakoe and Chiba as a speech recognition tool [21, 20]. 1971年, 佐古江と千葉が音声認識ツール [21, 20] として, 動的時間ワープ(DTW)距離を導入した。 0.72
Compared to the classic Euclidean distance, DTW handles distortion and disparate lengths. 古典的なユークリッド距離と比較して、DTWは歪みと異なる長さを扱う。 0.63
Intuitively, DTW “aligns” two series by aligning their points. 直感的には、DTWは2つのシリーズをポイントを並べて“調整”する。 0.58
The end points must be aligned, and no point-alignment shall cross each other. 終点が整列されなければならず、ポイントアライメントは互いに交差してはならない。 0.69
Figure 1a illustrates how DTW aligns two series S and T where the cost function is the square Euclidean distance. 図1aは、コスト関数が平方ユークリッド距離である2つの級数 S と T をDTWが整列する様子を描いている。 0.66
DTW compute the minimal (optimal) alignment cost. DTWは最小(最適)アライメントコストを計算する。 0.85
Note that several optimal alignments with the same cost may exist. 同じコストで複数の最適アライメントが存在する可能性があることに注意。 0.71
To compute the optimal alignment cost, DTW computes an optimal alignment which is represented by an optimal “warping path” in the (L+1×L+1) DTW cost matrix MDTW. 最適アライメントコストを計算するため、DTWは(L+1×L+1)DTWコスト行列MDTWにおいて最適な「ウォーピングパス」で表される最適アライメントを算出する。 0.81
Its cells represent the cumulative optimal cost of aligning the series according to the Equations 1d. そのセルは、方程式1dに従って系列を整列する累積最適コストを表す。 0.77
Equations 1a to 1c describe the boundary conditions. 方程式 1a から 1c は境界条件を記述する。 0.67
Figure 1b shows the cost matrix for two series S and T along with the optimal warping path. 図1bは、2つの級数 S と T のコスト行列と最適なワープ経路を示している。 0.71
DTW(S, T ) = MDTW(LS, LT ). DTW(S, T) = MDTW(LS, LT)。 0.76
MDTW(0, 0) = 0 MDTW(i, 0) = +∞ MDTW(0, j) = +∞ MDTW(0, 0) = 0 MDTW(i, 0) = +∞ MDTW(0, j) = +∞ 0.92
MDTW(i, j) = cost(si, tj) + min MDTW(i, j) = cost(si, tj) + min 0.85
MDTW(i − 1, j − 1) シュMDTW(i − 1, j − 1) 0.85
MDTW(i − 1, j) MDTW(i, j − 1) MDTW(i − 1, j) MDTW(i, j − 1) 0.85
3 (1a) (1b) 3 (1a) (1b) 0.91
(1c) (1d) (1c) (1d) 0.94
英語(論文から抽出)日本語訳スコア
(a) DTW alignements with costs. (a) DTWはコストと整合する。 0.72
(b) DTW cost matrix with warping path. (b) 反りのパスのDTWの費用マトリックス。 0.83
Figure 1: MDTW(S,T ) with warping path and alignments for S = (3, 1, 4, 4, 1, 1) and T = (1, 3, 2, 1, 2, 2). 図1: S = (3, 1, 4, 4, 1, 1) と T = (1, 3, 2, 1, 2, 2) に対する反動経路とアライメントを持つMTTW(S,T)。 0.76
We have DTW(S, T ) = MDTW(S,T )(6, 6) = 9. DTW(S, T ) = MDTW(S, T )(6, 6) = 9 である。 0.82
Taking the diagonal means a new alignment between two new points. 対角線を取ることは、2つの新しい点の間の新しいアライメントを意味する。 0.59
Going down or right means that one point is reused. ダウンするか正しいかは、あるポイントが再利用されることを意味します。 0.46
For example, in Figure 1b, the fifth point of S is aligned with the third, fourth and fifth point of T . 例えば、図1bでは、S の5番目の点は T の第3、第4、第5の点と一致している。 0.63
This can also be visualise on Figure 1a, with three dotted lines reaching the fifth point of S. An alignment requires the end points to be aligned. これは図1aでも可視化でき、3つの点線がSの5番目の点に達する。
訳抜け防止モード: これは図1aでも可視化できます。 Sの5番目の点に達する3つの点線。アライメントには、終点をアライメントする必要があります。
0.59
This means that a valid warping path starts from the top left cell and reaches the bottom right cell. これは、有効なワーピングパスが左上セルから始まり、右下セルに到達することを意味します。 0.72
One approach to speeding up elastic distances is through approximation, e.g. 弾性距離を高速化する1つのアプローチは近似(例えば近似)である。 0.64
FastDTW (see [22], and [31] for a counterpoint). FastDTW (カウンターポイントは [22] と [31] を参照)。 0.70
Our approach computes exact DTW (and other distances), which is useful when approximation is not desirable. 提案手法は,近似が望ましくない場合に有用であるDTW(および他の距離)を正確に計算する。 0.71
Comparing approximated approaches with exact approaches is left for further research. 正確なアプローチで近似したアプローチを比較することは、さらなる研究に欠かせない。 0.60
In the following, we will use notions of direction (left, right, previous, up, top, diagonal, etc...). 以下では、方向の概念(左、右、前、前、上、上、対角など)を使用する。 0.60
They should be understood in the context of a matrix similar to the one depicted Figure 1b. これらは図1bに示すような行列の文脈で理解されるべきである。 0.71
A diagonal always mean a new alignment between two new points. 対角線は常に2つの新しい点の間の新しいアライメントを意味する。 0.61
We call such an alignment a “canonical alignment”. このようなアライメントを“カノニカルアライメント”と呼んでいる。 0.64
Going down or right (or with a top or left dependency) represents an “alternate alignment”. 上下に進む(または上または左の依存関係を持つ)ことは、「交互アライメント」を表します。 0.67
Alternate alignments happen either because the canonical alignment is too expensive, or because the series have differing lengths. 交互なアライメントは、正準的なアライメントが高価すぎるか、またはシリーズの長さが異なるため起こる。 0.65
Note that the alternate cases are always symmetric. 交互のケースは常に対称である。 0.69
This is reflected in the commutative nature of the distances regarding their series arguments (e.g. これは、それらの級数引数(例えば)に関する距離の可換的性質に反映される。 0.64
DTW(S, T ) = DTW(T, S)). DTW(S, T) = DTW(T, S))。 0.80
2.3.2 Constrained DTW 2.3.2 制約DTW 0.51
In CDTW, the “constrained” variant of DTW, the warping path is restricted to a subarea of the matrix. CDTWでは、DTWの「制約された」変種である反動経路は行列の部分領域に制限される。 0.77
Different constraints exist [20, 8]. 異なる制約が存在します [20, 8]。 0.82
We focus on the popular Sakoe-Chiba band [20], also known as “Warping Window” (or “window” for short). われわれは、人気のSakae-Chibaバンド[20]、別名“Warping Window”(略して“Window”)に焦点を当てている。 0.76
This constraint can also be applied to other distances such as ERP and LCSS (section 2.3.4 and 2.5.2). この制約はERPやLCSS(2.3.4および2.5.2)のような他の距離にも適用できる。 0.63
The window is a parameter w controlling how far the warping path can deviate from the diagonal. ウィンドウは、反動パスが対角線からどの程度逸脱できるかを制御するパラメータ w です。 0.81
Given a matrix M , a line index 1 ≤ l ≤ L and a column index 1 ≤ c ≤ L, we have |l − c| ≤ w. Figure 2a illustrates the state of MCDTW(S, T ) for a window of 1. 行列 M と直線指数 1 ≤ l ≤ L と列指数 1 ≤ c ≤ L が与えられたとき、|l − c| ≤ w が得られる。
訳抜け防止モード: 行列 M が与えられたとき、直線指数 1 ≤ l ≤ L が与えられる。 カラムインデックス 1 ≤ c ≤ L は |l − c| ≤ w である。 T) は 1 のウィンドウである。
0.67
Notice how the path can only step away one cell from each side of the diagonal. 経路が斜めの両側から1つの細胞だけを引き離すことができることに注意してください。 0.69
The resulting cost is 11, which is greater than the cost of 9 obtained earlier by unconstrained DTW (see Figure 1). 結果として得られるコストは11であり、制約のないDTWで得られる9のコストよりも大きい(図1参照)。 0.81
Due to the window constraint, the cost of ウィンドウの制約のため、コストがかかります。 0.72
4 123456123440111011Se ries SSeries TAlignments05114413S =T =13212205012345601234 56044591011485567135 91491022691813132210 778922148789 4 123456123440111111Se ries TAlignments05114413S = T = 13212205012345601234 54459104855671359149 10226918132277892214 8789 0.49
英語(論文から抽出)日本語訳スコア
(a) CDTW cost matrix with w = 1 for S and T of equal length (a) 等しい長さの S と T に対して w = 1 の CDTW コスト行列 0.91
(b) CDTW cost matrix with w = 1 for S and U of disparate lengths. (b) 異なる長さの S と U に対して w = 1 の CDTW コスト行列。 0.79
Figure 2: Example of CDTW cost matrices with a window of 1. 図2: ウィンドウが1のCDTWコスト行列の例。 0.66
In the second case, the window it too small to allow an alignment between the last two points at (6, 8). 第2のケースでは、ウィンドウは小さすぎて、最後の2点 (6, 8) のアライメントができない。
訳抜け防止モード: 2つ目のケースでは 窓が小さすぎるので 最後の2点を(6、8)でアライメントできるようにする。
0.75
CDTW is always greater than or equal to DTW’s. CDTWは常にDTWよりも大きいか等しいです。 0.78
Figure 2b shows what happens with a window too short for series of disparate lengths. 図2bは、一連の異なる長さのウィンドウが短すぎる場合に起こることを示しています。
訳抜け防止モード: 図2bが示すのは 異なる長さの連続には 窓が短すぎます
0.81
The last two points can’t be aligned. 最後の2つのポイントは整列できません。 0.82
Given two series S and T of respective lengths LS and LT , an alignment is possible with a window w ≥ |LS − LT|. 各長さ LS と LT の 2 つの級数 S と T を与えられると、ウィンドウ w × |LS − LT| でアライメントが可能となる。 0.81
A window of 0 is akin to the squared Euclidean distance, while a window of L is equivalent to DTW (no constraint). 0 のウィンドウは正方形のユークリッド距離に似ているが、L のウィンドウは DTW (制約なし) と等価である。 0.76
With a correctly set window, NN1-CDTW can achieve better accuracy than NN1-DTW by preventing spurious alignments. 正しく設定されたウィンドウでは、NN1-CDTWはスプリアスアライメントを防止し、NN1-DTWよりも精度が高い。 0.54
It is also faster to compute than DTW, as cells beyond the window are ignored. ウィンドウの向こうのセルは無視されるため、DTWよりも高速に計算できます。 0.77
However, the window parameter must be set. しかし、ウィンドウパラメータを設定する必要がある。 0.78
A technique exploiting several properties of CDTW (e.g. CDTWのいくつかの特性を利用する技術(例) 0.72
increasing the window can only lead to a smaller or equal cost) has been developed to learn this parameter faster [28]. ウィンドウを増やすことは、より小さいか等しいコストにつながることができます)このパラメータをより速く学ぶために開発されました[28]。 0.76
2.3.3 Weighted DTW 2.3.3 重量DTW 0.55
The Weighted Dynamic Time Warping (WDTW, see [9]) distance is another variant of DTW. Weighted Dynamic Time Warping (WDTW, see [9]) 距離はDTWの別の変種である。 0.82
If CDTW can be seen as a hard constraint on the warping paths, WDTW can be seen as a soft one. CDTWが反動経路のハード制約として見られるならば、WDTWはソフト制約として見ることができる。 0.71
The cells (l, c) of the MW DT W cost matrix are weighted according to their distance to the diagonal d = |l − c|. MW DT W コスト行列のセル (l, c) は、対角 d = |l − c| への距離に応じて重み付けされる。 0.73
The larger the weight, the more the cell is penalized and unlikely to be part of an optimal path. 重量が大きいほど、細胞は罰せられやすくなり、最適な経路の一部になる可能性は低い。 0.65
The weight is computed according to the Equation 2, where g controls the penalization. 重みは式2に従って計算され、gはペナリゼーションを制御する。 0.67
Its optimal range is 0.01 – 0.6 [9]. 最適範囲は 0.01 - 0.6 [9] である。 0.74
w(d) = 1 1 + exp−g×(d−L/2) w(d) = 1 1 + exp−g×(d−L/2) 0.78
(2) 2.3.4 Edit Distance with Real Penalty (2) 2.3.4 実刑で距離を編集する 0.72
The Edit distance with Real Penalty (ERP, see [3]) is actually a metric fulfilling the triangular inequality. Real Penalty (ERP, see [3]) による編集距離は、実際には三角不等式を満たす計量である。 0.82
It takes as parameters a warping window (see CDTW section 2.3.2) and a “gap value” g. Intuitively, ERP aligns the points in the case of canonical alignments, and inserts a “gap” at a cost based on g in the case of パラメータとしてワープウィンドウ(CDTW セクション 2.3.2) と "ギャップ値" 例えば直感的には、ERP は正準アライメントの場合のポイントをアライメントし、g の場合の g に基づいたコストで "ギャップ" を挿入する。 0.84
5 05114413S =T =13212205012345601234 56044485591491818910 11101105114413S =U =13212244050123456780 12345604448559149181 891011101120 5 05114413S = T = 13212205012340123454 44855914918189101110 5114413S = U = 13212244050123478012 34544484918910111011 20 0.49
英語(論文から抽出)日本語訳スコア
alternate alignments. 交互にアライメントする 0.53
The authors suggest a gap value of 0, but EE still fine tunes it, along with the window size. 著者らは0のギャップ値を提案するが、EEはウィンドウサイズとともにそれを微調整している。 0.61
ERP is describe by the Equations 3. ERP は Equations 3 で説明されます。 0.89
Again, the cost function usually is the squared Euclidean distance, but other norms are allowed. 繰り返すが、コスト関数は通常2乗ユークリッド距離であるが、他のノルムは許される。 0.65
Compared to DTW, the borders are computed (equations 3b and 3c) rather than being set to +∞. dtwと比較すると、境界は +∞ ではなく 3b と 3c で計算される。 0.75
The cost function is now specialized per argument of the min{ function. コスト関数は min{ 関数の引数ごとに専門化されています。 0.80
MERP(0, 0) = 0 MERP(i, 0) = MERP(i − 1, 0) + cost(si, g) MERP(0, j) = MERP(0, j − 1) + cost(g, tj) MERP(0, 0) = 0 MERP(i, 0) = MERP(i − 1, 0) + cost(si, g) MERP(0, j) = MERP(0, j − 1) + cost(g, tj) 0.85
MERP(i − 1, j − 1) + cost(si, tj) シュメRP(i − 1, j − 1) + cost(si, tj) 0.79
MERP(i − 1, j) + cost(si, g) MERP(i, j − 1) + cost(ti, g) MERP(i − 1, j) + cost(si, g) MERP(i, j − 1) + cost(ti, g) 0.85
MERP(i, j) = min MERP(i, j) = min 0.85
(3a) (3b) (3c) (3a) (3b) (3c) 0.94
(3d) 2.3.5 Move-Split-Merge (3d) 2.3.5 Move-Split-Merge 0.63
Move-Split-Merge (MSM, see [27]) is another metric developed to overcome shortcomings in other elastic distances. Move-Split-Merge (MSM, see [27]) は、他の弾性距離の欠点を克服するために開発された別の計量である。 0.61
Compared to ERP, it is robust to translation1. ERPと比較して、翻訳1に堅牢です。 0.81
The authors showed that MSM is competitive against DTW, CDTW and ERP for NN1 classification. 著者らは,MSMがNN1分類においてDTW,CDTW,ERPと競合していることを示した。 0.59
MSM (Equations 5) defined its own cost function Cc (Equation 4) used to compute the cost of the alternate alignments. MSM (Equation 5) は、自身のコスト関数 Cc (Equation 4) を定義し、代替アライメントのコストを計算した。 0.84
It takes as argument the new point (np) of the alternate alignment, and the two previously considered points (x and y) of each series. これは、交互アライメントの新しい点 (np) と、各級数の以前に考慮された2つの点 (x, y) を議論するものである。 0.71
C also takes a real number c as a constant penalty. C はまた、実数 c を一定のペナルティとして取る。 0.78
This penalty is the only parameter of MSM (and is fine tuned by EE). このペナルティはMSMの唯一のパラメータです(EEによって微調整されています)。 0.70
Cc(np, x, y) = Cc(np, x, y) = 0.85
c + min otherwise c + min そうでなければ 0.59
If x ≤ np ≤ y or x ≥ np ≥ y x ≤ np ≤ y あるいは x ≥ np ≥ y であれば 0.95
(cid:40)|np − x| (cid:40)|np − x| 0.75
|np − y| c |np − y| オーク 0.59
MMSM(0, 0) = 0 MMSM(i, 0) = +∞ MMSM(0, j) = +∞ MMSM(0, 0) = 0 MMSM(i, 0) = +∞ MMSM(0, j) = +∞ 0.92
MMSM(i, j) = min MMSM(i, j) = min 0.85
MMSM(i − 1, j − 1) + |si − tj| シュMMSM(i − 1, j − 1) + |si − tj| 0.94
MMSM(i − 1, j) + C(si, si−1, tj) MMSM(i, j − 1) + C(tj, si, tj−1) MMSM(i − 1, j) + C(si, si−1, tj) MMSM(i, j − 1) + C(tj, si, tj−1) 0.95
(4) (5a) (5b) (4) (5a) (5b) 0.91
(5c) (5d) 2.3.6 Time Warp Edit Distance (5c) (5d) 2.3.6 Time Warp Edit Distance 0.86
The Time Warp Edit distance (TWE, see [17]) is motivated by the idea that timestamps (i.e. Time Warp Edit distance (TWE, see [17])はタイムスタンプ(タイムスタンプ)の概念に動機づけられている。 0.83
when a value is recorded) should be taken into account. 値が記録されるとき)考慮されるべきです。 0.71
This is important for series with non-uniform sampling rates. これは、不均一なサンプリングレートを持つシリーズにとって重要です。 0.52
Note that our current implementation does not use timestamps, also assuming a constant sampling rate. 現在の実装ではタイムスタンプは使用せず,一定のサンプリング率を前提としています。 0.63
The i-th timestamp of a series S is denoted by τs,i. 級数 S の i 番目のタイムスタンプは τs,i で表される。 0.71
TWE (Equations 7) defines its cost functions (Equations 6) with two parameters. TWE (Equations 7) はコスト関数 (Equations 6) を2つのパラメータで定義する。 0.90
The first one, ν, is a “stiffness” parameter weighting the timestamp contribution. 第1のνは、タイムスタンプの寄与を重み付けする“剛性”パラメータである。 0.77
A parameter of ν = 0 is similar to DTW. ν = 0 のパラメータは DTW と似ている。 0.86
The second one, λ, is a constant penalty added to the cost of the alternate alignments (“delete” in TWE 2つめのλは、代替アライメントのコストに追加される一定のペナルティである(twe における "delete" )。 0.73
1In ERP, the gap cost is given by cost(si, g). 1ERPでは、ギャップコストはコスト(si,g)によって与えられる。 0.72
If S is translated, the gap cost also changes while the canonical alignment cost Sが翻訳されると、ギャップコストも変化し、正準アライメントコストも変化します。 0.65
remains unchanged, making ERP translation-sensitiv e. ERP翻訳を敏感にします。 0.57
6 6 0.85
英語(論文から抽出)日本語訳スコア
terminology — deleteA for the lines, deleteB for the columns). 用語 — 行のdeleteA、列のdeleteB)。 0.60
The cost of the alternate case is the cost between the two current points, plus their timestamp difference, plus the λ penalty. オルタナティブケースのコストは、2つの現在のポイント間のコストと、それらのタイムスタンプ差、およびλペナルティである。 0.71
The canonical alignment (“match”) cost is the sum of the cost between the two current and the two previous points, plus a weighted contribution of their respective timestamps differences. 正準アライメントコスト(Match)は、2つの電流と2つの前の点の間のコストの合計であり、それぞれのタイムスタンプの違いの重み付けによる寄与である。 0.73
match: γM = cost(si, tj) + cost(si−1, tj−1) + ν(|τs,i − τt,j| + |τs,i−1 − τt,j−1|) deleteA: γA = cost(si, si−1) + ν|τs,i − τs,i−1| + λ deleteB: γB = cost(tj, tj−1) + ν|τt,j − τt,j−1| + λ match: γm = cost(si, tj) + cost(si−1, tj−1) + ν(|τs,i − τt,j| + |τs,i−1 − τt,j−1|) deletea: γa = cost(si, si−1) + ν|τs,i − τs,i−1| + λ deleteb: γb = cost(tj, tj−1) + ν|τt,j − τt,j−1| + λ 0.79
MTWE(0, 0) = 0 MTWE(i, 0) = +∞ MTWE(0, j) = +∞ MTWE(0, 0) = 0 MTWE(i, 0) = +∞ MTWE(0, j) = +∞ 0.92
MTWE(i, j) = min MTWE(i, j) = min 0.85
MTWE(i − 1, j − 1) + γM シュMTWE(i − 1, j − 1) + γM 0.90
MTWE(i − 1, j) + γA MTWE(i, j − 1) + γB MTWE(i − 1, j) + γA MTWE(i, j − 1) + γB 0.93
(6) (7a) (7b) (6) (7a) (7b) 0.91
(7c) (7d) 2.4 A Common Structure (7c) (7d) 2.4 共通構造 0.94
These six distances share a common structure, described by Equations 8. これら6つの距離は、方程式8によって記述された共通の構造を共有する。 0.54
For a distance D, these equations assign a value to every cell of a cost matrix MD. 距離 D に対して、これらの方程式はコスト行列 MD の各セルに値を割り当てる。 0.84
Given a series S “along the rows” and a series T “along the columns”, the 0-indexed matrix MD has dimension (LS + 1)× (LT + 1). 列の列」と「列の列」からなる級数 S が与えられたとき、0 進行列 MD は次元 (LS + 1)× (LT + 1) を持つ。 0.77
MD(i, j) is the cumulative cost of aligning the first i points of S with the first j points of T . MD(i, j) は、S の最初の i 点と T の最初の j 点を整列させる累積コストである。 0.81
It follows that the last cell at (LS + 1, LT + 1) holds the actual cost computed by D. 最後のセル(LS + 1, LT + 1)は、Dによって計算される実際のコストを保持する。 0.85
The first three equations describe the border initialization of the matrix. 最初の3つの方程式は行列の境界初期化を記述する。 0.72
Equation 8a initialises the top left corner with 0. 式8aは左上隅を0で初期化する。 0.73
Equation 8b initialises the left vertical border, and Equation 8c initialises the top horizontal border. 方程式8bは左垂直境界を初期化し、方程式8cは上部水平境界を初期化する。 0.66
The borders must be monotonously increasing, e.g. 境界は単調に増加しなければならない。 0.71
MD(i, 0) ≤ MD(i + 1, 0). MD(i, 0) ≤ MD(i + 1, 0) である。 0.89
Among the presented distances, only ERP has computed borders. 提示された距離のうち、ERPだけが境界を計算した。 0.59
The borders of all the others are initialised to +∞. 他のすべての境界は +∞ に初期化される。 0.79
The last equation (8d) is the main one. 最後の方程式(8d)は主な方程式です。 0.67
A cell is computed by taking the minimum of three different alignment costs plus the cost of their respective dependency. セルは、3つの異なるアライメントコストとそれぞれの依存関係のコストを最小にすることで計算される。 0.84
The canonical alignment (“Canonical”) cost depends on the top left diagonal cell (“diag” dependency). 正準アライメント("canonical")コストは左上対角セル("diag"依存性)に依存する。 0.67
The vertical alternate alignment (“AlternateLine”) cost depends on the above cell (“top” dependency). 垂直の交互アライメント(「AlternateLine」)コストは、上記のセル(「トップ」依存性)に依存します。 0.77
The horizontal alternate alignment (“AlternateColumn”) cost depends on the left cell (“left” dependency). 水平方向の代替アライメント("alternatecolumn" ;)のコストは、左セル("left"依存性)に依存する。 0.77
This process amounts to computing an optimal alignment (with minimum cost) represented by an optimal warping path in the cost matrix. このプロセスは、コストマトリックスにおける最適なワーピングパスで表される最適なアライメント(最小コスト)の計算に相当します。 0.87
For example, in Figure 1b, the cell (4, 2) is part of the optimal path, meaning that the fourth value of S is aligned with the second value of T . 例えば、図1bでは、セル(4, 2)は最適経路の一部であり、Sの4番目の値はTの2番目の値と一致している。 0.79
MD(0, 0) = 0 MD(i, 0) = InitVBorder MD(0, j) = InitHBorder MD(0, 0) = 0 MD(i, 0) = InitVBorder MD(0, j) = InitHBorder 0.85
such that MD(i, 0) ≤ MD(i + 1, 0) such that MD(0, i) ≤ MD(0, i + 1) MD(i, 0) ≤ MD(i + 1, 0) を MD(0, i) ≤ MD(0, i + 1) とする。 0.83
MD(i, j) = min MD(i, j) = min 0.85
MD(i − 1, j − 1) + Canonical MD(i − 1, j − 1) + Canonical 0.77
MD(i − 1, j) + AlternateLine MD(i, j − 1) + AlternateColumn MD(i − 1, j) + AlternateLine MD(i, j − 1) + AlternateColumn 0.85
(8a) (8b) (8c) (8a) (8b) (8c) 0.94
(8d) This generic structure guarantees the following properties: • An optimal path (with minimum cost) is computed. (8d) この一般的な構造は以下の性質を保証する: • 最適経路(最小コスト)が計算される。 0.89
7 7 0.85
英語(論文から抽出)日本語訳スコア
• Series extremities are aligned with each other ((1, 1) and (LS, LT )). •シリーズ四肢は互いに整列します((1、1)および(LS、LT))。 0.73
• The path is continuous and monotonous, i.e. • 経路は連続的で単調である。 0.68
for two of its consecutive cells (i1, j1) (cid:54)= (i2, j2), we have 2つの連続した細胞 (i1, j1) (cid:54)= (i2, j2) 0.82
i1 ≤ i2 ≤ i1 + 1 and j1 ≤ j2 ≤ j1 + 1. i1 ≤ i2 ≤ i1 + 1 および j1 ≤ j2 ≤ j1 + 1 である。 0.79
This structure hints at a linear space complexity. この構造は線形空間の複雑さを示唆する。 0.80
All dependencies of a cell are satisfied either by the previous row (diag and top dependencies), or by the previously computed cell on the same row (left dependency) case. セルのすべての依存関係は、前の行(ダイアログとトップの依存関係)または同じ行(左の依存関係)のケースで計算されたセルによって満足される。 0.77
It follows that if we proceed row by row, only two rows of the matrix are required at any time, achieving linear space complexity. 列を1行ずつ進めれば、行列の行はいつでも2行しか必要とせず、線形空間の複雑さが達成される。 0.75
We can further contain the memory footprint by using the shortest series as the “column series”, minimizing row length. 最短列を列列として使用し,行長を最小化することで,メモリフットプリントをさらに拡張することができる。 0.66
Algorithm 1 implements Equations 8 with the two rows technique. アルゴリズム1は方程式8を2列法で実装する。 0.71
We have two arrays representing the current row (curr) and the previous row (prev). 現在の行(curr)と前の行(prev)を表す2つの配列があります。 0.80
The arrays are swapped (line 6) at each iteration of the outer loop. 配列は外部ループの各イテレーションでスワップされます(6行目)。 0.76
The horizontal border is stored in the curr array (line 4), the swap operation putting it in prev so it can act as the previous row when computing the first one. 水平境界はcurr配列(ライン4)に格納され、スワップ操作はそれをprevに入れ、最初の行を計算するときに前の行として機能できるようにします。 0.78
The vertical border is gradually computed for each new row (line 7). 垂直境界は、新しい行ごとに徐々に計算される(ライン7)。 0.84
Finally, the inner loop (line 8) computes from left to right the value of the cells of the current row. 最後に、インナーループ(8行目)は、現在の行のセルの値を左から右に計算します。 0.80
Algorithm 1: Generic linear space complexity for a distance D. アルゴリズム1:距離Dに対する一般的な線形空間の複雑さ。 0.78
Input: the time series S and T Result: Cost D(S, T ) 入力:時系列SとTの結果:コストD(S,T) 0.75
1 co ← shortest series between S and T 2 li ← longest series between S and T 3 (prev, curr) ← arrays of length lco + 1; curr[0 ] ← 0 4 curr[1 — L] ← InitHBorder 5 for i ← 1 to Lli do swap(prev, curr) curr[0 ] ← InitVBorder for j ← 1 to Lco do 長さ lco + 1; curr[0 ] の配列 lco + 1; curr[0 ] は、長さ lco + 1; curr[0 ] の配列 0 4 curr[1 — L] の 1 から Lli do swap(prev, curr) curr[0 ] の InitHBorder 5 の 1 から Lli do swap(prev, curr) curr[0 ] の 1 から Lco do の InitVBorder である。 0.65
6 7 8 9 curr[j ] ← min 6 7 8 9 curr[j ] > min 0.81
10 return curr[lco] 10 return curr[lco] 0.85
prev[j-1 ] + Canonical ]prev[j-1 ] + canonical 0.80
prev[j ] + AlternateLine prev[j ] +AlternateLine 0.77
curr[j-1 ] + AlternateColumn curr[j-1 ] + AlternateColumn 0.92
Algorithm 2 builds upon Algorithm 1, adding support for a warping window w and the usual early abandoning technique with a cut-off value. アルゴリズム2はアルゴリズム1に基づいて構築され、ワーピングウィンドウwと通常、カットオフ値の早期放棄技術のサポートを追加している。 0.67
Hence, it is a suitable base for early abandoned CDTW and ERP. したがって、早期に放棄されたCDTWとERPに適した基盤である。 0.69
These two changes being orthogonal to each other, removing the window handling code yields the base for early abandoning all other distances presented until now. これら2つの変更は互いに直交しており、ウィンドウハンドリングコードを削除することで、これまで提示されていた他のすべての距離を早期に放棄する基盤が得られる。
訳抜け防止モード: この2つの変化は互いに直交している。 ウィンドウハンドリングコードを削除する これまでに提示された他のすべての距離を早期に放棄する基盤となる。
0.64
When dealing with a warping window w, we first check whether it permits an alignment or not (line 3) – see Figure 2b for a graphical representation of a window too small. ワーピングウィンドウwを扱う場合、まずアライメントを許可するかどうかを確認します(3行目) - ウィンドウのグラフィカル表現が小さすぎる場合は図2bを参照してください。 0.77
The horizontal border is only initialized up to w + 1 (line 6), and the inner loop is caped within the window around the diagonal (from jStart to jStop, lines 9, 10 and 13). 水平境界はw + 1(6行目)まで初期化され、内側ループは対角線(jStartからjStop、9行目、10行目と13行目)の周りのウィンドウ内でキャップされます。 0.81
The vertical border is only computed while the window covers the first column (line 11). 縦境界は、ウィンドウが第1の列(ライン11)を覆う間のみ計算される。 0.83
More interestingly, the arrays are now initialized to +∞. より興味深いことに、配列は +∞ に初期化される。 0.67
To understand why, let us consider the cell (2, 3) for MCDTW Figure 2a. その理由を理解するために、mcdtw 図 2a の細胞 (2, 3) を考えてみよう。 0.78
The cell (1, 3) is accessed to compute the AlternateLine case. セル (1, 3) にアクセスして AlternateLine のケースを計算します。 0.80
However, this cell is outside the window and should not contribute to the minimum. しかし、このセルはウィンドウの外にあり、最小限に貢献するべきではない。 0.68
By initializing the arrays to +∞, we implicitly set this cell, and all the upper right triangle outside of the window, to +∞. 配列を +∞ に初期化することで、このセルとウィンドウの外側にあるすべての右上の三角形を +∞ に設定します。 0.82
The lower triangle is implicitly set to +∞ line 11, after the window stops covering the first column. 下方三角形は、第1列をカバーするウィンドウが停止した後、+∞ライン11に暗黙的に設定される。 0.66
This explain why we assign to curr[jStart − 1] and not to curr[0 ]. これは、 curr[jStart − 1] に割り当て、 curr[0 ] に割り当てる理由を説明します。 0.77
Only the diagonal edge of the triangle is set to +∞, which is enough for the next cell’s AlternateColumn case to be properly ignored (e.g. 三角形の対角端のみが +∞ に設定され、これは次のセルの AlternateColumn の場合を適切に無視するのに十分である(例)。 0.83
in Figure 2a the cell (3, 2) ignoring the cell (3, 1)). 図2aでは、細胞(3, 2)は細胞(3, 1)を無視します。 0.83
8 8 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 2: Generic distance with window and early abandoning. アルゴリズム2:ウィンドウと早期放棄を伴う汎用距離。 0.69
Input: the time series S and T , a warping window w, a cut-off point cutoff Result: Cost D(S, T ) 入力:時系列SとT、ワープウィンドウw、カットオフポイントカットオフ結果:コストD(S,T)
訳抜け防止モード: 入力 : 時系列 s と t, ワーピングウインドウ w, a cut-off point cutoff result : cost d(s , t )
0.76
1 co ← shortest series between S and T 2 li ← longest series between S and T 3 if w < Lli − Lco then return +∞ 4 (prev, curr) ← arrays of length lco + 1 filled with +∞ 5 curr[0 ] ← 0 6 curr[1 — w+1 ] ← InitHBorder 7 for i ← 1 to Lli do swap(prev, curr) jStart ← max(1, i − w) jStop ← min(i + w, Lco) curr[jStart − 1] ← if jStart == 1 then InitVBorder else +∞ minv ← +∞ for j ← jStart to jStop do S と T 2 の間の最短級数 w < Lli − Lco が S と T 3 の間の最短級数 w < Lli − Lco であるなら +∞ 4 (prev, curr) の長 lco + 1 の配列を +∞ 5 curr[0 ] で満たすと +∞ 0 6 curr[1 - w+1 ] > InitHBorder 7 for i > 1 to Lli do swap(prev, curr) jStart (prev, curr) jStop > max(1, i − w) jStop >min(i + w, Lco) curr[jStart − 1] であるなら、jStart == 1 である。 0.75
8 9 12 13 10 8 9 12 13 10 0.85
11 14 15 16 11 14 15 16 0.85
prev[j-1 ] + Canonical ]prev[j-1 ] + canonical 0.80
prev[j ] + AlternateLine prev[j ] +AlternateLine 0.77
curr[j-1 ] + AlternateColumn curr[j-1 ] + AlternateColumn 0.92
v ← min v (複数形 vs) 0.25
minv ← min(minv, v) curr[j ] ← v minv (countable かつ uncountable, 複数形 minvs) 0.31
if minv > cutoff then return +∞ minv > cutoff ならば +∞ を返す。 0.75
17 18 return curr[lco] 17 18 return curr[lco] 0.85
2.5 Other Distances 2.5 その他の距離 0.52
The two missing distances from EE are the squared Euclidean distance and the longest common sub-sequence distance. eeからの2つの欠落距離は、二乗ユークリッド距離と最も長い共通部分列距離である。 0.70
They do not fit the common structure described section 2.4, nor will they fit the common structure described section 3. 2.4項の共通構造に合致しないし、3項の共通構造にも合致しない。 0.67
Hence, we fully treat them here. したがって、私たちはそれらをここで完全に扱います。 0.52
2.5.1 Squared Euclidean Distance 2.5.1 ユークリッド距離 0.59
The squared Euclidean distance is exactly what you would expect. 四角いユークリッド距離はまさにあなたが期待するものです。 0.61
It requires series of equal length (i.e. 同じ長さ(すなわち)の連続が必要です。 0.71
it is not elastic), returning a score of +∞ if not. 弾性ではない) でなければ +∞ のスコアを返します。 0.74
Algorithm 3 presents an early abandoned squared Euclidean distance. アルゴリズム3は、早期に放棄されたユークリッド距離を示す。 0.56
Our C++ implementation is based on it. C++の実装はそれに基づいています。 0.59
As mentioned before, this distance is equivalent to CDTW (section 2.3.2) with a window of 0. 前述したように、この距離は CDTW (section 2.3.2) と同値であり、ウィンドウは 0 である。 0.72
Algorithm 3: Squared Euclidean Distance. アルゴリズム3:正方形ユークリッド距離。 0.69
Input: the time series S and T , a cut-off point cutoff Result: sqed(S, T ) 入力: 時系列 S と T , カットオフポイント カットオフ結果: sqed(S, T ) 0.70
1 if LS (cid:54)= LT then return +∞ 2 acc ← 0 3 for i ← 1 to LS do 1 もし LS (cid:54)= LT ならば、 +∞ 2 は i の 0 3 を LS に返す。 0.85
acc ← acc + (Si − Ti)2 if acc > cutoff then return +∞ acc > acc + (si − ti)2 if acc > cutoff then return +∞ 0.78
4 5 6 return acc 4 5 6 return acc 0.85
9 9 0.85
英語(論文から抽出)日本語訳スコア
2.5.2 Longest Common Sub-Sequence 2.5.2 最長共通サブシーケンス 0.60
The Longest Common Sub-Sequence distance (LCSS, see [7]) is another elastic distance, more commonly used for string matching. 最も長い共通サブシーケンス距離(LCSS、参照[7])は、より一般的に文字列マッチングに使用される別の弾性距離です。 0.81
Time series aren’t usually made of discreet characters than can be compared for equality, so LCSS considers two values equal if they are within a threshold . 時系列は通常、等価で比較できるよりも控えめな文字でできていないので、LCSS は2つの値がしきい値 * 内であれば等しいと考える。 0.74
LCSS is describes by Equations 9. LCSSはEquations 9で記述される。 0.83
MLCSS(0, 0) = 0 MLCSS(i, 0) = 0 MLCSS(0, j) = 0 MLCSS(0, 0) = 0 MLCSS(i, 0) = 0 MLCSS(0, j) = 0 0.85
MLCSS(i, j) = MLCSS(i, j) = 0.85
1 + MLCSS(i − 1, j − 1) 1 + MLCSS(i − 1, j − 1) 0.85
MLCSS(i − 1, j − 1) シュMLCSS(i − 1, j − 1) 0.85
MLCSS(i − 1, j) MLCSS(i, j − 1) MLCSS(i − 1, j) MLCSS(i, j − 1) 0.85
max If |si−1 − tj−1| ≤  マックス もし |si−1 − tj−1| ≤ であるなら 0.61
otherwise (9a) そうでなければ (9a) 0.64
(9b) (9c) (9d) (9b) (9c) (9d) 0.94
 Contrary to other distances, LCSS maximizes a score, a higher score indicating greater similarity.  他の距離とは対照的に、LCSSはスコアを最大化し、高いスコアはより類似性を示す。 0.70
To be usable with nearest neighbor classifiers, its result is transformed using Equation 10. 近隣の分類器で使用できるように、その結果はEquation 10を使って変換される。 0.69
The MLCSS(LS, LT ) score is first normalized by dividing it by the length of the shortest series, i.e. MLCSS(LS, LT)スコアは、まず最短系列の長さで分割することによって正規化される。 0.80
the maximum number of possible matches. 可能なマッチの最大数。 0.68
Then, it is subtracted from 1, returning a score between 0 and 1 with the desired property (lower means greater similarity). そして 1 から減算され、0 から 1 の間のスコアを所望の特性で返す(より低いものはより類似度を意味する)。 0.70
LCSS(T, S) = 1 − MLCSS(L,T )(LS, LT ) LCSS(T, S) = 1 − MLCSS(L, T )(LS, LT ) 0.85
min(LS, LT ) min(LS, LT ) 0.85
(10) Algorithm 4: LCSS with warping window and early abandoning. (10) アルゴリズム4:ワーピングウィンドウと早期放棄を備えたLCSS。 0.82
Input: the time series S and T , a threshold , a warping window w, a cut-off point cutoff Result: Cost LCSS(S, T ) 入力: 時系列 S と T ,しきい値 , ワープウィンドウ w, カットオフポイント カットオフ結果: コスト LCSS(S, T )
訳抜け防止モード: 入力 : 時系列 s と t,しきい値 , a warping window w , a cut-off point cutoff result : cost lcss(s , t )
0.78
1 co ← shortest series between S and T 2 li ← longest series between S and T 3 if w < Lli − Lco then return +∞ 4 (prev, curr) ← arrays of length lco + 1 filled with 0 5 toreach ← (cid:100)(1 − cutoff) ∗ Lco(cid:101) 6 maxv ← 0 7 for i ← 1 to Lli do S と T 2 の間の最短級数 w < Lli − Lco が S と T 3 の間の最長級数 w < Lli − Lco であれば、長さ lco + 1 の長さ lco + 1 の +∞ 4 (prev, curr) の配列を 0 5 のトーレンチ シュ (cid:100)(1 − cutoff) ∗ Lco (cid:101) 6 maxv 1 から Lli do に対して ∗ Lco (cid:101) で満たすことができる。 0.66
8 9 10 11 12 8 9 10 11 12 0.85
13 14 15 16 13 14 15 16 0.85
17 18 if maxv + (Lli − i) < toreach then return +∞ swap(prev, curr) jStart ← max(1, i − w) jStop ← min(i + w, Lco) curr[jStart − 1] ← 0 for j ← jStart to jStop do if |lii − coj| ≤  then v ← prev[j-1 ] + 1 curr[j ] ← v maxv ← max(maxv, v) v ← max(prev[j-1 ], prev[j ], curr[j-1 ]) 17 18 maxv + (Lli − i) < toreach なら、 +∞ スワップ(prev, curr) jStart は max(1, i − w) jStop は min(i + w, Lco) curr[jStart − 1] は jStop が jStop に対して行う場合、 |lii − coj| ≤ は v は prev[j-1 ] + 1 curr[j-1 ] は v は max(maxv, v) v は max(prev[j-1 ], prev[j-1 ], curr[j-1 ] は curr[j-1 ] である。 0.86
else 19 20 return curr[lco] その他 19 20 return curr[lco] 0.72
10 10 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 4 presents an early abandoned version of LCSS (and how our C++ implementation works). アルゴリズム4は、LCSSの早期放棄バージョン(およびC++実装の仕組み)を提示する。 0.76
To early abandon, the cut-off value (which must be between 0 and 1) is turned into a number of matches that must be reached (line 5). 早期に放棄するためには、カットオフ値(0から1の間)は、到達しなければならないいくつかのマッチに変換される(ライン5)。 0.69
We early abandon if the highest value of a row added to the number of remaining potential matches is below the required value (line 8). 残余の潜在的なマッチの数に加算された行の最高値が要求値以下である場合、我々は早期に放棄する(ライン8)。 0.74
Note that number of remaining matches is given by min(Lco, Lli − i). 残りのマッチの数は min(Lco, Lli − i) で与えられることに注意してください。 0.75
However, because the score is adapted with respect to Lco, we can only early abandoned when we fewer than Lco lines remain (Lli − i < Lco). しかし、スコアは Lco に対して適合しているため、Lco のラインが残らない場合(Lli − i < Lco)にのみ早期に見捨てることができる。 0.75
Hence, the minimum operation is not required. したがって、最小の操作は不要である。 0.83
3 Pruning and Early Abandoning 3 刈り取りと早期放棄 0.72
We saw section 2.4 the idea behind early abandoning. セクション2.4 早期放棄の背後にあるアイデアを見ました 0.62
We now introduce the idea of pruning. 現在、刈り取りのアイデアを紹介します。 0.51
Given a cost matrix like the one presented Figure 1b, pruning refers to avoiding the computation of some of the cells. 図1bのようなコストマトリックスが与えられた場合、プルーニングはいくつかのセルの計算を避けることを指す。 0.76
As we still proceed row by row (such as in Algorithm 1), pruning all the cells in a row leads to early abandoning. アルゴリズム1のように)行ごとに行を進めると、すべてのセルを行にプルーニングすることで、早期放棄につながります。 0.68
In this section, we present how to prune and early abandon the distances based on the common structure described section 2.4. 本項では,第2.4条に規定する共通構造に基づいて,距離を早送りする方法について述べる。 0.69
We present our strategy, “EAPruned”, in a generic manner: all the distances based on the common structure can benefit from it. EAPruned" という戦略を一般的な方法で提示する: 共通構造に基づくすべての距離は、その利点を享受できる。 0.72
We present and illustrate the idea behind EAPruned using DTW. DTWを用いたEAPrunedの背景にあるアイデアを提示し、解説する。 0.59
However, we present the algorithm with a warping window and computed borders. しかし、我々はワーピングウィンドウと計算された境界でアルゴリズムを提示します。 0.72
Pruning was first developed for DTW in 2016 with PrunedDTW [25]. Pruningは2016年にPrunedDTW [25]とともにDTW用に最初に開発された。 0.65
It aimed at speeding up all pairwise calculation of DTW. DTWの全てのペアワイズ計算を高速化することを目的としていた。 0.53
In this context, no cut-off value is provided. この文脈では、カットオフ値は提供されない。 0.62
Instead, PrunedDTW computes its own cut-off value based on the diagonal of the cost matrix. 代わりに、PrunedDTWはコストマトリックスの対角線に基づいて独自のカットオフ値を計算します。 0.72
In the case of DTW with series of equal length, this amounts to the squared Euclidean distance. 同じ長さの系列を持つDTWの場合、これは正方形のユークリッド距離に相当します。 0.75
With disparate length, the bottom left corner can be reach by completing the diagonal with the last column. 異なる長さの場合、左下隅は最後の列で対角線を完結させることで到達できる。 0.79
Regardless of the distance, those cut-off computations are all similar to Algorithm 3, i.e. 距離に関係なく、それらのカットオフ計算はすべてアルゴリズム3、すなわち類似している。 0.75
are in O(L) time complexity, and a O(1) space complexity. O(L) の時間複雑性であり、O(1) 空間複雑性である。 0.82
The cut-off is an upper bound ub on the actual DTW cost, i.e. カットオフはDTWコスト、すなわち実際のDTWコストの上限ubである。 0.72
the actual DTW cost is smaller (or equal) than ub. 実際のDTWコストは、ubよりも小さい(または等しい)。 0.85
PrunedDTW uses ub not to early abandon, but to skip the computation of some alignments (i.e. PrunedDTWは、ubを早期に放棄するのではなく、いくつかのアライメントの計算をスキップする(すなわち)。 0.53
some cells from the cost matrix) that we know will be above it. コストマトリックスのいくつかの細胞)がそれより上にあることが分かっています。 0.63
PrunedDTW was later used for similarity search [26] with early abandoning. PrunedDTW は後に類似性探索 [26] に使われ、早期に放棄された。 0.68
However, its core was not revisited, and early abandoning was implemented in the classical way (like in Algorithm 2). しかし、その中核は再検討されず、(アルゴリズム2のように)古典的な方法で早期に放棄された。 0.67
We revisited the idea behind PrunedDTW and developed a strategy that tightly integrates early abandoning and pruning. 我々はPrunedDTWの背景にあるアイデアを再考し、早期放棄とプルーニングを緊密に統合する戦略を開発した。 0.61
In addition, it delivers more pruning than PrunedDTW and is carefully designed for computational efficiency. さらに、PrunedDTWよりもプルーニングを多く提供し、計算効率を高めるために慎重に設計されている。 0.55
It is organized in successive stages in which we avoid computing unnecessary dependencies. 不要な依存関係の計算を避けるため、連続して組織化されます。 0.52
EAPruned itself is presented Algorithm 5; the strategy is presented in two parts in “Pruning from the left” and “Pruning on the right”. EAPruned自身はアルゴリズム5で示され、その戦略は“Pruning from the left”と“Pruning on the right”の2つの部分で示される。 0.85
3.1 Pruning From the Left 3.1 左から突き出す 0.86
As stated earlier, we compute the cost matrix row by row, from left to right. 前述したように、コストマトリックスの行を左から右に並んで計算します。 0.73
While computing a row, we look at discarding as many as possible of the leftmost cells of the matrix. 列を計算している間、行列の最左端の細胞をできるだけ多く捨てることに目を向ける。 0.70
We define a “discard zone” as being the columns topped by a “discard point”. ディスカードゾーン”を“ディスカードポイント”でトッピングされた列と定義します。 0.56
In a row, discard points are all the cells preceding the first cell with a cost below the cut-off2, and that are not already part of the discard zone. 一列に並べると、デカードポイントは、カットオフ2以下のコストで最初のセルに先行する全てのセルであり、既にデカードゾーンの一部ではない。 0.64
Discard points and all the cells in the discard zone have a cost strictly greater than the cut-off. 破棄ポイントと破棄ゾーン内のすべてのセルは、カットオフよりも厳密にコストがかかります。 0.74
In the Figures 3a and 3b, the white cells with red border are discard points, and the discard zone is made of the grey columns they top. 図3aおよび3bでは、赤い境界線を持つ白いセルはポイントを破棄し、廃棄ゾーンは上部の灰色の列で作られています。 0.75
Notice how the cell (1, 5) is greater than the cut-off, but not a discard point. セル(1, 5)がカットオフよりも大きいが、破棄ポイントではないことに注意してください。 0.77
This is because it is on the right of (1, 1) which has a cost below the cut-off. これは(1, 1)の右側にあるためであり、カットオフ以下のコストがかかる。 0.69
Beside the discard points, no cell in the discard zone is ever evaluated: they are pruned. 廃棄ポイントの他に、廃棄ゾーン内のセルは評価されず、刈り取られる。
訳抜け防止モード: 破棄ポイントに加えて、破棄ゾーンのセルは評価されません。 : 取り除かれている。
0.63
For DTW, the discard zone starts with the left border at (1, 0). DTWの場合、破棄ゾーンは左の境界線(1, 0)で始まります。 0.69
The cell at (2, 0) is not a discard point, as it already is in the discard zone. 既に破棄ゾーンにあるので、(2, 0)のセルは破棄ポイントではありません。 0.61
This is due to DTW borders initialization to +∞, excepts for (0, 0) = 0. これは、(0, 0) = 0 を除いて、DTW 境界の初期化が +∞ になるためである。 0.73
When the border is computed, the discard zone starts at the first line i such that Md(S,T )(i, 0) > cutoff. 境界が計算されると、廃棄ゾーンは、Md(S,T )(i,0) > カットオフとなるように、第1の線 i から始まる。 0.78
If a window w is used, the discard zone starts at the line w + 1, unless started earlier (see Algorithm 5 line 14). ウィンドウ w が使われる場合、ディスカードゾーンは、先に開始しなければ w + 1 行から始まる(アルゴリズム 5 行 14 行参照)。 0.79
2I.e. that can be part of an optimal warping path. 2I。 それは最適なウォーピングパスの一部になり得る。 0.73
11 11 0.85
英語(論文から抽出)日本語訳スコア
(a) MDTW(S,T ) with cutoff = 9. (a)カットオフ=9のMDTW(S,T)。 0.68
The arrows represent the dependencies of the cell (4, 1). 矢印は、セルの依存関係を表す(4, 1)。 0.68
(b) MDTW(S,T ) with cutoff = 6. b) MDTW(S,T) with cutoff = 6。 0.74
Early abandon occurs at the end of the fifth line. 早期放棄は5行目の終わりに発生します。 0.75
Figure 3: Illustration of MDTW(S,T ) “from the left” pruning with two different cut-off value. 図3: mdtw(s,t ) “from the left” プルーニングの2つの異なるカットオフ値による図示。 0.79
To explain this pruning scheme, we examine a cell’s dependencies, as illustrated in Figure 3a for the cell (4, 1). この割付けスキームを説明するために、セル(4, 1)の図3aに示すように、セルの依存関係を調べます。 0.72
As before (see section 2.4), we give them the names of “left”, “top” and “diag”. 前述した通り(第2.4条参照)、私たちは彼らに「左」「上」「下」の名前を与えます。 0.73
All dependencies of (4, 1) are discarded (either in the discard zone or a discard point). 4, 1) のすべての依存関係は破棄されます(破棄ゾーンまたは破棄ポイントのいずれか)。 0.65
A cell’s cost can only be greater than (or equal to) its smallest dependency. セルのコストは、その最小の依存性よりも(あるいは同等に)大きいだけである。 0.80
It follows that if all of a cell’s dependencies are discarded, the cell can be discarded. 従って、あるセルの依存関係が全て破棄された場合、そのセルは破棄される。 0.69
Starting on the left border, a cell only has a top dependency. 左の境界線から始まると、セルはトップの依存関係のみを持ちます。 0.67
Hence, as soon as a border cell is above the cut-off (i.e. したがって、境界セルがカットオフを超えるとすぐに(すなわち)停止する。 0.76
(0, 1)), the remainder of the column can be discarded. (0, 1))、列の残りの部分を破棄することができます。 0.76
In turn, this creates the same conditions for the next column, starting next row. 順番に、次の列で同じ条件を作成し、次の行を開始します。 0.71
We only need to check the top dependency for cells (i > 1, 1), stopping as soon as possible. 細胞(i > 1, 1)に対するトップ依存関係のみをチェックし、できるだけ早く停止する必要があります。 0.75
The cell (3, 1) is above the cut-off, allowing to discard the remainder of the column. セル(3, 1)はカットオフの上方にあり、カラムの残りを廃棄することができる。 0.73
When proceeding row by row, pruning from the left is implemented by starting the next row after the discarded columns. 行ごとに進行する際には、廃棄された列の後に次の行を起動して左からのプルーニングを行う。 0.71
Discarding all the columns in a row, such as in Figure 3b, leads to early abandoning. 図3bのような行内のすべての列を破棄すると、早期放棄につながります。 0.76
Note that in this case, the discard points from (5, 3) up to (5, 6) need to check both their top and diag dependencies. この場合、(5, 3)から(5, 6)までのポイントは、依存関係のトップとダイアグの両方をチェックする必要があることに注意してください。 0.76
3.2 Pruning on the Right 3.2 右側の刈り込み 0.86
In the previous section, we extended a discard zone from the left to the right, leading to early abandoning when it reaches the end of a row. 前のセクションでは、捨てられたゾーンを左から右に拡張し、行の最後に到達すると早期に放棄します。 0.62
This strategy relying on the row by row evaluation order, we cannot do the same starting from the top border as this would require a column by column order. この戦略は行の行評価順序に依存しており、列の列の順序を必要とするため、トップバウンダリから開始することはできません。 0.72
We have to keep pruning inside a row. 私たちは一列に刈り続けなければならない。 0.56
Looking back at Figure 3b with a cut-off value of 6, we can find such cells. 図3bを6のカットオフ値で振り返ると、そのような細胞を見つけることができます。 0.74
The cell at (1, 4) is above the cut-off. 1, 4)のセルはカットオフの上にあります。 0.68
In conjunction with the top border, the following cells can only be above the cut-off. 最上部の境界と連動して、以下の細胞はカットオフを超えるだけである。 0.70
Dealing with this kind scenario allows us to “prune on the right”. この種のシナリオに対処することで、私たちは“右に進む”ことができます。 0.60
Pruning on the right is not as straightforward as pruning from the left. 右側の刈り取りは、左から刈り取るほど簡単ではありません。 0.72
The main reason is that pruning form the left allows us to discard a column once and for all. 主な理由は、左から切り離すことで、列を一度だけ捨てることができるからです。 0.63
But, the idea is similar. しかし、その考えは似ている。 0.74
In the previous section we mentioned that a discard point creates the “same conditions for the next column, starting next row”, allowing to continue the pruning process. 前節では,破棄ポイントが“次の行から始まる次の列のサム条件”を生成して,プルーニングプロセスの継続を可能にする,と説明しました。 0.79
When pruning on the right, we have to identify a condition akin to the top border. 右側を滑走するときは、上部の境界に類似した条件を特定する必要があります。 0.60
This condition is a continuous block of cell above the cut-off value, reaching the end of この条件はカットオフ値の上のセルの連続ブロックであり、終端に達する。 0.78
12 01234560123456044591 01148556713 > 95914910226918131322 10 > 97789221487890123456 01234560445910114855 6713 > 65914910226918131322 10 > 67 > 67 > 68 > 69 > 622148789 12 01234560123456044591 01148556713 > 95914910226918131322 10 > 97789221487890123456 01234560445910114855 6713 > 65914910226918131322 10 > 67 > 67 > 68 > 69 > 622148789 0.67
英語(論文から抽出)日本語訳スコア
(a) MDTW(S,T ) with cutoff = 9 Figure 4: Illustration of MDTW(S,T ) “from the left” and “on the right” pruning with two different cut-off value. (a)カットオフ=9のMDTW(S,T)図4:MTTW(S,T)の「左から」と「右から」のイラストレーションは、2つの異なるカットオフ値でプルーニングします。 0.77
The blue cell represents the point of early abandoning, white cells represent discard points, and dark gray cells represent pruning points. 青い細胞は早期放棄点を表し、白い細胞は廃棄点を表し、暗い灰色の細胞は刈り取り点を表す。 0.80
(b) MDTW(S,T ) with cutoff = 6 (b)カットオフ=6のMDTW(S,T) 0.74
their row. In the case of the top border, this block starts at (0, 1). 彼らの列 上の境界の場合、このブロックは (0, 1) から始まります。 0.68
In Figure 3b, the second one starts at (1, 4). 図3bでは、第2は (1, 4) から始まる。 0.76
The start of those block are called “pruning point”. これらのブロックの開始は "pruning point" と呼ばれる。 0.79
See Figure 4 where they are represented in dark grey with red borders. 図4を参照して、赤枠の濃い灰色で表現します。 0.69
Pruning points give an information for the next row3. プルーニングポイントは次の行3の情報を与える。 0.75
In the next row, as soon as we find a cell above the cut-off and after the pruning point, the remainder of the row can be dropped. 次の行では、カットオフの上のセルを見つけて、プルーニングポイントの後に、行の残りの部分をドロップすることができます。 0.65
Note that the cell just under the pruning point is a special case, as its diag dependency is not discarded by the pruning point (e.g the cell (1, 1) Figure 4b). プルーニングポイントのすぐ下の細胞は、そのダイアグ依存性がプルーニングポイント(例えば、セル(1, 1)図4b)によって破棄されないため、特別なケースである。 0.79
The tricky part is that pruning points move back and forth across rows. トリッキーな部分は、プルーニングポイントが行を横切って前後に移動することです。 0.59
To determine their position, a cell (i, j) with a cost below the cut-off will always assume that the next cell is the row’s pruning point. それらの位置を決定するために、カットオフ以下のコストのセル(i, j)は常に次のセルが行の切断ポイントであると仮定します。 0.80
If (i, j + 1) > cutoff, and so on up to (i, Lco), then (i, j + 1) indeed is a pruning point. i, j + 1) > カットオフ (i, Lco) まで (i, j + 1) > カットオフ (cutoff) であれば、(i, j + 1) は実際、プリンティングポイントである。 0.71
Else, we assume that (i, j + 2) is the pruning point, repeating the same logic. それ以外の場合、(i, j + 2) はプルーニング点であり、同じ論理を繰り返していると仮定する。 0.76
Note that all rows (up to an early abandoning row) have one and only one pruning point. すべての行(早期放棄行まで)は1つと1つのプルーニングポイントしか持たないことに注意してください。 0.62
It may be out of bounds, e.g. 例えば、境界外かもしれない。 0.46
at Lco + 1, in which case it does not appears in the figures. Lco + 1では、その場合、数字には表示されません。 0.78
Let us look at some examples, Figure 4b. 図4bの例を見てみましょう。 0.75
• The cell (2, 2) > cutoff is not a pruning point, because it does not start a continuous block of cells • 細胞(2, 2) > 切断は、細胞の連続的なブロックを開始しないため、刈り取りポイントではない。 0.83
above cutoff reaching the end of the row. カットオフの上、行の最後に到達します。 0.61
• The cell (3, 3) and all its following cells are above cutoff. •細胞(3,3)とその後続の細胞は、すべてカットオフ以上である。 0.83
The row must be fully evaluated to ensure that (3, 3) indeed is the row’s pruning point. 行は、(3, 3) が実際に行のpruningポイントであることを保証するために、完全に評価する必要があります。
訳抜け防止モード: 行は完全に評価されなければならない 確実に (3, 3 ) が行のプルーニングポイントであることを保証する。
0.73
It contributes to enabling pruning on the fourth row, starting at (4, 4). 4行目 (4, 4) から始まる4行目へのプルーニングの実現に寄与する。 0.69
Finally, we have to address what happen when both pruning strategies “collide”. 最後に、両方のプルーニング戦略が“衝突”した場合に何が起こるかに対処する必要があります。 0.47
The Figure 4b illustrates such a collision in blue. 図4bは、このような衝突を青で示している。 0.62
Without pruning on the right, the cell (5, 3) would be a discard point. 右側に刈り取ることなく、セル(5, 3)は破棄ポイントになります。 0.68
Because it is below a pruning point, we know that the rest of the row is above the cut-off. プルーニングポイントを下回っているので、残りの行がカットオフの上にいることが分かります。 0.55
EAPruned allows to prune a total of 16 cells over 36. EAPrunedでは、36以上の16の細胞をプルークすることができる。 0.67
The usual early abandoning strategy presented section 2.4 would only prune the セクション2.4が示す通常の早期放棄戦略は 0.69
3Similar to discard points, instructing the next row to skip their column. 3 ポイントを破棄し、次の行に列をスキップするように指示する。 0.67
13 01234560123456044591 0 > 91148556713 > 95914910 > 9226918 > 913132210 > 97789221487890123456 012345604459 > 61011485567 > 613 > 659 > 6149102269 > 61813132210 > 67 > 678922148789 13 01234560123456044591 0 > 91148556713 > 95914910 > 9226918 > 913132210 > 97789221487890123456 012345604459 > 61011485567 > 613 > 659 > 6149102269 > 61813132210 > 67 > 678922148789 0.89
英語(論文から抽出)日本語訳スコア
last line, i.e. 6 cells. 最後の行、i.e. 6細胞。 0.70
Also, if the cell at (1, 1) is above cutoff, EAPruned immediately early abandons, when the classical way either evaluates the full row or requires a special case for this cell. また、(1, 1)のセルがカットオフを超えると、古典的な方法で全行を評価するか、このセルに特別なケースを必要とする場合、直ちにeaprunedが破棄される。 0.68
As expected, Figure 4a does not show any early abandoning. 予想通り、図4aは早期放棄を示しません。 0.78
In this case, EAPruned still prunes 5 cells. この場合、EAPrunedはまだ5つの細胞をプルーンします。 0.63
3.3 The EAPruned Algorithm 3.3 EAPruned Algorithm 0.96
We now present the EAPruned algorithm (Algorithm 5) which is compatible with any distance matching the common structure described section 2.4. 現在,提案するEAPrunedアルゴリズム (Algorithm 5) は, 2.4条に記述された共通構造に適合する任意の距離と互換性がある。 0.72
We present the algorithm with a window and computed borders, covering the most complex case. このアルゴリズムをウィンドウと計算境界で表現し,最も複雑な場合をカバーする。 0.76
Our implementations are specialized for each distance’s needs. 私たちの実装は各距離のニーズに特化しています。 0.63
Our algorithm exploits resulting properties of pruning to further reduce the computational effort. このアルゴリズムは, プルーニングの結果として生じる特性を利用して, 計算量をさらに削減する。 0.53
For example, cells after the pruning point from the previous row can ignore their top and diag dependencies, along with the associated cost computation, as they are known to be above cutoff. 例えば、前行からのプルーニングポイント後のセルは、カットオフ以上であることが知られているように、そのトップとダイアグの依存関係と関連するコスト計算を無視することができる。 0.70
Hence, only the left dependency needs to be computed. したがって、左の依存関係のみを計算する必要がある。 0.72
To do so, we split the computation of a row in several stages. そこで我々は列の計算をいくつかの段階に分けた。 0.77
For each stage, we indicate the dependencies that must be checked. 各ステージに対して、チェックが必要な依存関係を示します。 0.69
1. Compute the value of the left border (computed or outside the window). 1. 左の境界線(計算またはウィンドウの外側)の値を計算します。 0.77
A computed border may require the top dependency. 計算された境界は、トップ依存関係を必要とする。 0.49
2. Compute discard points until a non-discard point or the pruning point. 2. 廃棄ポイントを非廃棄ポイントまたは刈り取りポイントまで計算する。 0.81
Check the diag and top dependencies. diag と top dependencies をチェックします。 0.84
3. Compute non-discard point until the pruning point 3. プルーニングポイントまで非廃点計算 0.74
Check all dependencies. すべての依存関係をチェックする。 0.48
4. Deal with the cell at the pruning point 4. プルーニングポイントでの細胞とのディール 0.72
Check the diag (always) and left (unless was a discard point) dependencies. diag (always) と左 (discard point) の依存関係をチェックします。 0.74
5. Compute the cells after the pruning point 5. 刈り取り点の後に細胞を計算します 0.77
Check the left dependency. 左の依存関係をチェックする。 0.60
In Algorithm 5, the discard points are represented by the next start variable. アルゴリズム5では、捨てられたポイントは次のスタート変数で表される。 0.71
The position of the pruning point from the previous row, use to prune in the current row, is represented by the pruning point variable. 前の行からのプルーニングポイントの位置は、現在の行でプルーンするために使用され、プルーニングポイント変数で表される。 0.65
Finally, the next pruning point variable represents the pruning point being computed in the current row, and used when computing the next row. 最後に、次のプルーニング点変数は、現在の行で計算されるプルーニング点を表し、次の行を計算する際に使用される。 0.68
To do so, its value is assigned to pruning point after a row is done (line 39). これを行うには、行が終わった後、その値がpruningポイントに割り当てられます(行39)。 0.75
Beginning a new row, we first determine the index of the first and last columns. 新しい行を開始すると、まず最初の列と最後の列のインデックスを決定します。 0.79
Then, the first stage updates the left border, computing its value or applying the window (line 14). そして、第1段は左境界を更新し、その値を計算するか、ウィンドウを適用する(ライン14)。 0.73
The second stage (line 16) computes discard points, which require the row to be bordered on the left by a value above cutoff (tested line 17). 第2段階(16行目)は、カットオフ上の値(17行目)で左の行に境界を付ける必要がある破棄ポイントを計算します。 0.72
The condition in the for loop ensures that all discard points form a continuous block. forループの条件は、すべての廃棄ポイントが連続ブロックを形成することを保証する。 0.74
As soon as a value below cutoff is found, we jump to the second stage as we cannot have any more discard points. カットオフ以下の値が見つかるとすぐに、2番目のステージにジャンプします。 0.40
As explained in the previous section, next pruning point is set (line 20) to the next column index. 前節で説明されているように、次のプルーニングポイントを次のカラムインデックスに設定する(ライン20)。 0.80
Note that next start can only be updated in the second stages while next pruning point must be checked for update after every cost computation. 注意すべきは、次のスタートは第2ステージでのみ更新可能であり、次のプルーニングポイントは、コスト計算のたびに更新される必要があることである。
訳抜け防止モード: 次の開始は第2段階でのみ更新できます。 次のpruningポイントはあらゆる費用計算の後で更新のために点検されなければなりません。
0.67
The third stage (line 21) compute the cost taking all dependencies into account until we reach pruning point. 第3ステージ(ライン21)は、プルーニングポイントに達するまですべての依存関係を考慮したコストを計算する。 0.73
If pruning point is out of bounds, the third stage completes the row and the following stages are skipped over. プルーニングポイントが境界外の場合、第3段階は行を完了し、次の段階はスキップされます。 0.74
We enter the fourth stage (line 25). 第4段階(25行目)に入ります。 0.66
If we are still within bounds, two cases are possible. まだ境界内にいる場合、2つのケースが可能です。 0.67
Either the left cell is a discard point, or it is not. 左の細胞が廃棄ポイントであるか、そうでないかです。 0.69
If it is a discard point (line 27), then we only need to check the diag dependency, early abandoning if the cost is above cutoff. 破棄点(ライン27)であれば、コストがカットオフ以上であれば早期に放棄して、ダイアグ依存性をチェックするだけでよい。 0.70
It not (line 30), both the left and diag dependencies are checked, and no early abandoning is possible. それは(30行目)、左右の両方の依存関係がチェックされ、早期の放棄は不可能です。 0.65
Finally, we early abandon if we are out of bounds and the discard points reach the end of the row (line 34). 最後に、境界外であれば早期に放棄し、廃棄点が行の終点に達する(ライン34)。
訳抜け防止モード: 最後に、境界がない場合、早期に放棄します。 そして捨てられたポイントは列の終わり(ライン34 )に達します。
0.70
At the fifth and final stage (line 35), only the left dependency is checked as, both the diag and top dependencies are known to be above cutoff. 第5段階と最終段階(ライン35)では、左依存関係のみがチェックされ、diagとトップ依存性の両方がカットオフ以上であることが知られている。 0.67
The loop stops as soon as we find a cost above cutoff, effectively pruning the rest of the row. ループは、コストがカットオフを超えるとすぐに停止し、行の残りの部分を効果的に刈り取る。 0.69
14 14 0.85
英語(論文から抽出)日本語訳スコア
Algorithm 5: Generic EAPruned Algorithm. アルゴリズム5: ジェネリックEAPrunedアルゴリズム。 0.68
Input: the time series S and T , a warping window w, a cut-off point cutoff Result: Cost d(S, T ) 入力:時系列SとT、ワープウィンドウw、カットオフポイントカットオフ結果:コストd(S,T)
訳抜け防止モード: 入力 : 時系列 s と t, ワーピングウインドウ w, a cut-off point cutoff result : cost d(s , t )
0.76
1 co ← shortest series between S and T 2 li ← longest series between S and T 3 if w < Lli − Lco then return +∞ 4 (prev, curr) ← arrays of length lco + 1 filled with +∞ 5 curr[0 ] ← 0 6 curr[1 — w+1 ] ← InitHBorder 7 next start ← 1 8 pruning point ← 1 9 for i ← 1 to Lli do swap(prev, curr) jStart ← max(i − w, next start) jStop ← min(i + w, Lco) j ← jStart /* Stage 1: curr[jStart − 1] ← if jStart == 1 then InitVBorder else +∞ /* Stage 2: if curr[jStart-1 ] > cutoff then w < lli − lco then return +∞ 4 (prev, curr) > arrays of length lco + 1 fill with +∞ 5 curr[0 ] , 0 6 curr[1 – w+1 ] , inithborder 7 next start s 1 8 pruning point , 1 9 for i ] 1 to lli do swap(prev, curr) jstart , max(i − w, next start) jstop , min(i + w, lco) j , jstart /* stage 1: curr[jstart − 1] , if jstart == 1 then initorder then if i == 1 then initvborder then if 2 /jstart > 1} } } } では、次のスタートがカットされる。
訳抜け防止モード: もし w < Lli − Lco が + ∞ 4 (prev, ) を返すなら、S と T 2 の間の最も短い級数は S と T 3 の間の最長級数である。 curr ) 長さ lco + 1 の配列 + ∞ 5 curr[0 ] × 0 6 curr[1 — w+1 ] × InitHBorder 7 次の開始 ・ 1 8 pruning point ・ 1 9 for i ・ 1 to Lli do swap(prev, initHBorder 7 for i ・ 1 8 pruning point ・ 1 9 for i ・ 1 to Lli do swap(prev, ) curr ) jStart(i − w, next start ) jStop(i + w, ) min(i + w) もし jStart = 1 ならば InitVBorder else + ∞ / * Stage 2 : curr[jStart-1 ] > cutoff
0.79
init the vertical border for j to pruning point − 1 while j = next start do 垂直の国境を囲む j から pruning point − 1 に対して j = next start do 0.87
10 11 12 13 10 11 12 13 0.85
14 15 16 17 14 15 16 17 0.85
discard points up to, excluding, the pruning point プルーニングポイントまで、または、除いたポイントを破棄する 0.62
curr[j ] ← min if curr[j ] ≤ cutoff then next pruning point ← j + 1 else next start++ curr[j ] が min if curr[j ] ≤ cutoff then next pruning point ] j + 1 else next start++ 0.86
prev[j-1 ] + Canonical prev[j-1 ] + Canonical 0.92
+ AlternateLine +AlternateLine 0.69
/* Stage 3: for j to pruning point − 1 do /*ステージ3:jからpruning point - 1にします。 0.80
continue up to, excluding, the pruning point 引き裂く点を除いて、まで続く 0.46
prev[j ] (cid:40) prev[j-1 ] + Canonical prev[j ] (cid:40) sprev[j-1 ] + canonical 0.83
prev[j ] curr[j ] ← min prev[j ] curr[j ] > min 0.76
+ AlternateLine +AlternateLine 0.69
if curr[j ] ≤ cutoff then next pruning point ← j + 1 curr[j ] ≤ cutoff ならば、次の pruning point は j + 1 である。 0.78
curr[j-1 ] + AlternateColumn curr[j-1 ] + AlternateColumn 0.92
/* Stage 4: if j ≤ jStop then /* ステージ4: j ≤ jStop の場合 0.77
at the pruning point the pruning point―the pruning point 0.60
if j = next start then j = next start の場合 0.77
curr[j ] ← prev[j-1 ] + Canonical if curr[j ] ≤ cutoff then next pruning point ← j + 1 else return +∞ curr[j ] ^ prev[j-1 ] + Canonical if curr[j ] ≤ cutoff then next pruning point ^ j + 1 else return +∞ 0.90
(cid:40) else (cid:40) その他 0.69
j++ curr[j ] ← min if curr[j ] ≤ cutoff then next pruning point ← j + 1 j++ curr[j ] > min if curr[j ] ≤ cutoff, then next pruning point > j + 1 0.70
curr[j-1 ] + AlternateColumn curr[j-1 ] + AlternateColumn 0.92
prev[j-1 ] + Canonical prev[j-1 ] + Canonical 0.92
else if j = next start then return +∞ /* Stage 5: for j to jStop while j = next pruning point do j = next start の場合、j = next pruning point do は j から jStop へ +∞ /* Stage 5: を返します。 0.91
after the pruning point curr[j ] ← curr[j-1 ] + AlternateColumn if curr[j ] ≤ cutoff then next pruning point ← j + 1 プルーニング点 curr[j ] > curr[j-1 ] + AlternateColumn if curr[j ] ≤ cutoff の後、次のプルーニング点 > j + 1 0.83
pruning point ← next pruning point pruning point (複数形 pruning points) 0.47
39 40 return curr[Lco] 39 40 return curr[Lco] 0.85
18 19 20 21 18 19 20 21 0.85
22 23 24 25 22 23 24 25 0.85
26 27 28 29 26 27 28 29 0.85
30 31 32 33 30 31 32 33 0.85
34 35 36 37 34 35 36 37 0.85
38 15 */ */ 38 15 */ */ 0.85
*/ */ */ */ */ */ 0.85
英語(論文から抽出)日本語訳スコア
4 Experiments EAPruned distances produce the exact same results as their classic counterparts. 4つの実験 EAPruned distancesは、従来のものと全く同じ結果をもたらす。 0.71
Hence, our experiments are not about accuracy, but execution speed. したがって、実験は正確性ではなく、実行速度に関するものです。 0.70
We implemented the DTW, CDTW, WDTW, ERP, MSM and TWE distances following Algorithm 5, simplifying (e.g. 我々はアルゴリズム5に従ってDTW, CDTW, WDTW, ERP, MSM, TWE距離を実装した。 0.68
removing handling of the warping window) where possible. 可能な場合は、ワーピングウィンドウの取り扱いを削除します。 0.51
All the experiments have been run in the same conditions, on a computer equipped with 64GB of RAM (enough memory to fit any dataset from the UCR Archive) and an AMD Opteron 6338P at 2.4Ghz. すべての実験は、64GBのRAM(UCRアーカイブのデータセットに適合する十分なメモリ)と2.4GhzのAMD Opteron 6338Pを備えたコンピュータで、同じ条件で実行されています。 0.83
We tested the performance of four versions. 我々は4つのバージョンのパフォーマンスをテストした。 0.66
The first one, “Base”, is the classical double buffered implementation without early abandoning. 最初の“Base”は、早期に放棄せずに古典的なダブルバッファ実装である。 0.80
The second one, “Pruned”, is based on Algorithm 5. 第2の“Pruned”は、アルゴリズム5をベースとしている。 0.78
However, it uses its own computed cutoff based on the diagonal of the cost matrix, as suggested by [25]. しかし、[25] で示唆されるように、コスト行列の対角線に基づく独自の計算カットオフを用いる。 0.77
Such cutoff only allow to prune, and may be quite loose. このようなカットオフはプルーンのみを許可し、非常に緩い場合があります。 0.55
However, it allows to show how our implementations perform when early abandoning is not possible. しかし、早期放棄が不可能な場合に実装がどのように機能するかを示すことができる。 0.51
The third one, “EABase”, is the classical double buffered implementation with early abandoning as presented Algorithm 2. 3つめの“EABase”は従来のダブルバッファ実装で、提示されたアルゴリズム2で早期に廃止されている。 0.67
Finally, the fourth one, “EAPruned”, is based on Algorithm 5. 最後に、4番目の「EAPruned」はアルゴリズム5に基づいています。 0.80
The Pruned and EAPruned version are not available for SQED and LCSS. PrunedとEAPrunedバージョンはSQEDとLCSSでは利用できません。 0.83
These distances are implemented following Algorithms 3 and 4. これらの距離はアルゴリズム3と4に従って実装される。 0.60
The first experiment compares the various versions against each other. 最初の実験では、様々なバージョンを比較した。 0.77
Every version of every distance is used within a NN1 classifier. 各距離の全てのバージョンはNN1分類器内で使用される。 0.72
Every classifier is run over every default train/test split from the UCR Archive in its 85 datasets version [4], for a total of 2380 runs. すべての分類器は、85データセットバージョン[4]のUCRアーカイブからすべてのデフォルトトレイン/テスト分割で実行され、合計2380回実行されます。 0.72
We use the parameters found by EE [14] after training. トレーニング後にEE [14]で見つかったパラメータを使用します。 0.76
Hence, our benchmarking conditions are similar to EE at test time. したがって、ベンチマーク条件はテスト時のEEと似ています。 0.64
The second experimentation assesses the impact of lower bounding of CDTW and DTW. 第2実験はCDTWおよびDTWの下界の影響を評価する。 0.72
The C++ source code for all the versions and the EE parameters are available on github [5]. すべてのバージョンのc++ソースコードとeeパラメータはgithub[5]で公開されている。 0.75
4.1 Evaluation of Pruning and Early Abandoning 4.1 刈り取りと早期放棄の評価 0.84
We measured the time taken by each distance, in each available version, to perform NN1 classification on the default train/test splits from the UCR Archive with 85 datasets. ucrアーカイブからのデフォルトの列車/テスト分割に対して85データセットでnn1分類を行うために,各距離の時間を測定した。 0.70
The Figure 5 presents the results in hours per distance, except for Figure 5a which excludes LCSS and SQED, as they are not prunable. 図5は、LCSSとSQEDを除外する図5aを除いて、実行不可能であるため、結果を時間単位で提示する。 0.76
LCSS and SQED (Figures 5h and 5i) are only early abandoned, not pruned. LCSSとSQED(図5hと5i)は早期に放棄され、刈り取られていない。 0.71
Both are ≈ 3 times faster when early abandoned. どちらも早期放棄時に3倍速くなります。 0.70
SQED is so fast that its time is negligible compared to other distances, early abandoned or not. SQEDは非常に速く、他の距離と比較して時間が無視できるほどです。 0.63
This is expected as its time complexity is O(L). これは時間複雑性が O(L) であるから予想される。 0.78
The time complexity of LCSS is O(Lw), for a warping window of size w, leading to a worst case complexity of O(L2). LCSS の時間複雑性は O(Lw) であり、サイズ w のワープウィンドウは O(Lw) で、O(L2) の最悪のケース複雑性をもたらす。 0.76
When early abandoning, the best case complexity is in O(L), due to buffers initialization. 早期に放棄する場合には、バッファの初期化によるO(L)の複雑さが最適である。 0.76
Now looking at the prunable distances Figure 5a. さて 刈り取り可能な距離図5aを見てみましょう 0.68
Compared to the Base case, pruning seems to help. Baseケースと比較して、pruningは役に立ちそうです。 0.59
However, this is not always the case when looking at individual distances: CDTW and TWE (Figures 5c and 5g) are actually slower. しかし、個々の距離を見る場合、CDTWとTWE(図5cと5g)は実際には遅い。
訳抜け防止モード: しかし、個々の距離を見る場合、必ずしもそうではない。 CDTWとTWE(図5cと5g)は実際には遅い。
0.74
This may be explained by the small windows used in the case of CDTW4. これはCDTW4の場合には使用される小さい窓によって説明することができます。 0.69
Small windows mean that there are less pruning opportunities. 小さな窓は刈り取りの機会が少ないことを意味する。 0.74
It follows than the time saved by pruning is less than its overhead cost (coming from the pruning technique itself, plus the computation of a cutoff). 引き落としによって節約される時間よりも、そのオーバーヘッドコスト(切り落としのテクニック自体から、そしてカットオフの計算から来る)よりも少なくなります。 0.61
In the case of TWE, which does not have a window, the computed cutoff may not allow to prune enough. ウィンドウを持たないTWEの場合、計算されたカットオフで十分なプルーンができない場合があります。 0.63
On the other hand, WDTW (Figure 5d), which does not have a window, is the only distance which benefits more from pruning than early abandoning in its base version. 一方、ウィンドウを持たないWDTW(図5d)は、ベースバージョンで早期に放棄するよりも、pruningの恩恵を受ける唯一の距離です。 0.62
We explain this by WDTW’s non linear weights: close to 0 around the diagonal, they rapidly increase as we step away. 私たちはこれをWDTWの非線形重みで説明します:斜めのまわりで0に近く、私たちは離れると急速に増加します。 0.70
Hence, the computed cutoff based on the diagonal is relatively tight, allowing a lot of pruning. したがって、対角線に基づく計算されたカットオフは比較的きついため、多くの刈り取りが可能となる。 0.68
Finally, EAPruned is ≈ 7.61 times faster than Base, and ≈ 2.88 times faster than EABase. 最後に、EAPrunedはBaseよりも7.61倍速く、EABaseよりも2.88倍速い。 0.75
Looking at individual distances, EAPruned is always the fastest, with a speedup ranging from ≈ 3.93 (TWE) up to ≈ 39.2 (WDTW) compared to Base, and from ≈ 1.85 (TWE) up to ≈ 8.44 (WDTW) compared to EABase. 個々の距離を見ると、EAPrunedは常に最速であり、速度アップはベースと比較して3.93(TWE)から39.2(WDTW)まで、そしてEABaseと比較して1.85(TWE)から8.44(WDTW)までです。 0.79
Note that CDTW (speedup ≈ 5.8) and TWE (speedup ≈ 3.93) remain the distances appearing to benefit less from pruning. なお、cdtw(スピードアップ5.8)とtwe(スピードアップ3.93)は、刈り取りによる利益の少ない距離である。 0.64
However, if TWE already benefits from EABase, only EAPruned achieves to speed up CDTW. しかし、もしTWEがEABaseの恩恵を受けているなら、EAPrunedだけがCDTWを高速化する。 0.64
4Note that CDTW is ≈ 12 times faster than DTW in the base version, giving an idea of the effect of small windows on the 4CDTWは、ベースバージョンではDTWの12倍の速度で、小さな窓の効果のアイデアを与えている点に注意してください。 0.73
computation time. 16 計算時間。 16 0.77
英語(論文から抽出)日本語訳スコア
(a) All Prunable Distances (a) すべての運転距離 0.69
(b) DTW (c) CDTW (b)DTW (c) CDTW 0.84
(d) WDTW Figure 5: Accumulated timings in hours of NN1 classification over 85 datasets from the UCR archive, using parameters discovered by EE. (d)WDTW 図5:EEによって発見されたパラメータを使用して、UCRアーカイブから85のデータセット上のNN1分類時間の累積タイミング。 0.79
(e) ERP (f) MSM (e)ERP (f)MSM 0.80
17 BasePrunedEABaseEAPr unedalgorithm families025507510012 5150175200runtime in hours192.37135.0272. 7125.24Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEDTW, CDTW, WDTW, ERP, MSM, TWEBasePrunedEABaseE APrunedalgorithm families0510152025ru ntime in hours24.8320.855.511 .01Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEDTWBasePrunedEABas eEAPrunedalgorithm families0.00.51.01.5 2.0runtime in hours1.982.351.990.3 4Total runtime in hours per algorithm family85 UCR Datasets, parameters from EECDTWBasePrunedEABa seEAPrunedalgorithm families0510152025ru ntime in hours24.724.765.320. 63Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEWDTWBasePrunedEABa seEAPrunedalgorithm families0.02.55.07.5 10.012.515.017.5runt ime in hours18.4412.175.091 .39Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEERPBasePrunedEABas eEAPrunedalgorithm families010203040506 070runtime in hours74.7546.2932.37 9.75Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEMSM 17 BasePrunedEABaseEAPr unedalgorithm families025507510012 5150175200runtime in hours192.37135.0272. 7125.24Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEDTW, CDTW, WDTW, ERP, MSM, TWEBasePrunedEABaseE APrunedalgorithm families0510152025ru ntime in hours24.8320.855.511 .01Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEDTWBasePrunedEABas eEAPrunedalgorithm families0.00.51.01.5 2.0runtime in hours1.982.351.990.3 4Total runtime in hours per algorithm family85 UCR Datasets, parameters from EECDTWBasePrunedEABa seEAPrunedalgorithm families0510152025ru ntime in hours24.724.765.320. 63Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEWDTWBasePrunedEABa seEAPrunedalgorithm families0.02.55.07.5 10.012.515.017.5runt ime in hours18.4412.175.091 .39Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEERPBasePrunedEABas eEAPrunedalgorithm families010203040506 070runtime in hours74.7546.2932.37 9.75Total runtime in hours per algorithm family85 UCR Datasets, parameters from EEMSM 0.64
英語(論文から抽出)日本語訳スコア
(g) TWE (h) LCSS (g)TWE (h) LCSS 0.70
Figure 5: archive, using parameters discovered by EE. 図5: EEによって発見されたパラメータを使用したアーカイブ。 0.66
(continued) Accumulated timings in hours of NN1 classification over 85 datasets from the UCR (継続) UCR 85データセット上の NN1 分類時間における累積タイミング 0.84
(i) SQED 18 (i)SQED 18 0.84
BasePrunedEABaseEAPr unedalgorithm families01020304050r untime in hours47.6448.6122.43 12.12Total runtime in hours per algorithm family85 UCR Datasets, parameters from EETWEBaseEABasealgor ithm families0123456runti me in hours5.921.98Total runtime in hours per algorithm family85 UCR Datasets, parameters from EELCSSBaseEABasealgo rithm families0.0000.0050. 0100.0150.0200.0250. 030runtime in hours0.030.01Total runtime in hours per algorithm family85 UCR Datasets, parameters from EESQED BasePrunedEABaseEAPr unedalgorithm family 01020304050runtime in hours47.6448.6122.43 12.12Total Runtime in hours per algorithm family85 UCR Datasets, parameters from EETWEBaseEABasealgor ithm family0123456runtime in hours5.921.98UCR Datasets, parameters in hours in algorithm family0.0000.0050.01 00.0150.0200.0250.03 0runtime in hours0.030.01Total Runtime in hours per algorithm family85 UCR Datasets, parameters from EESQEDED 0.58
英語(論文から抽出)日本語訳スコア
Dataset UWaveGestureLibraryX データセット UWaveGestureLibraryX 0.74
Phoneme ElectricDevices FordB FordA 音素 電気デバイス FordB FordA 0.66
NonInvasiveFetalECGT horax2 NonInvasiveFetalECGT horax1 Non InvasiveFetalECGThor ax2 Non InvasiveFetalECGThor ax1 0.50
HandOutlines UWaveGestureLibraryA ll ハンドアウトライン UWaveGestureLibraryA ll 0.74
StarLightCurves StarLightCurves 0.85
total Base 2.77 5.92 6.09 8.76 14.20 16.40 18.99 19.55 21.16 63.71 177.54 総じて Base 2.77 5.92 6.09 8.76 14.20 16.40 18.99 19.55 21.16 63.71 177.54 0.53
Pruned EABase EAPruned Pruned EABase EAPruned 0.85
2.37 4.21 5.11 6.11 8.43 9.49 7.27 9.91 17.30 48.40 118.61 2.37 4.21 5.11 6.11 8.43 9.49 7.27 9.91 17.30 48.40 118.61 0.42
1.33 3.54 2.84 4.91 7.84 3.80 3.89 6.90 8.47 19.58 63.10 1.33 3.54 2.84 4.91 7.84 3.80 3.89 6.90 8.47 19.58 63.10 0.42
0.57 2.26 1.16 2.36 3.79 0.38 0.36 1.33 3.47 7.61 23.28 0.57 2.26 1.16 2.36 3.79 0.38 0.36 1.33 3.47 7.61 23.28 0.42
Table 1: The 10 slowest datasets, timings in hours. 表1: 最も遅いデータセット10、時間内のタイミング。 0.80
Dataset ItalyPowerDemand データセット ItalyPowerDemand 0.74
Coffee SonyAIBORobotSurface 1 コーヒー SonyAIBORobotSurface 1 0.78
BirdChicken BirdChicken 0.85
BeetleFly ECG200 BeetleFly ECG200 0.88
Wine GunPoint Beef SonyAIBORobotSurface 2 ワイン 銃口 牛肉 SonyAIBORobotSurface 2 0.69
total Base Pruned EABase EAPruned 0.030 0.035 0.044 0.060 0.062 0.075 0.085 0.095 0.098 0.108 0.693 総じて Base Pruned EABase EAPruned 0.030 0.035 0.044 0.060 0.062 0.075 0.085 0.095 0.098 0.108 0.693 0.56
0.024 0.029 0.028 0.065 0.050 0.039 0.030 0.064 0.080 0.076 0.484 0.024 0.029 0.028 0.065 0.050 0.039 0.030 0.064 0.080 0.076 0.484 0.42
0.017 0.032 0.038 0.057 0.047 0.026 0.035 0.037 0.074 0.064 0.427 0.017 0.032 0.038 0.057 0.047 0.026 0.035 0.037 0.074 0.064 0.427 0.42
0.012 0.017 0.016 0.030 0.032 0.017 0.008 0.016 0.040 0.047 0.236 0.012 0.017 0.016 0.030 0.032 0.017 0.008 0.016 0.040 0.047 0.236 0.42
Table 2: The 10 fastet datasets, timings in minutes. 表2: 10のファセットデータセット、数分のタイミング。 0.79
The results presented Figure 5 are the timings over 85 datasets. 図5に示す結果は、85のデータセットのタイミングです。 0.79
We have to stress that the majority of the computation time is due to only some of the slowest datasets. 計算時間の大半は、最も遅いデータセットのほんの一部によるものであることを強調する必要がある。 0.73
The 10 slowest datasets reported Table 1 (in hours) make up for ≈ 92.29% of the Base time. テーブル1(時間内)が報告された最も遅いデータセットは、ベースタイムの92.29%を占める。 0.76
The 15 fastest datasets reported Table 2 (in minutes) confirm that EAPruned is also beneficial (it makes up for its overhead) even in these cases. テーブル2(数分)に報告された15の最速データセットでは、EAPrunedも有益である(オーバーヘッドを補っている)ことが確認されている。 0.71
4.1.1 On the Time Complexity of EAPruned 4.1.1 EAPrunedの時間複雑さについて 0.61
In Tables 1 and 2, datasets are ordered according to the Base column. テーブル 1 と 2 では、データセットは Base カラムに従って順序付けされる。 0.77
It is interesting to see that this order does not carry over to other columns. この順序が他の列に受け継がれていないことは興味深い。 0.69
For example, the second slowest dataset “UWaveGestureLibraryA ll” is more than twice slower than “FordA” with Base. たとえば、2番目に遅いデータセット「UWaveGestureLibraryA ll」は、Baseの「FordA」よりも2倍以上遅いです。 0.79
However, it becomes faster with EAPruned. しかし、EAPrunedではより速くなります。 0.79
This is due to the unpredictable nature of early abandoning and pruning. これは、早期放棄と耕作の予測不可能な性質によるものです。 0.62
The time complexity can be as low as O(1) when an implementation does not require any initialization (such as DTW’s). 実装が初期化(DTWなど)を必要としない場合、時間の複雑さはO(1)と同じくらい低くなります。 0.70
EAPruned’s time complexity can also be as high as O(L2), which is a “worst” quadratic complexity than the one from Base, due to EAPruned’s overhead. EAPrunedの時間の複雑さは、EAPrunedのオーバーヘッドのために、Baseよりも「最悪」の2次複雑さであるO(L2)と同じくらい高い場合もあります。 0.72
Time complexity under early abandoning is a moving target, sitting between the best and worst case scenarios, depending on the order of evaluation. 早期放棄時の時間の複雑さは、評価の順序に応じて、最善のシナリオと最悪のシナリオの中間に位置する、移動ターゲットである。 0.68
When performing a NN1 classification, if our first candidate is the actual nearest neighbor of a query, the average complexity will be close to O(1) (or O(L) with buffer initialization) for all following distance computations. NN1分類を行う場合、我々の最初の候補がクエリの実際の近傍である場合、平均複雑性は以下の全ての計算に対してO(1)(またはバッファ初期化を伴うO(L))に近くなる。 0.85
On the other hand, if the candidates are ordered from the furthest to the nearest, the computation will never be early abandoned, and probably not pruned much. 一方、もし候補が最下位から最寄りまで順序づけられたら、計算は決して早期に放棄されず、おそらくあまり刈り取られることはないだろう。 0.64
The average complexity will then be around O(L2). 平均的な複雑さは O(L2) の周りになる。 0.77
19 19 0.85
英語(論文から抽出)日本語訳スコア
Figure 6: CDTW Runtime (in hours) comparison over 85 datasets from the UCR Archive between Base, EABase and EAPRuned, under lb-none, lb-keogh and lb-keogh2. 図6: CDTW Runtime (数時間中) UCR Archiveから得られた85データセットの比較: Base, EABase, EAPRuned, under lb-none, lb-keogh, lb-keogh2。 0.76
Window parameters obtained from EE. EEから得られたウィンドウパラメータ。 0.78
Figure 7: DTW Runtime (in hours) comparison over 85 datasets from the UCR Archive between Base, EABase and EAPRuned, under lb-none, lb-keogh and lb-keogh2. 図7: dtwランタイム(数時間) ucrアーカイブの85以上のデータセットをbase、eabase、eapruned、lb-none、lb-keogh、lb-keogh2で比較します。
訳抜け防止モード: 図7:DTWランタイム(数時間) UCR Archiveの85データセットをBase、EABase、EAPRunedで比較します。 lb - no, lb - keogh and lb - keogh2
0.73
No parameter required. パラメータは不要です。 0.80
4.2 Comparing with Lower Bounds 4.2 下界との比較 0.76
The results obtained by EAPruned lead to ask how it behaves in the presence of lower bounding. EAPrunedによって得られた結果は、低いバウンディングの存在下でどのように振る舞うかを問う結果となった。
訳抜け防止モード: EAPruned Leadで得られた結果 下界の存在下でどのように振る舞うか尋ねます
0.64
Lower bounds early abandon even before starting a distance’s computation. 距離の計算を開始する前にも、下限は早期放棄される。 0.71
Hence EAPruned only sees the cases that could not be early abandoned, meaning it now sees a higher ratio of cases that cannot be early abandoned at all. したがって、EAPrunedは、早期に放棄できないケースのみを見ます。つまり、現在、早期に放棄できないケースの比率が高くなっています。 0.72
Under these circumstances, is EAPruned still worth it? このような状況下で、EAPrunedはまだ価値がありますか? 0.66
To study the question, we compare the results of CDTW and DTW for the Base, EABase and EAPruned versions, with no lower bound (“lb-none”), the LB-Keogh lower bound (“lb-keogh”), and cascading two applications of LB-Keogh (“lb-keogh2”, reversing their arguments as Keogh(a, b) (cid:54)= Keogh(b, a), see [18]). この問題を研究するために、ベース、EABase、EAPruned バージョンに対する CDTW と DTW の結果を比較し、下界("lb-none")、LB-Keogh の下界("lb-keogh")、LB-Keogh の2つの応用("lb-keogh2")を比較し、それらの議論を Keogh(a, b) (cid:54) = Keogh(b, a) として逆転する。 0.74
Note that LB-Keogh requires to compute the envelopes of the series. LB-ケーは級数のエンベロープを計算する必要があることに注意。 0.55
For a given run, envelopes are only computed once, keeping this overhead to a minimum. 与えられた実行では、エンベロープは一度だけ計算され、オーバーヘッドを最小限に抑える。 0.54
Moreover, envelopes are computed using the O(L) Lemire’s algorithm [13], the fastest known technique. さらに、封筒はO(L) Lemireのアルゴリズム[13]を使用して計算されます。 0.49
Figures 6 and 7 present the results respectively for CDTW and DTW. 図6と7はそれぞれCDTWとDTWの結果を示す。 0.79
The blue “lb-none” bars correspond to the Base cases presented Figure 5 (i.e. 青い「lb-none」バーは、図5に示すベースケースに対応します。 0.82
without lower bound). In the CDTW case, EAPruned without lower bound is on par against Base and EABase with lower bounds. 下限なし)。 CDTWの場合、下位境界のないEAPrunedは、下位境界を持つBaseとEABaseと同等である。 0.57
Lower bounding EAPruned then provides a ≈ 2 times speed up. より低い境界 EAPruned は 2 倍の速度を提供します。 0.76
In the DTW case, EAPruned if more than ≈ 4 times faster than the EABase with lb-keogh2, one of the fastest configurations known until now. DTWの場合、EAPは、これまで知られている最速の構成の1つであるlb-keogh2でEABaseよりも4倍以上高速であれば実行しました。 0.64
Lower bounding EAPruned still offers a ≈ 10% speedup, which is good news. ローバウンディングEAPrunedは、未だに10パーセントのスピードアップを提供しており、良いニュースです。 0.65
Indeed, an envelope computed over a window as wide as the series 実際、エンベロープは、シリーズと同じくらいの幅の窓越しに計算される 0.57
20 BaseEABaseEAPrunedlo wer bounds / mode0.00.51.01.52.0r untime in hours1.981.990.340.3 70.380.170.280.270.1 5CDTW runtime in minutes per mode and lower bound85 UCR Datasets, window parameter from EElb-nonelb-keoghlb- keogh2BaseEABaseEAPr unedlower bounds / mode0510152025runtim e in hours24.835.511.0114 .134.520.9410.544.14 0.92DTW runtime in minutes per mode and lower bound85 UCR Datasetslb-nonelb-ke oghlb-keogh2 20 BaseEABaseEAPrunedlo wer bounds / mode0.00.51.52.0runt ime in hours1.981.990.370.3 70.370.270.270.270.2 15CDTW runtime in minutes and lowerbound85 UCR Datasets, window parameters from EElb-nonelb-keoghlb- keogh2BaseEABaseEAPr unedlower bounds / mode0510152025runtim e in hours24.835.511.0114 .134.520.9410.544.14 0.92DTW runtime in minutes and lowerbound85 UCR Datasetslb-nonelb-ke oghlb-keogh2 0.63
英語(論文から抽出)日本語訳スコア
does not contain much information (see how the CDTW benefits way more from lower bounding in the Base and EABase cases than DTW). CDTWのメリットは、DTWよりもベースとEABaseのケースの低いバウンディングからはるかに多くなります)多くの情報が含まれていません。 0.70
Our results indicate that lower bounding – at least with lb-Keogh – and EAPruned complement each other. 我々の結果は、少なくとも lb-Keogh と EAPruned が相互に補うことを示す。 0.61
We explain this by the difference in the modus operandi of the two techniques. ここでは,2つの手法のモーダスオペランディの違いについて説明する。 0.68
Lower bounds have the opportunity to pre-compute some data over the series, given them an overall but approximate view. 下位境界は、全体的だが近似的な視点から、系列上のいくつかのデータを事前計算する機会を持つ。 0.58
On the other hand, EAPruned works locally, but with the exact costs. 一方、EAPrunedはローカルで動作しますが、正確なコストで動作します。 0.69
5 Conclusion In this paper, we presented how to efficiently prune and early abandon elastic distances. 5 結論 本稿では,弾性距離を効率よく削り,早期に捨てる方法について述べる。 0.70
We implemented our algorithm EAPruned for major elastic distances used by state-of-the-art ensemble classifiers, and compared the timings with existing techniques. 最新のアンサンブル分類器が使用する大きな弾性距離のアルゴリズム EAPruned を実装し,そのタイミングを既存の手法と比較した。 0.72
We show over 85 datasets from the UCR archive that in scenarios akin to NN1 classification, our algorithm is always the fastest, even in already fast cases. ucrアーカイブの85以上のデータセットを見ると、nn1分類のようなシナリオでは、すでに高速なケースであっても、アルゴリズムは常に最速です。 0.68
We also show that pruning alone can be beneficial for some distances, although caution is advised as it may be counter productive in some cases. また, 伐採だけではある程度の距離が有益であることを示すが, 反生産的である場合もあり, 注意が必要である。 0.55
Finally, we show that non only is EAPruned competitive against lower bounding alone, the two techniques actually are complementary. 最後に、非非 EAPruned 競争は下限のみであり、2 つのテクニックが相補的であることを示します。 0.70
In the lights of this results, we encourage the researcher to keep developing lower bounds, and the practitioner to use our algorithm. この結果の照らし合わせで,研究者は下限の開発を継続し,実践者はアルゴリズムの使用を奨励する。 0.71
We make the latter easy by releasing our C++ implementations with python/numpy bindings (see [6]) under the permissive MIT licence. C++実装のpython/numpyバインディング([6]を参照)を寛容なMITライセンスでリリースすることで、後者を簡単にします。 0.65
Our next steps will be to implement our algorithm for the multivariate case, and implement more lower bounds in Tempo. 我々の次のステップは、多変量の場合のアルゴリズムを実装し、テンポのより低い境界を実装することである。 0.69
We also plan to fit some ensemble classifiers such as Proximity Forest or TSChief with our distances, expecting significant speed up. また,近接林やtschiefなどのアンサンブル分類器を距離に適合させ,大幅な高速化を期待する計画である。 0.60
References [1] Anthony Bagnall, Michael Flynn, James Large, Jason Lines, and Matthew Middlehurst. 参考文献 [1]Anthony Bagnall氏、Michael Flynn氏、James Large氏、Jason Lines氏、Matthew Middlehurst氏。 0.75
A tale of two toolkits, report the third: On the usage and performance of HIVE-COTE v1.0. a tale of two toolkits, report the third: on the usage and performance of hive-cote v1.0。 0.73
arXiv:2004.06069 [cs, stat], April 2020. arXiv:2004.06069 [cs, stat], April 2020 0.96
[2] Seif-Eddine Benkabou, Khalid Benabdeslem, and Bruno Canitia. [2]Seef-Eddine Benkabou, Khalid Benabdeslem, Bruno Canitia。 0.78
Unsupervised outlier detection for time series by entropy and dynamic time warping. エントロピーおよび動的時間の反りによる時系列のためのunsupervised外の検出。 0.69
Knowledge and Information Systems, 54(2):463–486, 2018. 知識と情報システム, 54(2):463–486, 2018 0.87
[3] Lei Chen and Raymond Ng. [3]Lei ChenとRaymond Ng。 0.73
On the marriage of lp-norms and edit distance. lp-ノルムの結婚と編集距離について 0.64
In Proceedings 2004 VLDB 2004年VLDBに参加して 0.65
Conference, pages 792 – 803, 2004. カンファレンス、ページ782 - 803、2004。 0.64
[4] Hoang Anh Dau, Anthony Bagnall, Kaveh Kamgar, Chin-Chia Michael Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, and Eamonn Keogh. 4] Hoang Anh Dau、Anthony Bagnall、Kaveh Kamgar、Chin-Chia Michael Yeh、Yan Zhu、Shaghayegh Gharghabi、Chotirat Ann Ratanamahatana、Eamonn Keogh。 0.73
The UCR Time Series Archive. UCR Time Series Archiveの略。 0.84
arXiv:1810.07758 [cs, stat], September 2019. arXiv:1810.07758 [cs, stat] 2019年9月。 0.77
[5] Matthieu Herrmann. 5]Matthieu Herrmann。 0.60
Experimentation source code and ressources. ソースコードとリソースの実験。 0.86
https://github.com/H errmannM/ https://github.com/H errmannM/ 0.43
paper-2021-EAPElasti cDist, 2021. 論文2021-EAPElasticDist, 2021。 0.64
[6] Matthieu Herrmann. 6] マシュー・ヘルマン (Matthieu Herrmann)。 0.56
Tempo, the monash time series classification library. tempo, the monash time series classification library (英語) 0.81
https://github.com/ https://github.com/ 0.52
MonashTS/tempo, 2021. モナシュツ/テンポ 2021年。 0.44
[7] Daniel S. Hirschberg. Daniel S. Hirschberg. [7] Daniel S. Hirschberg. 0.62
Algorithms for the Longest Common Subsequence Problem. 最も長い共通部分列問題に対するアルゴリズム 0.73
Journal of the ACM (JACM), 24(4):664–675, October 1977. ACMの日誌 (JACM) 24(4):664-675, 1977年10月。 0.69
[8] F. Itakura. [8]F.イタクラ。 0.72
Minimum prediction residual principle applied to speech recognition. 音声認識における最小予測残差原理の適用 0.84
IEEE Transactions IEEEトランザクション 0.76
on Acoustics, Speech, and Signal Processing, 23(1):67–72, 1975. The Acoustics, Speech and Signal Processing, 23(1):67–72, 1975. 0.91
21 21 0.85
英語(論文から抽出)日本語訳スコア
[9] Young-Seon Jeong, Myong K. Jeong, and Olufemi A. Omitaomu. 9]ヨン・ジョン、ミョン・k・ジョン、オルフェミ・a・オミタオム 0.48
Weighted dynamic time warping for 重み付きダイナミックタイムワーピング。 0.70
time series classification. Pattern Recognition, 44(9):2231–2240, September 2011. 時系列分類。 パターン認識, 44(9):2231–2240, 2011年9月 0.76
[10] Eamonn Keogh and Chotirat Ann Ratanamahatana. [10]Eamonn KeoghとChotirat Ann Ratanamahatana。 0.76
Exact indexing of dynamic time warping. 動的時間の反りの正確な索引付け。 0.64
Knowl- edge and Information Systems, 7(3):358–386, 2005. 通称 edge and Information Systems, 7(3):358–386, 2005 0.67
[11] Eamonn J. Keogh and Michael J. Pazzani. 11] Eamonn J. KeoghとMichael J. Pazzani。 0.85
Derivative Dynamic Time Warping. Derivative Dynamic Time Warpingの略。 0.72
In Proceedings of the 2001 SIAM International Conference on Data Mining, pages 1–11. 2001 SIAM International Conference on Data MiningのProceedingsで、1-11ページ。 0.76
Society for Industrial and Applied Mathematics, April 2001. 工業応用数学会、2001年4月。 0.63
[12] Thomas Lampert, Thi-Bich-Hanh Dao, Baptiste Lafabregue, Nicolas Serrette, Germain Forestier, Bruno Cr´emilleux, Christel Vrain, and Pierre Gan¸carski. 12]Thomas Lampert, Thi-Bich-Hanh Dao, Baptiste Lafabregue, Nicolas Serrette, Germain Forestier, Bruno Cr ́emilleux, Christel Vrain, Pierre Gan alcarski。 0.93
Constrained distance based clustering for time-series: a comparative and experimental study. 時系列における制約付き距離ベースクラスタリング : 比較および実験的研究 0.84
Data Mining and Knowledge Discovery, 32(6):1663–1707, 2018. Data Mining and Knowledge Discovery, 32(6):1663–1707, 2018 0.89
[13] Daniel Lemire. ダニエル・レミア(Daniel Lemire)。 0.62
Faster retrieval with a two-pass dynamic-time-warping lower bound. 2パスダイナミック・タイムワープ下界による高速検索 0.63
Pattern Recognition, 42(9):2169–2180, September 2009. パターン認識。 42(9)2169-2180, 2009年9月。 0.70
[14] Jason Lines and Anthony Bagnall. 14] Jason LinesとAnthony Bagnall。 0.71
Time series classification with ensembles of elastic distance measures. 弾性距離測定のアンサンブルによる時系列分類。 0.74
Data Mining and Knowledge Discovery, 29(3):565–592, May 2015. Data Mining and Knowledge Discovery, 29(3):565–592, May 2015 0.92
[15] Jason Lines, Sarah Taylor, and Anthony Bagnall. 15] Jason Lines、Sarah Taylor、Anthony Bagnall。 0.64
Time Series Classification with HIVE-COTE: The Hierarchical Vote Collective of Transformation-Based Ensembles. HIVE-COTEによる時系列分類:変換に基づく集合の階層的投票集合。 0.76
ACM Transactions on Knowledge Discovery from Data, 12(5):1–35, July 2018. ACM Transactions on Knowledge Discovery from Data, 12(5):1–35, July 2018 0.90
[16] Benjamin Lucas, Ahmed Shifaz, Charlotte Pelletier, Lachlan O’Neill, Nayyar Zaidi, Bart Goethals, Fran¸cois Petitjean, and Geoffrey I. Webb. [16]Benjamin Lucas, Ahmed Shifaz, Charlotte Pelletier, Lachlan O’Neill, Nayyar Zaidi, Bart Goethals, Fran scois Petitjean, Geoffrey I. Webb. 0.84
Proximity Forest: An effective and scalable distance-based classifier for time series. Proximity Forest: 時系列の有効かつスケーラブルな距離ベース分類器。 0.77
Data Mining and Knowledge Discovery, 33(3):607–635, May 2019. Data Mining and Knowledge Discovery, 33(3):607–635, May 2019 0.92
[17] P.-F. Marteau. [17]p.f.マートー 0.70
Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching. 時系列マッチングのための剛性調整付きタイムワープ編集距離 0.76
IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(2):306–318, February 2009. IEEE パターン分析とマシンインテリジェンスに関するトランザクション, 31(2):306–318, February 2009 0.87
[18] Abdullah Mueen and Eamonn Keogh. 18] Abdullah MueenとEamonn Keogh。 0.69
Extracting optimal performance from dynamic time warping. 動的時間ウォーピングによる最適性能の抽出 0.79
In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’16, pages 2129–2130. 第22回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’16, page 2129–2130 に参加して 0.85
ACM Press, 2016. ACM Press、2016年。 0.90
[19] Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. [19]Tarawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, Eamonn Keogh。 0.76
Searching and mining trillions of time series subsequences under dynamic time warping. 動的時間ワーピング下での時系列のシークエンスの探索とマイニング。 0.63
In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’12, page 262, Beijing, China, 2012. 第18回ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’12, page 262, Beijing, China, 2012 に参加して 0.84
ACM Press. [20] H. Sakoe and S. Chiba. ACMプレス。 20] H.サコエとS.千葉。 0.67
Dynamic programming algorithm optimization for spoken word recognition. 音声単語認識のための動的プログラミングアルゴリズム最適化 0.86
IEEE Transactions on Acoustics, Speech, and Signal Processing, 26(1):43–49, February 1978. IEEE Transactions on Acoustics, Speech, and Signal Processing, 26(1):43–49, February 1978 0.90
[21] Hiroaki Sakoe and Seibi Chiba. [21] 佐古江弘明と千葉清美。 0.64
A dynamic programming approach to continuous speech recognition. 連続音声認識のための動的プログラミングアプローチ。 0.83
In Proceedings of the Seventh International Congress on Acoustics, Budapest, volume 3, pages 65–69, Budapest, 1971. 第7回ブダペスト国際音響会議 (Proceedings of the Seventh International Congress on Acoustics, Budapest), 巻3, 65-69, ブダペスト, 1971。 0.73
Akad´emiai Kiad´o. Akad ́emiai Kiad ́o。 0.52
[22] Stan Salvador and Philip Chan. 22] スタン・サルバドールとフィリップ・チャン。 0.62
Toward accurate dynamic time warping in linear time and space. 線形時間と空間における正確な動的時間ゆらぎ 0.70
Intelligent Data Analysis, 11(5):561–580, 2007. Intelligent Data Analysis, 11(5):561–580, 2007 0.94
[23] Sang-Wook Kim, Sanghyun Park, and W.W. Chu. 23] Sang-Wook Kim、Sanghyun Park、W.W. Chu。 0.85
An index-based approach for similarity search supporting time warping in large sequence databases. 大規模データベースにおける類似性検索支援時間ワープのための索引に基づく手法 0.69
In Proceedings 17th International Conference on Data Engineering, pages 607–614. 第17回データエンジニアリング国際会議において、607-614ページ。 0.78
IEEE Comput. IEEE コンピュート。 0.71
Soc, 2001. 2001年、soc。 0.72
22 22 0.85
英語(論文から抽出)日本語訳スコア
[24] Ahmed Shifaz, Charlotte Pelletier, Francois Petitjean, and Geoffrey I. Webb. 24] Ahmed Shifaz、Charlotte Pelletier、Francois Petitjean、Geoffrey I. Webb。 0.70
TS-CHIEF: A Scalable and Accurate Forest Algorithm for Time Series Classification. TS-CHIEF: 時系列分類のためのスケーラブルで正確な森林アルゴリズム。 0.77
arXiv:1906.10329 [cs, stat], February 2020. arXiv:1906.10329[cs, stat], February 2020 0.97
[25] Diego F. Silva and Gustavo E. A. P. A. Batista. [25] Diego F. SilvaとGustavo E. A. P. A. Batista。 0.83
Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation. 全pairwise動的時間ゆがみ行列計算の高速化 0.60
In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 837–845. 2016 SIAM International Conference on Data MiningのProceedingsで、ページ837–845。 0.78
Society for Industrial and Applied Mathematics, June 2016. 工業・応用数学会、2016年6月。 0.70
[26] Diego F. Silva, Rafael Giusti, Eamonn Keogh, and Gustavo E. A. P. A. Batista. [26] Diego F. Silva, Rafael Giusti, Eamonn Keogh, Gustavo E. A. P. A. Batista 0.94
Speeding up similarity search under dynamic time warping by pruning unpromising alignments. 妥協のないアライメントによる動的時間ワーピングによる類似検索の高速化。 0.71
Data Mining and Knowledge Discovery, 32(4):988–1016, July 2018. Data Mining and Knowledge Discovery, 32(4):988–1016, July 2018 0.89
[27] Alexandra Stefan, Vassilis Athitsos, and Gautam Das. 27]Alexandra Stefan、Vassilis Athitsos、Gautam Das。 0.50
The Move-Split-Merge Metric for Time Series. Time SeriesのMove-Split-Merge Metric。 0.75
IEEE Transactions on Knowledge and Data Engineering, 25(6):1425–1438, June 2013. IEEE Transactions on Knowledge and Data Engineering, 25(6):1425–1438, June 2013 0.91
[28] Chang Wei Tan, Matthieu Herrmann, Germain Forestier, Geoffrey I. Webb, and Fran¸cois Petitjean. [28]Chang Wei Tan、Matthieu Herrmann、Germain Forestier、Geoffrey I. Webb、Fran 'cois Petitjean。 0.76
Efficient search of the best warping window for Dynamic Time Warping. ダイナミックタイムワーピングに最適なワーピングウィンドウの効率的な検索。 0.75
In Proceedings of the 2018 SIAM International Conference on Data Mining, Philadelphia, PA, May 2018. 2018 SIAM International Conference on Data Mining, Philadelphia, PA, May 2018 に出展します。 0.75
Society for Industrial and Applied Mathematics. 産業数学と応用数学の学会。 0.76
[29] Chang Wei Tan, Fran¸cois Petitjean, and Geoffrey I. Webb. 29] チャン・ワイ・タン、フラン・シコイ・プティジャン、ジョフリー・i・ウェッブ。 0.48
FastEE: Fast ensembles of elastic distances FastEE:弾性距離の速いアンサンブル 0.73
for time series classification. Data Mining and Knowledge Discovery, 34(1):231–272, 2020. 時系列の分類です データマイニングと知識発見, 34(1):231–272, 2020 0.75
[30] Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, and Eamonn Keogh. 30]Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, Eamonn Keogh。 0.67
Experimental comparison of representation methods and distance measures for time series data. 時系列データの表現方法と距離測定の実験的比較 0.75
Data Mining and Knowledge Discovery, 26(2):275–309, 2013. データマイニングと知識発見, 26(2):275–309, 2013 0.84
[31] Renjie Wu and Eamonn J. Keogh. 31] Renjie WuとEamonn J. Keogh。 0.78
FastDTW is approximate and generally slower than the algorithm FastDTWはアルゴリズムよりも近似的で一般的に遅い 0.78
it approximates. IEEE Transactions on Knowledge and Data Engineering, pages 1–1, 2020. およそです IEEE Transactions on Knowledge and Data Engineering, page 1–1, 2020。 0.67
23 23 0.85
                                               ページの最初に戻る

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