OpenRaiser/Intern-Atlas huggingface dataset:
New Results for Adaptive and Approximate Counting of Inversions
Venue: arXiv cs.DS 2016
Year: 2016

Counting inversions is a classic and important problem in databases. The number of inversions, $K^*$, in a list $L=(L(1),L(2),\ldots,L(n))$ is defined as the number of pairs $i < j$ with $L(i) > L(j)$. In this paper, new results for this problem are presented: (1) In the I/O-model, an adaptive algorithm is presented for calculating $K^{*}$. The algorithm performs $O(\frac{N}{B}+ \frac{N}{B}\log_{M/B}(\frac{K^*}{NB}))$ I/Os. When $K^{*}=O(NM)$, then the algorithm takes only $O(\frac{N}{B})$ I/Os. This algorithm can be modified to match the state of the art for the comparison based model and the RAM model. (2) In the RAM model, a linear-time algorithm is presented to obtain a tight estimate of $K^*$; specifically, a value which lies with high probability in the range $[(1-\frac{\log N}{N^{1/4}})K^*,(1+\frac{\log N}{N^{1/4}})K^*]$. The state of the art linear-time algorithm works for the special case where $L$ is a permutation, i.e., each $L(i)$ is a distinct integer in the range $[1,N]$. In this paper, we handle a general case where each $L(i)$ is a real number.
Joint denoising and distortion correction of atomic scale scanning transmission electron microscopy images
Venue: arXiv cs.CV 2016
Year: 2016

Nowadays, modern electron microscopes deliver images at atomic scale. The precise atomic structure encodes information about material properties. Thus, an important ingredient in the image analysis is to locate the centers of the atoms shown in micrographs as precisely as possible. Here, we consider scanning transmission electron microscopy (STEM), which acquires data in a rastering pattern, pixel by pixel. Due to this rastering combined with the magnification to atomic scale, movements of the specimen even at the nanometer scale lead to random image distortions that make precise atom localization difficult. Given a series of STEM images, we derive a Bayesian method that jointly estimates the distortion in each image and reconstructs the underlying atomic grid of the material by fitting the atom bumps with suitable bump functions. The resulting highly non-convex minimization problems are solved numerically with a trust region approach. Well-posedness of the reconstruction method and the model behavior for faster and faster rastering are investigated using variational techniques. The performance of the method is finally evaluated on both synthetic and real experimental data.
Variations on Variants
Venue: arXiv cs.PL 2016
Year: 2016

Extensible variants improve the modularity and expressiveness of programming languages: they allow program functionality to be decomposed into independent blocks, and allow seamless extension of existing code with both new cases of existing data types and new operations over those data types. This paper considers three approaches to providing extensible variants in Haskell. Row typing is a long understood mechanism for typing extensible records and variants, but its adoption would require extension of Haskell's core type system. Alternatively, we might hope to encode extensible variants in terms of existing mechanisms, such as type classes. We describe an encoding of extensible variants using instance chains, a proposed extension of the class system. Unlike many previous encodings of extensible variants, ours does not require the definition of a new type class for each function that consumes variants. Finally, we translate our encoding to use closed type families, an existing feature of GHC. Doing so demonstrates the interpretation of instances chains and functional dependencies in closed type families. One concern with encodings like ours is how completely they match the encoded system. We compare the expressiveness of our encodings with each other and with systems based on row types. We find that, while equivalent terms are typable in each system, both encodings require explicit type annotations to resolve ambiguities in typing not present in row type systems, and the type family implementation retains more constraints in principal types than does the instance chain implementation. We propose a general mechanism to guide the instantiation of ambiguous type variables, show that it eliminates the need for type annotations in our encodings, and discuss conditions under which it preserves coherence.
YOLO9000: Better, Faster, Stronger
Venue: arXiv cs.CV 2016
Year: 2016

We introduce YOLO9000, a state-of-the-art, real-time object detection system that can detect over 9000 object categories. First we propose various improvements to the YOLO detection method, both novel and drawn from prior work. The improved model, YOLOv2, is state-of-the-art on standard detection tasks like PASCAL VOC and COCO. At 67 FPS, YOLOv2 gets 76.8 mAP on VOC 2007. At 40 FPS, YOLOv2 gets 78.6 mAP, outperforming state-of-the-art methods like Faster RCNN with ResNet and SSD while still running significantly faster. Finally we propose a method to jointly train on object detection and classification. Using this method we train YOLO9000 simultaneously on the COCO detection dataset and the ImageNet classification dataset. Our joint training allows YOLO9000 to predict detections for object classes that don't have labelled detection data. We validate our approach on the ImageNet detection task. YOLO9000 gets 19.7 mAP on the ImageNet detection validation set despite only having detection data for 44 of the 200 classes. On the 156 classes not in COCO, YOLO9000 gets 16.0 mAP. But YOLO can detect more than just 200 classes; it predicts detections for more than 9000 different object categories. And it still runs in real-time.
Large-Scale MIMO Secure Transmission with Finite Alphabet Inputs
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate secure transmission over the large-scale multiple-antenna wiretap channel with finite alphabet inputs. First, we show analytically that a generalized singular value decomposition (GSVD) based design, which is optimal for Gaussian inputs, may exhibit a severe performance loss for finite alphabet inputs in the high signal-to-noise ratio (SNR) regime. In light of this, we propose a novel Per-Group-GSVD (PG-GSVD) design which can effectively compensate the performance loss caused by the GSVD design. More importantly, the computational complexity of the PG-GSVD design is by orders of magnitude lower than that of the existing design for finite alphabet inputs in [1] while the resulting performance loss is minimal. Numerical results indicate that the proposed PG-GSVD design can be efficiently implemented in large-scale multiple-antenna systems and achieves significant performance gains compared to the GSVD design.
Network, Popularity and Social Cohesion: A Game-Theoretic Approach
Venue: arXiv cs.SI 2016
Year: 2016

In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry -- arises from the network topology of interpersonal ties between members of the group. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. A group is socially cohesive if the grand coalition is core stable. We study social cohesion in some special types of graphs and draw a link between social cohesion and the classical notion of structural cohesion. We then focus on the problem of deciding whether a given social network is socially cohesive and show that this problem is CoNP-complete. Nevertheless, we give two efficient heuristics for coalition structures where players enjoy high popularity and experimentally evaluate their performances.
Higher-order organization of complex networks
Venue: arXiv cs.SI 2016
Year: 2016

Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks---at the level of small network subgraphs---remains largely unknown. Here we develop a generalized framework for clustering networks based on higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.
Constructive Interference Based Secure Precoding: A New Dimension in Physical Layer Security
Venue: arXiv cs.IT 2016
Year: 2016

Conventionally, interference and noise are treated as catastrophic elements in wireless communications. However, it has been shown recently that exploiting known interference constructively can even contribute to signal detection ability at the receiving end. This paper exploits this concept to design artificial noise (AN) beamformers constructive to the intended receiver (IR) yet keeping AN disruptive to possible eavesdroppers (Eves). The scenario considered here is a multiple-input single-output (MISO) wiretap channel with multiple eavesdroppers. Both perfect and imperfect channel information have been considered. The main objective is to improve the receive signal-to-interference and noise ratio (SINR) at IR through exploitation of AN power in an attempt to minimize the total transmit power, while confusing the Eves. Numerical simulations demonstrate that the proposed constructive AN precoding approach yields superior performance over conventional AN schemes in terms of transmit power as well as symbol error rate (SER).
Performance and Compensation of I/Q Imbalance in Differential STBC-OFDM
Venue: arXiv cs.IT 2016
Year: 2016

Differential space time block coding (STBC) achieves full spatial diversity and avoids channel estimation overhead. Over highly frequency-selective channels, STBC is integrated with orthogonal frequency division multiplexing (OFDM) to achieve high performance. However, low-cost implementation of differential STBC-OFDM using direct-conversion transceivers is sensitive to In-phase/Quadrature-phase imbalance (IQI). In this paper, we quantify the performance impact of IQI at the receiver front-end on differential STBC-OFDM systems and propose a compensation algorithm to mitigate its effect. The proposed receiver IQI compensation works in an adaptive decision-directed manner without using known pilots or training sequences, which reduces the rate loss due to training overhead. Our numerical results show that our proposed compensation algorithm can effectively mitigate receive IQI in differential STBC-OFDM.
Monte Carlo Sort for unreliable human comparisons
Venue: arXiv cs.AI 2016
Year: 2016

Algorithms which sort lists of real numbers into ascending order have been studied for decades. They are typically based on a series of pairwise comparisons and run entirely on chip. However people routinely sort lists which depend on subjective or complex judgements that cannot be automated. Examples include marketing research; where surveys are used to learn about customer preferences for products, the recruiting process; where interviewers attempt to rank potential employees, and sporting tournaments; where we infer team rankings from a series of one on one matches. We develop a novel sorting algorithm, where each pairwise comparison reflects a subjective human judgement about which element is bigger or better. We introduce a finite and large error rate to each judgement, and we take the cost of each comparison to significantly exceed the cost of other computational steps. The algorithm must request the most informative sequence of comparisons from the user; in order to identify the correct sorted list with minimum human input. Our Discrete Adiabatic Monte Carlo approach exploits the gradual acquisition of information by tracking a set of plausible hypotheses which are updated after each additional comparison.
Parallel photonic reservoir computing using frequency multiplexing of neurons
Venue: arXiv cs.ET 2016
Year: 2016

Today's unrelenting increase in demand for information processing creates the need for novel computing concepts. Reservoir computing is such a concept that lends itself particularly well to photonic hardware implementations. Over recent years, these hardware implementations have gained maturity and now achieve state-of-the-art performance on several benchmark tasks. However, implementations so far are essentially all based on sequential data processing, leaving the inherent parallelism of photonics unexploited. Parallel implementations process all neurons simultaneously, and therefore have the potential of reducing computation time by a factor equal to the number of neurons, compared to sequential architectures. Here, we report a parallel reservoir computer that uses frequency domain multiplexing of neuron states. We illustrate its performance on standard benchmark tasks such as nonlinear channel equalization, the reproduction of a nonlinear 10th-order system, and speech recognition, obtaining error rates similar to previous optical experiments. The present experiment is thus an important step towards high speed, low footprint, all optical photonic information processing.
ASAP: Asynchronous Approximate Data-Parallel Computation
Venue: arXiv cs.DC 2016
Year: 2016

Emerging workloads, such as graph processing and machine learning are approximate because of the scale of data involved and the stochastic nature of the underlying algorithms. These algorithms are often distributed over multiple machines using bulk-synchronous processing (BSP) or other synchronous processing paradigms such as map-reduce. However, data parallel processing primitives such as repeated barrier and reduce operations introduce high synchronization overheads. Hence, many existing data-processing platforms use asynchrony and staleness to improve data-parallel job performance. Often, these systems simply change the synchronous communication to asynchronous between the worker nodes in the cluster. This improves the throughput of data processing but results in poor accuracy of the final output since different workers may progress at different speeds and process inconsistent intermediate outputs. In this paper, we present ASAP, a model that provides asynchronous and approximate processing semantics for data-parallel computation. ASAP provides fine-grained worker synchronization using NOTIFY-ACK semantics that allows independent workers to run asynchronously. ASAP also provides stochastic reduce that provides approximate but guaranteed convergence to the same result as an aggregated all-reduce. In our results, we show that ASAP can reduce synchronization costs and provides 2-10X speedups in convergence and up to 10X savings in network costs for distributed machine learning applications and provides strong convergence guarantees.
Finding Influential Institutions in Bibliographic Information Networks
Venue: arXiv cs.SI 2016
Year: 2016

Ranking in bibliographic information networks is a widely studied problem due to its many applications such as advertisement industry, funding, search engines, etc. Most of the existing works on ranking in bibliographic information network are based on ranking of research papers and their authors. But the bibliographic information network can be used for solving other important problems as well. The KDD Cup $2016$ competition considers one such problem, which is to measure the impact of research institutions, i.e. to perform ranking of research institutions. The competition took place in three phases. In this paper, we discuss our solutions for ranking institutions in each phase. We participated under team name "anu@TASL" and our solutions achieved the average NDCG@$20$ score of $0.7483$, ranking in eleventh place in the contest.
Assisting humans to achieve optimal sleep by changing ambient temperature
Venue: arXiv cs.CY 2016
Year: 2016

Environment plays a vital role in the sleep mechanism of a human. It has been shown from many studies that sleeping and waking environment, waking time and hours of sleep is of very significant importance which can result in sleeping disorders and variety of diseases. This paper finds the sleep cycle of an individual and according changes the ambient temperature to maximize his/her sleep efficiency. We suggest a method which will assist in increasing sleep efficiency. Using Fast-Fourier-Transformation (FFT) of heart rate signals to extract heart rate variability data such that low frequency / high frequency (LF/HF) power ratio we are detecting sleep stages using an automated algorithm and then applying feedback mechanism to alter the ambient temperature depending upon the sleep stage.
Role of Simplicity in Creative Behaviour: The Case of the Poietic Generator
Venue: arXiv cs.AI 2016
Year: 2016

We propose to apply Simplicity Theory (ST) to model interest in creative situations. ST has been designed to describe and predict interest in communication. Here we use ST to derive a decision rule that we apply to a simplified version of a creative game, the Poietic Generator. The decision rule produces what can be regarded as an elementary form of creativity. This study is meant as a proof of principle. It suggests that some creative actions may be motivated by the search for unexpected simplicity.
Provable learning of Noisy-or Networks
Venue: arXiv cs.LG 2016
Year: 2016

Many machine learning applications use latent variable models to explain structure in data, whereby visible variables (= coordinates of the given datapoint) are explained as a probabilistic function of some hidden variables. Finding parameters with the maximum likelihood is NP-hard even in very simple settings. In recent years, provably efficient algorithms were nevertheless developed for models with linear structures: topic models, mixture models, hidden markov models, etc. These algorithms use matrix or tensor decomposition, and make some reasonable assumptions about the parameters of the underlying model. But matrix or tensor decomposition seems of little use when the latent variable model has nonlinearities. The current paper shows how to make progress: tensor decomposition is applied for learning the single-layer {\em noisy or} network, which is a textbook example of a Bayes net, and used for example in the classic QMR-DT software for diagnosing which disease(s) a patient may have by observing the symptoms he/she exhibits. The technical novelty here, which should be useful in other settings in future, is analysis of tensor decomposition in presence of systematic error (i.e., where the noise/error is correlated with the signal, and doesn't decrease as number of samples goes to infinity). This requires rethinking all steps of tensor decomposition methods from the ground up. For simplicity our analysis is stated assuming that the network parameters were chosen from a probability distribution but the method seems more generally applicable.
Multivariate mixture model for myocardium segmentation combining multi-source images
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a method for simultaneous segmentation of multi-source images, using the multivariate mixture model (MvMM) and maximum of log-likelihood (LL) framework. The segmentation is a procedure of texture classification, and the MvMM is used to model the joint intensity distribution of the images. Specifically, the method is applied to the myocardial segmentation combining the complementary texture information from multi-sequence (MS) cardiac magnetic resonance (CMR) images. Furthermore, there exist inter-image mis-registration and intra-image misalignment of slices in the MS CMR images. Hence, the MvMM is formulated with transformations, which are embedded into the LL framework and optimized simultaneously with the segmentation parameters. The proposed method is able to correct the inter- and intra-image misalignment by registering each slice of the MS CMR to a virtual common space, as well as to delineate the indistinguishable boundaries of myocardium consisting of pathologies. Results have shown statistically significant improvement in the segmentation performance of the proposed method with respect to the conventional approaches which can solely segment each image separately. The proposed method has also demonstrated better robustness in the incongruent data, where some images may not fully cover the region of interest and the full coverage can only be reconstructed combining the images from multiple sources.
Evaluating Marijuana-Related Tweets On Twitter
Venue: arXiv cs.SI 2016
Year: 2016

This paper studies marijuana-related tweets in social network Twitter. We collected more than 300,000 marijuana related tweets during November 2016 in our study. Our text-mining based algorithms and data analysis unveil some interesting patterns including: (i) users' attitudes (e.g., positive or negative) can be characterized by the existence of outer links in a tweet; (ii) 67% users use their mobile phones to post their messages while many users publish their messages using third-party automatic posting services; and (3) the number of tweets during weekends is much higher than during weekdays. Our data also showed the impact of the political events such as the U.S. presidential election or state marijuana legalization votes on the marijuana-related tweeting frequencies.
A Basic Recurrent Neural Network Model
Venue: arXiv cs.NE 2016
Year: 2016

We present a model of a basic recurrent neural network (or bRNN) that includes a separate linear term with a slightly "stable" fixed matrix to guarantee bounded solutions and fast dynamic response. We formulate a state space viewpoint and adapt the constrained optimization Lagrange Multiplier (CLM) technique and the vector Calculus of Variations (CoV) to derive the (stochastic) gradient descent. In this process, one avoids the commonly used re-application of the circular chain-rule and identifies the error back-propagation with the co-state backward dynamic equations. We assert that this bRNN can successfully perform regression tracking of time-series. Moreover, the "vanishing and exploding" gradients are explicitly quantified and explained through the co-state dynamics and the update laws. The adapted CoV framework, in addition, can correctly and principally integrate new loss functions in the network on any variable and for varied goals, e.g., for supervised learning on the outputs and unsupervised learning on the internal (hidden) states.