論文の概要: Effective and Sparse Count-Sketch via k-means clustering

• arxiv url: http://arxiv.org/abs/2011.12046v2
• Date: Thu, 26 Nov 2020 06:20:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-21 13:57:02.571073
• Title: Effective and Sparse Count-Sketch via k-means clustering
• Title（参考訳）: k-meansクラスタリングによるスケッチの有効性とスパース
• Authors: Yuhan Wang, Zijian Lei, Liang Lan
• Abstract要約: 我々は,k平均クラスタリングアルゴリズムを用いて,カウントスケッチの再構成誤差を低減し,低次元スケッチ行列を得る。 6つの実生活分類データセットに基づく実験結果から,提案手法は従来のカウントスケッチよりも精度が高いことを示した。
• 参考スコア（独自算出の注目度）: 17.26941311020711
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Count-sketch is a popular matrix sketching algorithm that can produce a sketch of an input data matrix X in O(nnz(X))time where nnz(X) denotes the number of non-zero entries in X. The sketched matrix will be much smaller than X while preserving most of its properties. Therefore, count-sketch is widely used for addressing high-dimensionality challenge in machine learning. However, there are two main limitations of count-sketch: (1) The sketching matrix used count-sketch is generated randomly which does not consider any intrinsic data properties of X. This data-oblivious matrix sketching method could produce a bad sketched matrix which will result in low accuracy for subsequent machine learning tasks (e.g.classification); (2) For highly sparse input data, count-sketch could produce a dense sketched data matrix. This dense sketch matrix could make the subsequent machine learning tasks more computationally expensive than on the original sparse data X. To address these two limitations, we first show an interesting connection between count-sketch and k-means clustering by analyzing the reconstruction error of the count-sketch method. Based on our analysis, we propose to reduce the reconstruction error of count-sketch by using k-means clustering algorithm to obtain the low-dimensional sketched matrix. In addition, we propose to solve k-mean clustering using gradient descent with -L1 ball projection to produce a sparse sketched matrix. Our experimental results based on six real-life classification datasets have demonstrated that our proposed method achieves higher accuracy than the original count-sketch and other popular matrix sketching algorithms. Our results also demonstrate that our method produces a sparser sketched data matrix than other methods and therefore the prediction cost of our method will be smaller than other matrix sketching methods.
• Abstract（参考訳）: Count-sketch は、入力データ行列 X を O(nnz(X)) 時間でスケッチできる一般的な行列スケッチアルゴリズムであり、nnz(X) は X のゼロでないエントリの数を表す。 したがって、カウントスケッチは機械学習における高次元課題への対処に広く用いられている。 しかし、count-sketchの主な制限は2つある:(1)count-sketchを使用するスケッチ行列はランダムに生成され、xの固有のデータ特性を考慮しない。 この密集したスケッチマトリクスは、後の機械学習タスクを元のスパースデータxよりも計算コストが高くなる可能性がある。この2つの制限に対処するために、count-sketch法の再構成誤差を分析して、count-sketchとk-meansクラスタリングの興味深い関係を示す。 そこで本研究では,k-meansクラスタリングアルゴリズムを用いて数値スケッチの再構成誤差を低減し,低次元スケッチ行列を得る。 さらに,-L1球投射による勾配降下を用いたk平均クラスタリングの解法を提案し,スパーススケッチ行列を生成する。 6つの実生活分類データセットに基づく実験結果から,提案手法は従来のカウントスケッチや一般的な行列スケッチアルゴリズムよりも精度が高いことを示した。 また,本手法は他の手法よりもスペーサースケッチデータ行列を生成するので,提案手法の予測コストは他の手法よりも小さくなることを示す。

関連論文リスト

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。 計算のためのランダム化アルゴリズムを2つ開発した。 提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
  論文  参考訳（メタデータ） (2024-02-13T00:02:05Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。 学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-02-24T14:50:59Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Learning the Positions in CountSketch [51.15935547615698]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。 このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
  論文  参考訳（メタデータ） (2020-07-20T05:06:29Z)
• Localized sketching for matrix multiplication and ridge regression [29.61816941867831]
  局所的スケッチの新たな設定において,スケッチ化された近似行列乗法とリッジ回帰を考察する。 緩やかな条件下では、ブロック対角線スケッチ行列はO(安定ランク/エプシロン2)と$O(stat. dim. epsilon)$の値のみを必要とする。
  論文  参考訳（メタデータ） (2020-03-20T04:25:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。