ForestDSH: A Universal Hash Design for Discrete Probability Distributions
원문 초록
In this paper, we consider the problem of classification of $M$ high dimensional queries $y^1,\cdots,y^M\in B^S$ to $N$ high dimensional classes $x^1,\cdots,x^N\in A^S$ where $A$ and $B$ are discrete alphabets and the probabilistic model that relates data to the classes $P(x,y)$ is known. This problem has applications in various fields including the database search problem in mass spectrometry. The problem is analogous to the nearest neighbor search problem, where the goal is to find the data point in a database that is the most similar to a query point. The state of the art method for solving an approximate version of the nearest neighbor search problem in high dimensions is locality sensitive hashing (LSH). LSH is based on designing hash functions that map near points to the same buckets with a probability higher than random (far) points. To solve our high dimensional classification problem, we introduce distribution sensitive hashes that map jointly generated pairs $(x,y)\sim P$ to the same bucket with probability higher than random pairs $x\sim P^A$ and $y\sim P^B$, where $P^A$ and $P^B$ are the marginal probability distributions of $P$. We design distribution sensitive hashes using a forest of decision trees and we show that the complexity of search grows with $O(N^{\lambda^*(P)})$ where $\lambda^*(P)$ is expressed in an analytical form. We further show that the proposed hashes perform faster than state of the art approximate nearest neighbor search methods for a range of probability distributions, in both theory and simulations. Finally, we apply our method to the spectral library search problem in mass spectrometry, and show that it is an order of magnitude faster than the state of the art methods.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
EANN: Event Adversarial Neural Networks for Multi-Modal Fake News Detection
CNTK: Microsoft's Open-Source Deep-Learning Toolkit
Chainer: a Next-Generation Open Source Framework for Deep Learning
PCA of probability measures: Sparse and Dense sampling regimes
scTrilemma: 단일 세포 표현 학습에서 정체성, 불변성, 충실도의 균형 잡기
scTrilemma: Balancing Identity, Invariance, and Fidelity in Single-Cell Representation Learning
단일 세포 RNA 시퀀싱(single-cell RNA-seq) 표현 학습은 근본적으로 레이블이 없습니다(label-free). 즉, 세포 정체성(cell identity), 상태(state), 맥락(context)이 고정된 학습(training) 목표가 아니므로, 무엇이 신호(signal)이고 방해 요인(nuisance)인지는 분석 목적에 따라 달라집니다. 따라서 단일 표현은 생물학적 정체성과 상태를 보존하고, 방해 요인이 되는 맥락에 강건해야 하며, 유전자 발현 분석에 필요한 유전자 수준의 변이를 유지해야 합니다. 본 연구에서는 이 세 가지 요구 사항을 '표현 트릴레마(representation trilemma)'라고 부릅니다. 이 문제를 해결하기 위해, 모든 발현 기반 변이를 하나의 임베딩(embedding)으로 강제 통과시키는 대신 임베딩, 디코더, 사전 분포(prior)로 라우팅하는 잠재 병목 VAE인 scTrilemma를 소개합니다. scTrilemma는 단일 재구성 목표 아래에서 대상 어노테이션이나 보조 표현 손실 없이, 발현량에 따라 유전자 토큰을 게이팅하고, 세포 표현을 디코더로 라우팅하며, 레이블이 지정되지 않은 유사 벌크(pseudo-bulk) 맥락에 따라 사전 분포를 조건화합니다. 연속적인 CZ CELLxGENE Census 릴리스에 대한 릴리스 기반 제로샷(zero-shot) 평가에서, scTrilemma는 세 가지 요구 사항을 동시에 모두 선도하며 여러 질병 환경 전반에 걸쳐 생물학적 상태, 차등 발현(differential-expression) 및 경로(pathway) 구조를 보존합니다. 잠재 변수 개입(latent intervention) 실험은 다른 요구 사항에 거의 영향을 주지 않고 맥락을 제거할 수 있음을 추가로 보여주며, 정체성과 충실도 간의 관계만이 상충 관계(tension)로 남음을 입증합니다. 코드는 https://github.com/yunhak0/scTrilemma 에서 공개적으로 이용 가능합니다.
비선형 행렬 분해를 위한 교차 방향 승수법
Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions
우리는 비선형 행렬 분해(NMD)를 해결하기 위해 교차 방향 승수법(ADMM)에 기반한 알고리즘을 제시합니다. 입력 행렬 $X \in \mathbb{R}^{m \times n}$과 인수분해 랭크 $r \ll \min(m, n)$가 주어지면, NMD는 $X \approx f(WH)$를 만족하는 행렬 $W \in \mathbb{R}^{m \times r}$와 $H \in \mathbb{R}^{r \times n}$을 찾습니다. 여기서 $f$는 요소별(element-wise) 비선형 함수입니다. 우리는 음수가 아닌 희소 데이터 근사에 적합한 정류 선형 유닛(ReLU) 활성화 $f(x) = \max(0, x)$, 확률적 회로 표현에 적용 가능한 요소별 제곱 $f(x) = x^2$, 그리고 추천 시스템과 관련된 MinMax 변환 $f(x) = \min(b, \max(a, x))$를 포함하여 여러 대표적인 비선형 모델에서 우리의 방법을 평가합니다. 제안된 프레임워크는 최소제곱법(least squares), $\ell_1$ 노름, 쿨백-라이블러 발산(Kullback-Leibler divergence)을 포함한 다양한 손실(loss) 함수를 유연하게 지원하며, 다른 비선형성과 메트릭으로 쉽게 확장될 수 있습니다. 우리는 실제 데이터셋(dataset)에서 이 접근 방식의 적용 가능성, 효율성, 적응성을 입증하여 광범위한 응용 분야에 대한 잠재력을 강조합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.