OpenRaiser/Intern-Atlas huggingface dataset:
Individual Recognition in Schizophrenia using Deep Learning Methods with Random Forest and Voting Classifiers: Insights from Resting State EEG Streams
Venue: arXiv cs.CV 2018
Year: 2018

Recently, there has been a growing interest in monitoring brain activity for individual recognition system. So far these works are mainly focussing on single channel data or fragment data collected by some advanced brain monitoring modalities. In this study we propose new individual recognition schemes based on spatio-temporal resting state Electroencephalography (EEG) data. Besides, instead of using features derived from artificially-designed procedures, modified deep learning architectures which aim to automatically extract an individual's unique features are developed to conduct classification. Our designed deep learning frameworks are proved of a small but consistent advantage of replacing the $softmax$ layer with Random Forest. Additionally, a voting layer is added at the top of designed neural networks in order to tackle the classification problem arisen from EEG streams. Lastly, various experiments are implemented to evaluate the performance of the designed deep learning architectures; Results indicate that the proposed EEG-based individual recognition scheme yields a high degree of classification accuracy: $81.6\%$ for characteristics in high risk (CHR) individuals, $96.7\%$ for clinically stable first episode patients with schizophrenia (FES) and $99.2\%$ for healthy controls (HC).
Structure- & Physics- Preserving Reductions of Power Grid Models
Venue: arXiv cs.SY 2018
Year: 2018

The large size of multiscale, distribution and transmission, power grids hinder fast system-wide estimation and real-time control and optimization of operations. This paper studies graph reduction methods of power grids that are favorable for fast simulations and follow-up applications. While the classical Kron reduction has been successful in reduced order modeling of power grids with traditional, hierarchical design, the selection of reference nodes for the reduced model in a multiscale, distribution and transmission, network becomes ambiguous. In this work we extend the use of the iterative Kron reduction by utilizing the electric grid's graph topology for the selection of reference nodes, consistent with the design features of multiscale networks. Additionally, we propose further reductions by aggregation of coherent subnetworks of triangular meshes, based on the graph topology and network characteristics, in order to preserve currents and build another power-flow equivalent network. Our reductions are achieved through the use of iterative aggregation of sub-graphs that include general tree structures, lines, and triangles. Important features of our reduction algorithms include that: (i) the reductions are, either, equivalent to the Kron reduction, or otherwise produce a power-flow equivalent network; (ii) due to the former mentioned power-flow equivalence, the reduced network can model the dynamic of the swing equations for a lossless, inductive, steady state network; (iii) the algorithms efficiently utilize hash-tables to store the sequential reduction steps.
Robust Visual Tracking via Hierarchical Convolutional Features
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose to exploit the rich hierarchical features of deep convolutional neural networks to improve the accuracy and robustness of visual tracking. Deep neural networks trained on object recognition datasets consist of multiple convolutional layers. These layers encode target appearance with different levels of abstraction. For example, the outputs of the last convolutional layers encode the semantic information of targets and such representations are invariant to significant appearance variations. However, their spatial resolutions are too coarse to precisely localize the target. In contrast, features from earlier convolutional layers provide more precise localization but are less invariant to appearance changes. We interpret the hierarchical features of convolutional layers as a nonlinear counterpart of an image pyramid representation and explicitly exploit these multiple levels of abstraction to represent target objects. Specifically, we learn adaptive correlation filters on the outputs from each convolutional layer to encode the target appearance. We infer the maximum response of each layer to locate targets in a coarse-to-fine manner. To further handle the issues with scale estimation and re-detecting target objects from tracking failures caused by heavy occlusion or out-of-the-view movement, we conservatively learn another correlation filter, that maintains a long-term memory of target appearance, as a discriminative classifier. We apply the classifier to two types of object proposals: (1) proposals with a small step size and tightly around the estimated location for scale estimation; and (2) proposals with large step size and across the whole image for target re-detection. Extensive experimental results on large-scale benchmark datasets show that the proposed algorithm performs favorably against state-of-the-art tracking methods.
Universal Sparse Superposition Codes with Spatial Coupling and GAMP Decoding
Venue: arXiv cs.IT 2018
Year: 2018

Sparse superposition codes, or sparse regression codes, constitute a new class of codes which was first introduced for communication over the additive white Gaussian noise (AWGN) channel. It has been shown that such codes are capacity-achieving over the AWGN channel under optimal maximum-likelihood decoding as well as under various efficient iterative decoding schemes equipped with power allocation or spatially coupled constructions. Here, we generalize the analysis of these codes to a much broader setting that includes all memoryless channels. We show, for a large class of memoryless channels, that spatial coupling allows an efficient decoder, based on the generalized approximate message-passing (GAMP) algorithm, to reach the potential (or Bayes optimal) threshold of the underlying (or uncoupled) code ensemble. Moreover, we argue that spatially coupled sparse superposition codes universally achieve capacity under GAMP decoding by showing, through analytical computations, that the error floor vanishes and the potential threshold tends to capacity as one of the code parameter goes to infinity. Furthermore, we provide a closed form formula for the algorithmic threshold of the underlying code ensemble in terms of a Fisher information. Relating an algorithmic threshold to a Fisher information has theoretical as well as practical importance. Our proof relies on the state evolution analysis and uses the potential method developed in the theory of low-density parity-check (LDPC) codes and compressed sensing.
Finding Fair and Efficient Allocations
Venue: arXiv cs.GT 2018
Year: 2018

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto optimality (PO). While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare (NSW) objective is both EF1 and PO. However, the problem of maximizing NSW is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and PO; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally PO. Another contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the NSW objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al. (2017)). Unlike many of the existing approaches, our algorithm is completely combinatorial.
Block-Normalized Gradient Method: An Empirical Study for Training Deep Neural Network
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose a generic and simple strategy for utilizing stochastic gradient information in optimization. The technique essentially contains two consecutive steps in each iteration: 1) computing and normalizing each block (layer) of the mini-batch stochastic gradient; 2) selecting appropriate step size to update the decision variable (parameter) towards the negative of the block-normalized gradient. We conduct extensive empirical studies on various non-convex neural network optimization problems, including multi-layer perceptron, convolution neural networks and recurrent neural networks. The results indicate the block-normalized gradient can help accelerate the training of neural networks. In particular, we observe that the normalized gradient methods having constant step size with occasionally decay, such as SGD with momentum, have better performance in the deep convolution neural networks, while those with adaptive step sizes, such as Adam, perform better in recurrent neural networks. Besides, we also observe this line of methods can lead to solutions with better generalization properties, which is confirmed by the performance improvement over strong baselines.
On Approximating the Number of $k$-cliques in Sublinear Time
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of approximating the number of $k$-cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries and (3) pair queries. Let $n$ denote the number of vertices in the graph, $m$ the number of edges, and $C_k$ the number of $k$-cliques. We design an algorithm that outputs a $(1+\varepsilon)$-approximation (with high probability) for $C_k$, whose expected query complexity and running time are $O\left(\frac{n}{C_k^{1/k}}+\frac{m^{k/2}}{C_k}\right)\poly(\log n,1/\varepsilon,k)$. Hence, the complexity of the algorithm is sublinear in the size of the graph for $C_k = ω(m^{k/2-1})$. Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on $\log n$, $1/\varepsilon$ and $k$). The previous results in this vein are by Feige (SICOMP 06) and by Goldreich and Ron (RSA 08) for edge counting ($k=2$) and by Eden et al. (FOCS 2015) for triangle counting ($k=3$). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting, and does not generalize for larger cliques. We obtain a general algorithm that works for any $k\geq 3$ by designing a procedure that samples each $k$-clique incident to a given set $S$ of vertices with approximately equal probability. The primary difficulty is in finding cliques incident to purely high-degree vertices, since random sampling within neighbors has a low success probability. This is achieved by an algorithm that samples uniform random high degree vertices and a careful tradeoff between estimating cliques incident purely to high-degree vertices and those that include a low-degree vertex.
Speeding up the Köhler's method of contrast thresholding
Venue: arXiv cs.CV 2018
Year: 2018

K{ö}hler's method is a useful multi-thresholding technique based on boundary contrast. However, the direct algorithm has a too high complexity-O(N 2) i.e. quadratic with the pixel numbers N-to process images at a sufficient speed for practical applications. In this paper, a new algorithm to speed up K{ö}hler's method is introduced with a complexity in O(N M), M is the number of grey levels. The proposed algorithm is designed for parallelisation and vector processing , which are available in current processors, using OpenMP (Open Multi-Processing) and SIMD instructions (Single Instruction on Multiple Data). A fast implementation allows a gain factor of 405 in an image of 18 million pixels and a video processing in real time (gain factor of 96).
Lower Bounds for Searching Robots, some Faulty
Venue: arXiv cs.RO 2018
Year: 2018

Suppose we are sending out $k$ robots from $0$ to search the real line at constant speed (with turns) to find a target at an unknown location; $f$ of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most $λ|d|$, if the target is located at $d$, $|d| \ge 1$, for $λ$ as small as possible. We show that this cannot be achieved for $$λ< 2\frac{ρ^ρ}{(ρ-1)^{ρ-1}}+1,~~ ρ:= \frac{2(f+1)}{k}~, $$ which is tight due to earlier work (see J. Czyzowitz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, PODC'16, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper, we deal with the $m$-rays generalization of the problem, where the hidden target is to be detected on $m$ rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with $ρ:= m(f+1)/k$). When specialized to the case $f=0$, this resolves the question on parallel search on $m$ rays, posed by three groups of scientists some 15 to 30 years ago: by Baeza-Yates, Culberson, and Rawlins; by Kao, Ma, Sipser, and Yin; and by Bernstein, Finkelstein, and Zilberstein. The $m$-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms.
Aesthetic-Driven Image Enhancement by Adversarial Learning
Venue: arXiv cs.CV 2018
Year: 2018

We introduce EnhanceGAN, an adversarial learning based model that performs automatic image enhancement. Traditional image enhancement frameworks typically involve training models in a fully-supervised manner, which require expensive annotations in the form of aligned image pairs. In contrast to these approaches, our proposed EnhanceGAN only requires weak supervision (binary labels on image aesthetic quality) and is able to learn enhancement operators for the task of aesthetic-based image enhancement. In particular, we show the effectiveness of a piecewise color enhancement module trained with weak supervision, and extend the proposed EnhanceGAN framework to learning a deep filtering-based aesthetic enhancer. The full differentiability of our image enhancement operators enables the training of EnhanceGAN in an end-to-end manner. We further demonstrate the capability of EnhanceGAN in learning aesthetic-based image cropping without any groundtruth cropping pairs. Our weakly-supervised EnhanceGAN reports competitive quantitative results on aesthetic-based color enhancement as well as automatic image cropping, and a user study confirms that our image enhancement results are on par with or even preferred over professional enhancement.
Coordination and Control of Distributed Discrete Event Systems under Actuator and Sensor Faults
Venue: arXiv cs.SY 2018
Year: 2018

We investigate the coordination and control problems of distributed discrete event systems that are composed of multiple subsystems subject to potential actuator and/or sensor faults. We model actuator faults as local controllability loss of certain actuator events and sensor faults as observability failure of certain sensor readings, respectively. Starting from automata-theoretic models that characterize behaviors of the subsystems in the presence of faulty actuators and/or sensors, we establish necessary and sufficient conditions for the existence of actuator and sensor fault tolerant supervisors, respectively, and synthesize appropriate local post-fault supervisors to prevent the post-fault subsystems from jeopardizing local safety requirements. Furthermore, we apply an assume-guarantee coordination scheme to the controlled subsystems for both the nominal and faulty subsystems so as to achieve the desired specifications of the system. A multi-robot coordination example is used to illustrate the proposed coordination and control architecture.
Reconciling Graphs and Sets of Sets
Venue: arXiv cs.DS 2018
Year: 2018

We explore a generalization of set reconciliation, where the goal is to reconcile sets of sets. Alice and Bob each have a parent set consisting of $s$ child sets, each containing at most $h$ elements from a universe of size $u$. They want to reconcile their sets of sets in a scenario where the total number of differences between all of their child sets (under the minimum difference matching between their child sets) is $d$. We give several algorithms for this problem, and discuss applications to reconciliation problems on graphs, databases, and collections of documents. We specifically focus on graph reconciliation, providing protocols based on set of sets reconciliation for random graphs from $G(n,p)$ and for forests of rooted trees.
Weak Memory Models: Balancing Definitional Simplicity and Implementation Flexibility
Venue: arXiv cs.PL 2018
Year: 2018

The memory model for RISC-V, a newly developed open source ISA, has not been finalized yet and thus, offers an opportunity to evaluate existing memory models. We believe RISC-V should not adopt the memory models of POWER or ARM, because their axiomatic and operational definitions are too complicated. We propose two new weak memory models: WMM and WMM-S, which balance definitional simplicity and implementation flexibility differently. Both allow all instruction reorderings except overtaking of loads by a store. We show that this restriction has little impact on performance and it considerably simplifies operational definitions. It also rules out the out-of-thin-air problem that plagues many definitions. WMM is simple (it is similar to the Alpha memory model), but it disallows behaviors arising due to shared store buffers and shared write-through caches (which are seen in POWER processors). WMM-S, on the other hand, is more complex and allows these behaviors. We give the operational definitions of both models using Instantaneous Instruction Execution (I2E), which has been used in the definitions of SC and TSO. We also show how both models can be implemented using conventional cache-coherent memory systems and out-of-order processors, and encompasses the behaviors of most known optimizations.
Generic Black-Box End-to-End Attack Against State of the Art API Call Based Malware Classifiers
Venue: arXiv cs.CR 2018
Year: 2018

In this paper, we present a black-box attack against API call based machine learning malware classifiers, focusing on generating adversarial sequences combining API calls and static features (e.g., printable strings) that will be misclassified by the classifier without affecting the malware functionality. We show that this attack is effective against many classifiers due to the transferability principle between RNN variants, feed forward DNNs, and traditional machine learning classifiers such as SVM. We also implement GADGET, a software framework to convert any malware binary to a binary undetected by malware classifiers, using the proposed attack, without access to the malware source code.
Relative Pose Based Redundancy Removal: Collaborative RGB-D Data Transmission in Mobile Visual Sensor Networks
Venue: arXiv cs.RO 2018
Year: 2018

The Relative Pose based Redundancy Removal(RPRR) scheme is presented, which has been designed for mobile RGB-D sensor networks operating under bandwidth-constrained operational scenarios. Participating sensor nodes detect the redundant visual and depth information to prevent their transmission leading to a significant improvement in wireless channel usage efficiency and power savings. Experimental results show that wireless channel utilization is improved by 250% and battery consumption is halved when the RPRR scheme is used instead of sending the sensor images independently.
A class of constacyclic codes over $\mathbb{F}_{p^m}[u]/\left<u^2\right>$
Venue: arXiv cs.IT 2018
Year: 2018

Let $p$ be an odd prime, and let $m$ be a positive integer satisfying $p^m \equiv 3~(\text{mod }4).$ Let $\mathbb{F}_{p^m}$ be the finite field with $p^m$ elements, and let $R=\mathbb{F}_{p^m}[u]/\left<u^2\right>$ be the finite commutative chain ring with unity. In this paper, we determine all constacyclic codes of length $4p^s$ over $R$ and their dual codes, where $s$ is a positive integer. We also determine their sizes and list some isodual constacyclic codes of length $4p^s$ over $R.$
On the Convergence of the TTL Approximation for an LRU Cache under Independent Stationary Request Processes
Venue: arXiv cs.PF 2018
Year: 2018

The modeling and analysis of an LRU cache is extremely challenging as exact results for the main performance metrics (e.g. hit rate) are either lacking or cannot be used because of their high computational complexity for large caches. As a result, various approximations have been proposed. The state-of-the-art method is the so-called TTL approximation, first proposed and shown to be asymptotically exact for IRM requests by Fagin. It has been applied to various other workload models and numerically demonstrated to be accurate but without theoretical justification. In this paper we provide theoretical justification for the approximation in the case where distinct contents are described by independent stationary and ergodic processes. We show that this approximation is exact as the cache size and the number of contents go to infinity. This extends earlier results for the independent reference model. Moreover, we establish results not only for the aggregate cache hit probability but also for every individual content. Last, we obtain bounds on the rate of convergence.
Dynamic Bridge-Finding in $\tilde{O}(\log ^2 n)$ Amortized Time
Venue: arXiv cs.DS 2018
Year: 2018

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in $\tilde{O}((\log n)^2)$ amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in $O(\log n / \log \log n)$ worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to $\log\log n$ factors. The previous best dynamic bridge finding was an $\tilde{O}((\log n)^3)$ amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the $O((\log n)^4)$ amortized time algorithm by Holm et al.[STOC98, JACM2001]. Our approach is based on a different and purely combinatorial improvement of the algorithm of Holm et al., which by itself gives a new combinatorial $\tilde{O}((\log n)^3)$ amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed $\tilde{O}((\log n)^2)$ amortized time. Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to $\tilde{O}((\log n)^3)$. We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use $O(m + n\log n\log\log n)$. Finally, we show how to obtain $O(\log n/\log \log n)$ query time, matching the optimal trade-off between update and query time. Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.