論文の概要: Metricizing the Euclidean Space towards Desired Distance Relations in
Point Clouds
- arxiv url: http://arxiv.org/abs/2211.03674v1
- Date: Mon, 7 Nov 2022 16:37:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 18:59:08.435963
- Title: Metricizing the Euclidean Space towards Desired Distance Relations in
Point Clouds
- Title(参考訳): 点雲の所望距離関係へのユークリッド空間の計量化
- Authors: Stefan Rass, Sandra K\"onig, Shahzad Ahmad, Maksim Goman
- Abstract要約: 我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。
クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
- 参考スコア(独自算出の注目度): 1.2366208723499545
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of points in the Euclidean space $\mathbb{R}^\ell$ with $\ell>1$,
the pairwise distances between the points are determined by their spatial
location and the metric $d$ that we endow $\mathbb{R}^\ell$ with. Hence, the
distance $d(\mathbf x,\mathbf y)=\delta$ between two points is fixed by the
choice of $\mathbf x$ and $\mathbf y$ and $d$. We study the related problem of
fixing the value $\delta$, and the points $\mathbf x,\mathbf y$, and ask if
there is a topological metric $d$ that computes the desired distance $\delta$.
We demonstrate this problem to be solvable by constructing a metric to
simultaneously give desired pairwise distances between up to $O(\sqrt\ell)$
many points in $\mathbb{R}^\ell$. We then introduce the notion of an
$\varepsilon$-semimetric $\tilde{d}$ to formulate our main result: for all
$\varepsilon>0$, for all $m\geq 1$, for any choice of $m$ points $\mathbf
y_1,\ldots,\mathbf y_m\in\mathbb{R}^\ell$, and all chosen sets of values
$\{\delta_{ij}\geq 0: 1\leq i<j\leq m\}$, there exists an
$\varepsilon$-semimetric $\tilde{\delta}:\mathbb{R}^\ell\times
\mathbb{R}^\ell\to\mathbb{R}$ such that $\tilde{d}(\mathbf y_i,\mathbf
y_j)=\delta_{ij}$, i.e., the desired distances are accomplished, irrespectively
of the topology that the Euclidean or other norms would induce. We showcase our
results by using them to attack unsupervised learning algorithms, specifically
$k$-Means and density-based (DBSCAN) clustering algorithms. These have manifold
applications in artificial intelligence, and letting them run with externally
provided distance measures constructed in the way as shown here, can make
clustering algorithms produce results that are pre-determined and hence
malleable. This demonstrates that the results of clustering algorithms may not
generally be trustworthy, unless there is a standardized and fixed prescription
to use a specific distance function.
- Abstract(参考訳): ユークリッド空間 $\mathbb{r}^\ell$ with $\ell>1$ の点の集合が与えられると、それらの点の間の対距離は、その空間的位置と、$\mathbb{r}^\ell$ with を与える計量 $d$ によって決定される。
したがって、2つの点の間の距離 $d(\mathbf x,\mathbf y)=\delta$ は、$\mathbf x$ と $\mathbf y$ と $d$ の選択によって固定される。
我々は、値 $\delta$ と点 $\mathbf x,\mathbf y$ を固定する関連する問題を研究し、所望距離 $\delta$ を計算する位相計量 $d$ が存在するかどうかを問う。
この問題は、最大$o(\sqrt\ell)$ の点間の所望の対距離を$\mathbb{r}^\ell$ で同時に与えるメトリックを構築して解くことができることを示した。
We then introduce the notion of an $\varepsilon$-semimetric $\tilde{d}$ to formulate our main result: for all $\varepsilon>0$, for all $m\geq 1$, for any choice of $m$ points $\mathbf y_1,\ldots,\mathbf y_m\in\mathbb{R}^\ell$, and all chosen sets of values $\{\delta_{ij}\geq 0: 1\leq i<j\leq m\}$, there exists an $\varepsilon$-semimetric $\tilde{\delta}:\mathbb{R}^\ell\times \mathbb{R}^\ell\to\mathbb{R}$ such that $\tilde{d}(\mathbf y_i,\mathbf y_j)=\delta_{ij}$, i.e., the desired distances are accomplished, irrespectively of the topology that the Euclidean or other norms would induce.
本稿では,教師なし学習アルゴリズム,具体的には$k$-Means and density-based clustering algorithm(DBSCAN)に対する攻撃効果を示す。
これらには人工知能における多様体的応用があり、以下に示すように、外部から提供される距離測度で実行させることで、クラスタアルゴリズムが事前に決定され、従って可鍛性を持つ結果を生成することができる。
このことはクラスタリングアルゴリズムの結果が、特定の距離関数を使用するための標準化された固定された処方令がない限り、一般的には信頼できないことを示している。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳(メタデータ) (2023-10-02T16:44:47Z) - For Kernel Range Spaces a Constant Number of Queries Are Sufficient [13.200502573462712]
カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。
Anvarepsilon$-cover は点 $Q の部分集合 mathbbRd$ for any $p in mathbbRd$ that $frac1n |R_p - R_q|leq varepsilon$ for some $q in Q$ の部分集合である。
論文 参考訳(メタデータ) (2023-06-28T19:19:33Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Locally Private $k$-Means Clustering with Constant Multiplicative
Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。
局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文 参考訳(メタデータ) (2021-05-31T14:41:40Z) - Approximating the Riemannian Metric from Point Clouds via Manifold
Moving Least Squares [2.2774471443318753]
近似測地線距離を収束率$ O(h) $ provable approximations で生成するネーブアルゴリズムを提案する。
いくつかの数値シミュレーションにおいて,提案手法の雑音に対するポテンシャルとロバスト性を示す。
論文 参考訳(メタデータ) (2020-07-20T04:42:17Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳(メタデータ) (2020-05-22T16:55:01Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳(メタデータ) (2020-03-09T13:30:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。