OpenRaiser/Intern-Atlas huggingface dataset:
The simultaneous conjugacy problem in the symmetric group
Venue: arXiv cs.DM 2020
Year: 2020

The transitive simultaneous conjugacy problem asks whether there exists a permutation $τ\in S_n$ such that $b_j = τ^{-1} a_j τ$ holds for all $j = 1,2, \ldots, d$, where $a_1, a_2, \ldots, a_d$ and $b_1, b_2, \ldots, b_d$ are given sequences of $d$ permutations in $S_n$, each of which generates a transitive subgroup of $S_n$. As from mid 70' it has been known that the problem can be solved in $O(dn^2)$ time. An algorithm with running time $O(dn \log(dn))$, proposed in late 80', does not work correctly on all input data. In this paper we solve the transitive simultaneous conjugacy problem in $O(n^2 \log d / \log n + dn\log n)$ time and $O(n^{3/ 2} + dn)$ space. Experimental evaluation on random instances shows that the expected running time of our algorithm is considerably better, perhaps even nearly linear in $n$ at given $d$.
Total variation based community detection using a nonlinear optimization approach
Venue: arXiv cs.SI 2020
Year: 2020

Maximizing the modularity of a network is a successful tool to identify an important community of nodes. However, this combinatorial optimization problem is known to be NP-complete. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $TV_Q$ and show that its box-constrained global maximum coincides with the maximum of the original discrete modularity function. Thus we describe a new nonlinear optimization approach to solve the equivalent problem leading to a community detection strategy based on $TV_Q$. The proposed approach relies on the use of a fast first-order method that embeds a tailored active-set strategy. We report extensive numerical comparisons with standard matrix-based approaches and the Generalized RatioDCA approach for nonlinear modularity eigenvectors, showing that our new method compares favourably with state-of-the-art alternatives.
Modified swarm-based metaheuristics enhance Gradient Descent initialization performance: Application for EEG spatial filtering
Venue: arXiv cs.NE 2020
Year: 2020

Gradient Descent (GD) approximators often fail in the solution space with multiple scales of convexities, i.e., in subspace learning and neural network scenarios. To handle that, one solution is to run GD multiple times from different randomized initial states and select the best solution over all experiments. However, this idea is proved impractical in plenty of cases. Even Swarm-based optimizers like Particle Swarm Optimization (PSO) or Imperialistic Competitive Algorithm (ICA), as commonly used GD initializers, have failed to find optimal solutions in some applications. In this paper, Swarm-based optimizers like ICA and PSO are modified by a new optimization framework to improve GD optimization performance. This improvement is for applications with high number of convex localities in multiple scales. Performance of the proposed method is analyzed in a nonlinear subspace filtering objective function over EEG data. The proposed metaheuristic outperforms commonly used baseline optimizers as GD initializers in both the EEG classification accuracy and EEG loss function fitness. The optimizers have been also compared to each other in some of CEC 2014 benchmark functions, where again our method outperforms other algorithms.
Provenance Analysis for Logic and Games
Venue: arXiv cs.LO 2020
Year: 2020

A model checking computation checks whether a given logical sentence is true in a given finite structure. Provenance analysis abstracts from such a computation mathematical information on how the result depends on the atomic data that describe the structure. In database theory, provenance analysis by interpretations in commutative semirings has been rather succesful for positive query languages (such a unions of conjunctive queries, positive relational algebra, or datalog). However, it did not really offer an adequate treatment of negation or missing information. Here we propose a new approach for the provenance analysis of logics with negation, such as first-order logic and fixed-point logics. It is closely related to a provenance analysis of the associated model-checking games, and based on new semirings of dual-indeterminate polynomials or dual-indeterminate formal power series. These are obtained by taking quotients of traditional provenance semirings by congruences that are generated by products of positive and negative provenance tokens. Beyond the use for model-checking problems in logics, provenance analysis of games is of independent interest. Provenance values in games provide detailed information about the number and properties of the strategies of the players, far beyond the question whether or not a player has a winning strategy from a given position.
Achieving Super-Linear Speedup across Multi-FPGA for Real-Time DNN Inference
Venue: arXiv cs.DC 2020
Year: 2020

Real-time Deep Neural Network (DNN) inference with low-latency requirement has become increasingly important for numerous applications in both cloud computing (e.g., Apple's Siri) and edge computing (e.g., Google/Waymo's driverless car). FPGA-based DNN accelerators have demonstrated both superior flexibility and performance; in addition, for real-time inference with low batch size, FPGA is expected to achieve further performance improvement. However, the performance gain from the single-FPGA design is obstructed by the limited on-chip resource. In this paper, we employ multiple FPGAs to cooperatively run DNNs with the objective of achieving super-linear speed-up against single-FPGA design. In implementing such systems, we found two barriers that hinder us from achieving the design goal: (1) the lack of a clear partition scheme for each DNN layer to fully exploit parallelism, and (2) the insufficient bandwidth between the off-chip memory and the accelerator due to the growing size of DNNs. To tackle these issues, we propose a general framework, "Super-LIP", which can support different kinds of DNNs. In this paper, we take Convolutional Neural Network (CNN) as a vehicle to illustrate Super-LIP. We first formulate an accurate system-level model to support the exploration of best partition schemes. Then, we develop a novel design methodology to effectively alleviate the heavy loads on memory bandwidth by moving traffic from memory bus to inter-FPGA links. We implement Super-LIP based on ZCU102 FPGA boards. Results demonstrate that Super-LIP with 2 FPGAs can achieve 3.48x speedup, compared to the state-of-the-art single-FPGA design. What is more, as the number of FPGAs scales up, the system latency can be further reduced while maintaining high energy efficiency.
On the adoption, usage and evolution of Kotlin Features on Android development
Venue: arXiv cs.SE 2020
Year: 2020

Background: Google announced Kotlin as an Android official programming language in 2017, giving developers an option of writing applications using a language that combines object-oriented and functional features. Aims: The goal of this work is to understand the usage of Kotlin features considering four aspects: i) which features are adopted, ii) what is the degree of adoption, iii)when are these features added into Android applications for the first time, and iv) how the usage of features evolves along with applications' evolution. Method: Exploring the source code of 387 Android applications, we identify the usage of Kotlin features on each version application's version and compute the moment that each feature is used for the first time. Finally, we identify the evolution trend that better describes the usage of these features. Results: 15 out of 26 features are used on at least 50% of applications. Moreover, we found that type inference, lambda and safe call are the most used features. Also, we observed that the most used Kotlin features are those first included on Android applications. Finally, we report that the majority of applications tend to add more instances of 24 out of 26 features along with their evolution. {\bf Conclusions:} Our study generates 7 main findings. We present their implications, which are addressed to developers, researchers and tool builders in order to foster the use of Kotlin features to develop Android applications.
Feature Graph Learning for 3D Point Cloud Denoising
Venue: arXiv cs.CV 2020
Year: 2020

Identifying an appropriate underlying graph kernel that reflects pairwise similarities is critical in many recent graph spectral signal restoration schemes, including image denoising, dequantization, and contrast enhancement. Existing graph learning algorithms compute the most likely entries of a properly defined graph Laplacian matrix $\mathbf{L}$, but require a large number of signal observations $\mathbf{z}$'s for a stable estimate. In this work, we assume instead the availability of a relevant feature vector $\mathbf{f}_i$ per node $i$, from which we compute an optimal feature graph via optimization of a feature metric. Specifically, we alternately optimize the diagonal and off-diagonal entries of a Mahalanobis distance matrix $\mathbf{M}$ by minimizing the graph Laplacian regularizer (GLR) $\mathbf{z}^{\top} \mathbf{L} \mathbf{z}$, where edge weight is $w_{i,j} = \exp\{-(\mathbf{f}_i - \mathbf{f}_j)^{\top} \mathbf{M} (\mathbf{f}_i - \mathbf{f}_j) \}$, given a single observation $\mathbf{z}$. We optimize diagonal entries via proximal gradient (PG), where we constrain $\mathbf{M}$ to be positive definite (PD) via linear inequalities derived from the Gershgorin circle theorem. To optimize off-diagonal entries, we design a block descent algorithm that iteratively optimizes one row and column of $\mathbf{M}$. To keep $\mathbf{M}$ PD, we constrain the Schur complement of sub-matrix $\mathbf{M}_{2,2}$ of $\mathbf{M}$ to be PD when optimizing via PG. Our algorithm mitigates full eigen-decomposition of $\mathbf{M}$, thus ensuring fast computation speed even when feature vector $\mathbf{f}_i$ has high dimension. To validate its usefulness, we apply our feature graph learning algorithm to the problem of 3D point cloud denoising, resulting in state-of-the-art performance compared to competing schemes in extensive experiments.
MemNet: Memory-Efficiency Guided Neural Architecture Search with Augment-Trim learning
Venue: arXiv cs.LG 2020
Year: 2020

Recent studies on automatic neural architectures search have demonstrated significant performance, competitive to or even better than hand-crafted neural architectures. However, most of the existing network architecture tend to use residual, parallel structures and concatenation block between shallow and deep features to construct a large network. This requires large amounts of memory for storing both weights and feature maps. This is challenging for mobile and embedded devices since they may not have enough memory to perform inference with the designed large network model. To close this gap, we propose MemNet, an augment-trim learning-based neural network search framework that optimizes not only performance but also memory requirement. Specifically, it employs memory consumption based ranking score which forces an upper bound on memory consumption for navigating the search process. Experiment results show that, as compared to the state-of-the-art efficient designing methods, MemNet can find an architecture which can achieve competitive accuracy and save an average of 24.17% on the total memory needed.
Not Only Look But Observe: Variational Observation Model of Scene-Level 3D Multi-Object Understanding for Probabilistic SLAM
Venue: arXiv cs.CV 2020
Year: 2020

We present NOLBO, a variational observation model estimation for 3D multi-object from 2D single shot. Previous probabilistic instance-level understandings mainly consider the single-object image, not single shot with multi-object; relations between objects and the entire scene are out of their focus. The objectness of each observation also hardly join their model. Therefore, we propose a method to approximate the Bayesian observation model of scene-level 3D multi-object understanding. By exploiting variational auto-encoder (VAE), we estimate latent variables from the entire scene, which follow tractable distributions and concurrently imply 3D full shape and pose. To perform object-oriented data association and probabilistic simultaneous localization and mapping (SLAM), our observation models can easily be adopted to probabilistic inference by replacing object-oriented features with latent variables.
A-MAL: Automatic Movement Assessment Learning from Properly Performed Movements in 3D Skeleton Videos
Venue: arXiv cs.CV 2020
Year: 2020

The task of assessing movement quality has recently gained high demand in a variety of domains. The ability to automatically assess subject movement in videos that were captured by affordable devices, such as Kinect cameras, is essential for monitoring clinical rehabilitation processes, for improving motor skills and for movement learning tasks. The need to pay attention to low-level details while accurately tracking the movement stages, makes this task very challenging. In this work, we introduce A-MAL, an automatic, strong movement assessment learning algorithm that only learns from properly-performed movement videos without further annotations, powered by a deviation time-segmentation algorithm, a parameter relevance detection algorithm, a novel time-warping algorithm that is based on automatic detection of common temporal points-of-interest and a textual-feedback generation mechanism. We demonstrate our method on movements from the Fugl-Meyer Assessment (FMA) test, which is typically held by occupational therapists in order to monitor patients' recovery processes after strokes.
Boosting Privately: Privacy-Preserving Federated Extreme Boosting for Mobile Crowdsensing
Venue: arXiv cs.CR 2020
Year: 2020

Recently, Google and other 24 institutions proposed a series of open challenges towards federated learning (FL), which include application expansion and homomorphic encryption (HE). The former aims to expand the applicable machine learning models of FL. The latter focuses on who holds the secret key when applying HE to FL. For the naive HE scheme, the server is set to master the secret key. Such a setting causes a serious problem that if the server does not conduct aggregation before decryption, a chance is left for the server to access the user's update. Inspired by the two challenges, we propose FedXGB, a federated extreme gradient boosting (XGBoost) scheme supporting forced aggregation. FedXGB mainly achieves the following two breakthroughs. First, FedXGB involves a new HE based secure aggregation scheme for FL. By combining the advantages of secret sharing and homomorphic encryption, the algorithm can solve the second challenge mentioned above, and is robust to the user dropout. Then, FedXGB extends FL to a new machine learning model by applying the secure aggregation scheme to the classification and regression tree building of XGBoost. Moreover, we conduct a comprehensive theoretical analysis and extensive experiments to evaluate the security, effectiveness, and efficiency of FedXGB. The results indicate that FedXGB achieves less than 1% accuracy loss compared with the original XGBoost, and can provide about 23.9% runtime and 33.3% communication reduction for HE based model update aggregation of FL.
A Probabilistic Separation Logic
Venue: arXiv cs.PL 2020
Year: 2020

Probabilistic independence is a useful concept for describing the result of random sampling---a basic operation in all probabilistic languages---and for reasoning about groups of random variables. Nevertheless, existing verification methods handle independence poorly, if at all. We propose a probabilistic separation logic PSL, where separation models probabilistic independence. We first give a new, probabilistic model of the logic of bunched implications (BI). We then build a program logic based on these assertions, and prove soundness of the proof system. We demonstrate our logic by verifying information-theoretic security of cryptographic constructions for several well-known tasks, including private information retrieval, oblivious transfer, secure multi-party addition, and simple oblivious RAM. Our proofs reason purely in terms of high-level properties, like independence and uniformity.
Simple Near-Optimal Scheduling for the M/G/1
Venue: arXiv cs.PF 2020
Year: 2020

We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not have access to each job's size. Instead, we know only the job size distribution. In this setting the Gittins policy is known to minimize mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative to Gittins is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown whether or not SERPT is close to optimal for mean response time. We present a new variant of SERPT called monotonic SERPT (M-SERPT) which is as simple as SERPT but has provably near-optimal mean response time at all loads for any job size distribution. Specifically, we prove the mean response time ratio between M-SERPT and Gittins is at most 3 for load $ρ\leq 8/9$ and at most 5 for any load. This makes M-SERPT the only non-Gittins scheduling policy known to have a constant-factor approximation ratio for mean response time.
Two-hidden-layer Feedforward Neural Networks are Universal Approximators: A Constructive Approach
Venue: arXiv cs.LG 2020
Year: 2020

It is well known that Artificial Neural Networks are universal approximators. The classical result proves that, given a continuous function on a compact set on an n-dimensional space, then there exists a one-hidden-layer feedforward network which approximates the function. Such result proves the existence, but it does not provide a method for finding it. In this paper, a constructive approach to the proof of this property is given for the case of two-hidden-layer feedforward networks. This approach is based on an approximation of continuous functions by simplicial maps. Once a triangulation of the space is given, a concrete architecture and set of weights can be obtained. The quality of the approximation depends on the refinement of the covering of the space by simplicial complexes.
Minimal Solvers for Rectifying from Radially-Distorted Scales and Change of Scales
Venue: arXiv cs.CV 2020
Year: 2020

This paper introduces the first minimal solvers that jointly estimate lens distortion and affine rectification from the image of rigidly-transformed coplanar features. The solvers work on scenes without straight lines and, in general, relax strong assumptions about scene content made by the state of the art. The proposed solvers use the affine invariant that coplanar repeats have the same scale in rectified space. The solvers are separated into two groups that differ by how the equal scale invariant of rectified space is used to place constraints on the lens undistortion and rectification parameters. We demonstrate a principled approach for generating stable minimal solvers by the Gröbner basis method, which is accomplished by sampling feasible monomial bases to maximize numerical stability. Synthetic and real-image experiments confirm that the proposed solvers demonstrate superior robustness to noise compared to the state of the art. Accurate rectifications on imagery taken with narrow to fisheye field-of-view lenses demonstrate the wide applicability of the proposed method. The method is fully automatic.
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
Venue: arXiv cs.DS 2020
Year: 2020

We show that, if $\mathbf{W} \in \mathbb{R}^{N \times N}_{\mathsf{sym}}$ is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective $N^{-1} \cdot \mathbf{x}^\top \mathbf{W} \mathbf{x}$ under the constraints $x_i^2 - 1 = 0$ (i.e. $\mathbf{x} \in \{ \pm 1 \}^N$) that is asymptotically smaller than $λ_{\max}(\mathbf{W}) \approx 2$. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as $N \to \infty$, by proposing an approximate pseudomoment construction.
PingPong: Packet-Level Signatures for Smart Home Device Events
Venue: arXiv cs.NI 2020
Year: 2020

Smart home devices are vulnerable to passive inference attacks based on network traffic, even in the presence of encryption. In this paper, we present PINGPONG, a tool that can automatically extract packet-level signatures for device events (e.g., light bulb turning ON/OFF) from network traffic. We evaluated PINGPONG on popular smart home devices ranging from smart plugs and thermostats to cameras, voice-activated devices, and smart TVs. We were able to: (1) automatically extract previously unknown signatures that consist of simple sequences of packet lengths and directions; (2) use those signatures to detect the devices or specific events with an average recall of more than 97%; (3) show that the signatures are unique among hundreds of millions of packets of real world network traffic; (4) show that our methodology is also applicable to publicly available datasets; and (5) demonstrate its robustness in different settings: events triggered by local and remote smartphones, as well as by homeautomation systems.
Generative Adversarial Network for Handwritten Text
Venue: arXiv cs.LG 2020
Year: 2020

Generative adversarial networks (GANs) have proven hugely successful in variety of applications of image processing. However, generative adversarial networks for handwriting is relatively rare somehow because of difficulty of handling sequential handwriting data by Convolutional Neural Network (CNN). In this paper, we propose a handwriting generative adversarial network framework (HWGANs) for synthesizing handwritten stroke data. The main features of the new framework include: (i) A discriminator consists of an integrated CNN-Long-Short-Term- Memory (LSTM) based feature extraction with Path Signature Features (PSF) as input and a Feedforward Neural Network (FNN) based binary classifier; (ii) A recurrent latent variable model as generator for synthesizing sequential handwritten data. The numerical experiments show the effectivity of the new model. Moreover, comparing with sole handwriting generator, the HWGANs synthesize more natural and realistic handwritten text.
Modeling Winner-Take-All Competition in Sparse Binary Projections
Venue: arXiv cs.LG 2020
Year: 2020

Inspired by the advances in biological science, the study of sparse binary projection models has attracted considerable recent research attention. The models project dense input samples into a higher-dimensional space and output sparse binary data representations after the Winner-Take-All competition, subject to the constraint that the projection matrix is also sparse and binary. Following the work along this line, we developed a supervised-WTA model when training samples with both input and output representations are available, from which the optimal projection matrix can be obtained with a simple, effective yet efficient algorithm. We further extended the model and the algorithm to an unsupervised setting where only the input representation of the samples is available. In a series of empirical evaluation on similarity search tasks, the proposed models reported significantly improved results over the state-of-the-art methods in both search accuracies and running speed. The successful results give us strong confidence that the work provides a highly practical tool to real world applications.