OpenRaiser/Intern-Atlas huggingface dataset:
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search
Venue: arXiv cs.DS 2020
Year: 2020

We formulate and optimally solve a new generalized Set Similarity Search problem, which assumes the size of the database and query sets are known in advance. By creating polylog copies of our data-structure, we optimally solve any symmetric Approximate Set Similarity Search problem, including approximate versions of Subset Search, Maximum Inner Product Search (MIPS), Jaccard Similarity Search and Partial Match. Our algorithm can be seen as a natural generalization of previous work on Set as well as Euclidean Similarity Search, but conceptually it differs by optimally exploiting the information present in the sets as well as their complements, and doing so asymmetrically between queries and stored sets. Doing so we improve upon the best previous work: MinHash [J. Discrete Algorithms 1998], SimHash [STOC 2002], Spherical LSF [SODA 2016, 2017] and Chosen Path [STOC 2017] by as much as a factor $n^{0.14}$ in both time and space; or in the near-constant time regime, in space, by an arbitrarily large polynomial factor. Turning the geometric concept, based on Boolean supermajority functions, into a practical algorithm requires ideas from branching random walks on $\mathbb Z^2$, for which we give the first non-asymptotic near tight analysis. Our lower bounds follow from new hypercontractive arguments, which can be seen as characterizing the exact family of similarity search problems for which supermajorities are optimal. The optimality holds for among all hashing based data structures in the random setting, and by reductions, for 1 cell and 2 cell probe data structures. As a side effect, we obtain new hypercontractive bounds on the directed noise operator $T^{p_1 \to p_2}_ρ$.
Wireless resilient routing reconfiguration
Venue: arXiv cs.NI 2020
Year: 2020

Mobile wireless networks are intrinsically more prone to link congestion and outright failures than wired networks. In this paper, we elaborate the resilient routing reconfiguration method of \cite{WangEtAl} and generalize it to accomodate point-to-multipoint links and wireless networks. By reframing link failures as traffic uncertainties, this technique allows essentially instantaneous rerouting around arbitrary link failures while preventing congestion. We illustrate the technique by identifying a critical bottleneck in a realistic model wireless network.
Unwind: Interactive Fish Straightening
Venue: arXiv cs.GR 2020
Year: 2020

The ScanAllFish project is a large-scale effort to scan all the world's 33,100 known species of fishes. It has already generated thousands of volumetric CT scans of fish species which are available on open access platforms such as the Open Science Framework. To achieve a scanning rate required for a project of this magnitude, many specimens are grouped together into a single tube and scanned all at once. The resulting data contain many fish which are often bent and twisted to fit into the scanner. Our system, Unwind, is a novel interactive visualization and processing tool which extracts, unbends, and untwists volumetric images of fish with minimal user interaction. Our approach enables scientists to interactively unwarp these volumes to remove the undesired torque and bending using a piecewise-linear skeleton extracted by averaging isosurfaces of a harmonic function connecting the head and tail of each fish. The result is a volumetric dataset of a individual, straight fish in a canonical pose defined by the marine biologist expert user. We have developed Unwind in collaboration with a team of marine biologists: Our system has been deployed in their labs, and is presently being used for dataset construction, biomechanical analysis, and the generation of figures for scientific publication.
ThumbNet: One Thumbnail Image Contains All You Need for Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Although deep convolutional neural networks (CNNs) have achieved great success in computer vision tasks, its real-world application is still impeded by its voracious demand of computational resources. Current works mostly seek to compress the network by reducing its parameters or parameter-incurred computation, neglecting the influence of the input image on the system complexity. Based on the fact that input images of a CNN contain substantial redundancy, in this paper, we propose a unified framework, dubbed as ThumbNet, to simultaneously accelerate and compress CNN models by enabling them to infer on one thumbnail image. We provide three effective strategies to train ThumbNet. In doing so, ThumbNet learns an inference network that performs equally well on small images as the original-input network on large images. With ThumbNet, not only do we obtain the thumbnail-input inference network that can drastically reduce computation and memory requirements, but also we obtain an image downscaler that can generate thumbnail images for generic classification tasks. Extensive experiments show the effectiveness of ThumbNet, and demonstrate that the thumbnail-input inference network learned by ThumbNet can adequately retain the accuracy of the original-input network even when the input images are downscaled 16 times.
Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs
Venue: arXiv cs.LG 2020
Year: 2020

Knowledge graph reasoning is a critical task in natural language processing. The task becomes more challenging on temporal knowledge graphs, where each fact is associated with a timestamp. Most existing methods focus on reasoning at past timestamps and they are not able to predict facts happening in the future. This paper proposes Recurrent Event Network (RE-NET), a novel autoregressive architecture for predicting future interactions. The occurrence of a fact (event) is modeled as a probability distribution conditioned on temporal sequences of past knowledge graphs. Specifically, our RE-NET employs a recurrent event encoder to encode past facts and uses a neighborhood aggregator to model the connection of facts at the same timestamp. Future facts can then be inferred in a sequential manner based on the two modules. We evaluate our proposed method via link prediction at future times on five public datasets. Through extensive experiments, we demonstrate the strength of RENET, especially on multi-step inference over future timestamps, and achieve state-of-the-art performance on all five datasets. Code and data can be found at https://github.com/INK-USC/RE-Net.
Deep Back-Projection Networks for Single Image Super-resolution
Venue: arXiv cs.CV 2020
Year: 2020

Previous feed-forward architectures of recently proposed deep super-resolution networks learn the features of low-resolution inputs and the non-linear mapping from those to a high-resolution output. However, this approach does not fully address the mutual dependencies of low- and high-resolution images. We propose Deep Back-Projection Networks (DBPN), the winner of two image super-resolution challenges (NTIRE2018 and PIRM2018), that exploit iterative up- and down-sampling layers. These layers are formed as a unit providing an error feedback mechanism for projection errors. We construct mutually-connected up- and down-sampling units each of which represents different types of low- and high-resolution components. We also show that extending this idea to demonstrate a new insight towards more efficient network design substantially, such as parameter sharing on the projection module and transition layer on projection step. The experimental results yield superior results and in particular establishing new state-of-the-art results across multiple data sets, especially for large scaling factors such as 8x.
Multiplicative Up-Drift
Venue: arXiv cs.NE 2020
Year: 2020

Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a $(1+δ)$-multiplicative growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a simple and insightful proof of the level-based theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the best-possible near-linear dependence on $1/δ$ (the previous results had an at least near-quadratic dependence), and it only requires a population size near-linear in $δ$ (this was super-quadratic in previous results). These improvements immediately lead to stronger run time guarantees for a number of applications. We also discuss the case of large $δ$ and show stronger results for this setting.
Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning
Venue: arXiv cs.LG 2020
Year: 2020

Temporal observations such as videos contain essential information about the dynamics of the underlying scene, but they are often interleaved with inessential, predictable details. One way of dealing with this problem is by focusing on the most informative moments in a sequence. We propose a model that learns to discover these important events and the times when they occur and uses them to represent the full sequence. We do so using a hierarchical Keyframe-Inpainter (KeyIn) model that first generates a video's keyframes and then inpaints the rest by generating the frames at the intervening times. We propose a fully differentiable formulation to efficiently learn this procedure. We show that KeyIn finds informative keyframes in several datasets with different dynamics and visual properties. KeyIn outperforms other recent hierarchical predictive models for planning. For more details, please see the project website at \url{https://sites.google.com/view/keyin}.
The distribution of age-of-information performance measures for message processing systems
Venue: arXiv cs.PF 2020
Year: 2020

The idea behind the recently introduced "age of information" performance measure of a networked message processing system is that it indicates our knowledge regarding the "freshness" of the most recent piece of information that can be used as a criterion for real-time control. In this foundational paper, we examine two such measures, one that has been extensively studied in the recent literature and a new one that could be more relevant from the point of view of the processor. Considering these measures as stochastic processes in a stationary environment (defined by the arrival processes, message processing times and admission controls in bufferless systems), we characterize their distributions using the Palm inversion formula. Under renewal assumptions we derive explicit solutions for their Laplace transforms and show some interesting decomposition properties. Previous work has mostly focused on computation of expectations in very particular cases. We argue that using bufferless or very small buffer systems is best and support this by simulation. We also pose some open problems including assessment of enqueueing policies that may be better in cases where one wishes to minimize more general functionals of the age of information measures.
When does OMP achieve exact recovery with continuous dictionaries?
Venue: arXiv cs.IT 2020
Year: 2020

This paper presents new theoretical results on sparse recovery guarantees for a greedy algorithm, Orthogonal Matching Pursuit (OMP), in the context of continuous parametric dictionaries. Here, the continuous setting means that the dictionary is made up of an infinite uncountable number of atoms. In this work, we rely on the Hilbert structure of the observation space to express our recovery results as a property of the kernel defined by the inner product between two atoms. Using a continuous extension of Tropp's Exact Recovery Condition, we identify key assumptions allowing to analyze OMP in the continuous setting. Under these assumptions, OMP unambiguously identifies in exactly $k$ steps the atom parameters from any observed linear combination of $k$ atoms. These parameters play the role of the so-called support of a sparse representation in traditional sparse recovery. In our paper, any kernel and set of parameters that satisfy these conditions are said to be admissible. In the one-dimensional setting, we exhibit a family of kernels relying on completely monotone functions for which admissibility holds for any set of atom parameters. For higher dimensional parameter spaces, the analysis turns out to be more subtle. An additional assumption, so-called axis admissibility, is imposed to ensure a form of delayed recovery (in at most $k^D$ steps, where $D$ is the dimension of the parameter space). Furthermore, guarantees for recovery in exactly $k$ steps are derived under an additional algebraic condition involving a finite subset of atoms (built as an extension of the set of atoms to be recovered). We show that the latter technical conditions simplify in the case of Laplacian kernels, allowing us to derive simple conditions for $k$-step exact recovery, and to carry out a coherence-based analysis in terms of a minimum separation assumption between the atoms to be recovered.
Reconfigurable Intelligent Surface-Based Index Modulation: A New Beyond MIMO Paradigm for 6G
Venue: arXiv cs.IT 2020
Year: 2020

Transmission through reconfigurable intelligent surfaces (RISs), which control the reflection/scattering characteristics of incident waves in a deliberate manner to enhance the signal quality at the receiver, appears as a promising candidate for future wireless communication systems. In this paper, we bring the concept of RIS-assisted communications to the realm of index modulation (IM) by proposing RIS-space shift keying (RIS-SSK) and RIS-spatial modulation (RIS-SM) schemes. These two schemes are realized through not only intelligent reflection of the incoming signals to improve the reception but also utilization of the IM principle for the indices of multiple receive antennas in a clever way to improve the spectral efficiency. Maximum energy-based suboptimal (greedy) and exhaustive search-based optimal (maximum likelihood) detectors of the proposed RIS-SSK/SM schemes are formulated and a unified framework is presented for the derivation of their theoretical average bit error probability. Extensive computer simulation results are provided to assess the potential of RIS-assisted IM schemes as well as to verify our theoretical derivations. Our findings also reveal that RIS-based IM, which enables high data rates with remarkably low error rates, can become a potential candidate for future wireless communication systems in the context of beyond multiple-input multiple-output (MIMO) solutions.
Learning Spatiotemporal Features of Ride-sourcing Services with Fusion Convolutional Network
Venue: arXiv cs.LG 2020
Year: 2020

To collectively forecast the demand for ride-sourcing services in all regions of a city, the deep learning approaches have been applied with commendable results. However, the local statistical differences throughout the geographical layout of the city make the spatial stationarity assumption of the convolution invalid, which limits the performance of CNNs on the demand forecasting task. In this paper, we propose a novel deep learning framework called LC-ST-FCN (locally connected spatiotemporal fully-convolutional neural network) to address the unique challenges of the region-level demand forecasting problem within one end-to-end architecture (E2E). We first employ the 3D convolutional layers to fuse the spatial and temporal information existed in the input and then feed the spatiotemporal features extracted by the 3D convolutional layers to the subsequent 2D convolutional layers. Afterward, the prediction value of each region is obtained by the locally connected convolutional layers which relax the parameter sharing scheme. We evaluate the proposed model on a real dataset from a ride-sourcing service platform (DiDiChuxing) and observe significant improvements compared with a bunch of baseline models. Besides, we also illustrate the effectiveness of our proposed model by visualizing how different types of convolutional layers transform their input and capture useful features. The visualization results show that fully convolutional architecture enables the model to better localize the related regions. And the locally connected layers play an important role in dealing with the local statistical differences and activating useful regions.
Learning Discriminative Model Prediction for Tracking
Venue: arXiv cs.CV 2020
Year: 2020

The current strive towards end-to-end trainable computer vision systems imposes major challenges for the task of visual tracking. In contrast to most other vision problems, tracking requires the learning of a robust target-specific appearance model online, during the inference stage. To be end-to-end trainable, the online learning of the target model thus needs to be embedded in the tracking architecture itself. Due to the imposed challenges, the popular Siamese paradigm simply predicts a target feature template, while ignoring the background appearance information during inference. Consequently, the predicted model possesses limited target-background discriminability. We develop an end-to-end tracking architecture, capable of fully exploiting both target and background appearance information for target model prediction. Our architecture is derived from a discriminative learning loss by designing a dedicated optimization process that is capable of predicting a powerful model in only a few iterations. Furthermore, our approach is able to learn key aspects of the discriminative loss itself. The proposed tracker sets a new state-of-the-art on 6 tracking benchmarks, achieving an EAO score of 0.440 on VOT2018, while running at over 40 FPS. The code and models are available at https://github.com/visionml/pytracking.
Predicting Fluid Intelligence of Children using T1-weighted MR Images and a StackNet
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we utilize T1-weighted MR images and StackNet to predict fluid intelligence in adolescents. Our framework includes feature extraction, feature normalization, feature denoising, feature selection, training a StackNet, and predicting fluid intelligence. The extracted feature is the distribution of different brain tissues in different brain parcellation regions. The proposed StackNet consists of three layers and 11 models. Each layer uses the predictions from all previous layers including the input layer. The proposed StackNet is tested on a public benchmark Adolescent Brain Cognitive Development Neurocognitive Prediction Challenge 2019 and achieves a mean squared error of 82.42 on the combined training and validation set with 10-fold cross-validation. In addition, the proposed StackNet also achieves a mean squared error of 94.25 on the testing data. The source code is available on GitHub.
Point-width and Max-CSPs
Venue: arXiv cs.DS 2020
Year: 2020

The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, $β$-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms. We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) Max-CSPs, which generalises both bounded MIM-width and \b{eta}-acyclicity. On the way, we give a new characterisation of bounded MIM-width and discuss other hypergraph properties which are relevant to the complexity of Max-CSPs, such as $β$-hypertreewidth.
Speech Denoising by Accumulating Per-Frequency Modeling Fluctuations
Venue: arXiv cs.SD 2020
Year: 2020

We present a method for audio denoising that combines processing done in both the time domain and the time-frequency domain. Given a noisy audio clip, the method trains a deep neural network to fit this signal. Since the fitting is only partly successful and is able to better capture the underlying clean signal than the noise, the output of the network helps to disentangle the clean audio from the rest of the signal. This is done by accumulating a fitting score per time-frequency bin and applying the time-frequency domain filtering based on the obtained scores. The method is completely unsupervised and only trains on the specific audio clip that is being denoised. Our experiments demonstrate favorable performance in comparison to the literature methods. Our code and samples are available at github.com/mosheman5/DNP and as supplementary. Index Terms: Audio denoising; Unsupervised learning
Fast Commutative Matrix Algorithm
Venue: arXiv cs.CC 2020
Year: 2020

We show that the product of an nx3 matrix and a 3x3 matrix over a commutative ring can be computed using 6n+3 multiplications. For two 3x3 matrices this gives us an algorithm using 21 multiplications. This is an improvement with respect to Makarov's algorithm using 22 multiplications[13]. We generalize our result for nx3 and 3x3 matrices and present an algorithm for computing the product of an lxn matrix and an nxm matrix over a commutative ring for odd n using n(lm+l+m-1)/2 multiplications if m is odd and using (n(lm+l+m-1)+l-1)/2 multiplications if m is even. Waksman's and Islam's algorithm for odd n needs (n-1)(lm+l+m-1)/2+lm multiplications [10,19], thus in both cases less multiplications are required by our algorithm. We also give an algorithm for even n using n(lm+l+m-1)/2 multiplications without making use of divisions, since Waksman's and Islam's algorithm make use of some divisions by 2 [10,19]. Furthermore we present a novelty for matrix multiplication: In this paper we show that some non-bilinear algorithms with special properties can be used as recursive algorithms. In comparison to bilinear algorithms for small nxn matrices say n<20 we obtain some better results. From these non-bilinear algorithms we finally obtain approximate non-bilinear algorithms. For instance we obtain an approximate non-bilinear algorithm for 5x5 matrices that uses only 89 multiplications. If at all it is possible to compare this algorithm with a bilinear algorithm we obtain a better result with respect to Smirnov's algorithm [15].
Weakly Supervised Gaussian Networks for Action Detection
Venue: arXiv cs.CV 2020
Year: 2020

Detecting temporal extents of human actions in videos is a challenging computer vision problem that requires detailed manual supervision including frame-level labels. This expensive annotation process limits deploying action detectors to a limited number of categories. We propose a novel method, called WSGN, that learns to detect actions from \emph{weak supervision}, using only video-level labels. WSGN learns to exploit both video-specific and dataset-wide statistics to predict relevance of each frame to an action category. This strategy leads to significant gains in action detection for two standard benchmarks THUMOS14 and Charades. Our method obtains excellent results compared to state-of-the-art methods that uses similar features and loss functions on THUMOS14 dataset. Similarly, our weakly supervised method is only 0.3% mAP behind a state-of-the-art supervised method on challenging Charades dataset for action localization.