02/02/2021

Accelerated Combinatorial Search for Outlier Detection with Provable Bound on Sub-Optimality

Guihong Wan, Haim Schweitzer

Keywords:

Abstract Paper Similar Papers

Abstract: Outliers negatively affect the accuracy of data analysis. In this paper we are concerned with their influence on the accuracy of Principal Component Analysis (PCA). Algorithms that attempt to detect outliers and remove them from the data prior to applying PCA are sometimes called Robust PCA, or Robust Subspace Recovery algorithms. We propose a new algorithm for outlier detection that combines two ideas. The first is "chunk recursive elimination" that was used effectively to accelerate feature selection, and the second is combinatorial search, in a setting similar to A*. Our main result is showing how to combine these two ideas. One variant of our algorithm is guaranteed to compute an optimal solution according to some natural criteria, but its running time makes it impractical for large datasets. Other variants are much faster and come with provable bounds on sub-optimality. Experimental results show the effectiveness of the proposed approach.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948160
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:34 
 0
 0
 0
 0
 9:55 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 10:53 
 0
 0
 0
 0
 5:47 
 0
 0
 0
 0
 11:28 
 0
 0
 0
 0
 10:27 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 15:32 
 0
 0
 0
 0
 14:30 
 0
 0
 0
 0
 15:11 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 9:26 
 0
 0
 0
 0
 9:08 
 0
 0
 0
 0
 12:40 
 0
 0
 0
 0
 17:42 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 20:11 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 20:05 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 13:51 
 0
 0
 0
 0
 17:01 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 2:48 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 13:19 
 0
 0
 0
 0
 13:57 
 0
 0
 0
 0
 5:13 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 15:47 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 9:41 
 0
 0
 0
 0
 2:57 
 0
 0
 0
 0
 8:43