OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Parallel Algorithms for k-Center Clustering
Venue: arXiv cs.DC 2016
Year: 2016

The k-center problem is one of several classic NP-hard clustering questions. For contemporary massive data sets, RAM-based algorithms become impractical. And although there exist good sequential algorithms for k-center, they are not easily parallelizable. In this paper, we design and implement parallel approximation algorithms for this problem. We observe that Gonzalez's greedy algorithm can be efficiently parallelized in several MapReduce rounds; in practice, we find that two rounds are sufficient, leading to a 4-approximation. We contrast this with an existing parallel algorithm for k-center that runs in a constant number of rounds, and offers a 10-approximation. In depth runtime analysis reveals that this scheme is often slow, and that its sampling procedure only runs if k is sufficiently small, relative to the input size. To trade off runtime for approximation guarantee, we parameterize this sampling algorithm, and find in our experiments that the algorithm is not only faster, but sometimes more effective. Yet the parallel version of Gonzalez is about 100 times faster than both its sequential version and the parallel sampling algorithm, barely compromising solution quality.
Online Learning of Portfolio Ensembles with Sector Exposure Regularization
Venue: arXiv cs.LG 2016
Year: 2016

We consider online learning of ensembles of portfolio selection algorithms and aim to regularize risk by encouraging diversification with respect to a predefined risk-driven grouping of stocks. Our procedure uses online convex optimization to control capital allocation to underlying investment algorithms while encouraging non-sparsity over the given grouping. We prove a logarithmic regret for this procedure with respect to the best-in-hindsight ensemble. We applied the procedure with known mean-reversion portfolio selection algorithms using the standard GICS industry sector grouping. Empirical Experimental results showed an impressive percentage increase of risk-adjusted return (Sharpe ratio).
Spectral Efficient Communications employing 1-Bit Quantization and Oversampling at the Receiver
Venue: arXiv cs.IT 2016
Year: 2016

To relax power consumption requirements in multigigabit/s communications systems low resolution quantization can be used. Information-theoretic results have shown that systems employing 1-bit quantization and oversampling are a viable option for this. This work investigates such a structure under the influence of additive Gaussian noise and two matched pulse shaping filters. It is described how a BCJR algorithm, based on a finite-state channel assumption, can be used to reconstruct symbols of higher order modulation schemes that allow the transmission of more than one bit per symbol. Furthermore, it is shown how symbol sources that are fitted to the 1-bit constraint can significantly improve the error rate performance of the system.
Applying Ontological Modeling on Quranic Nature Domain
Venue: arXiv cs.AI 2016
Year: 2016

The holy Quran is the holy book of the Muslims. It contains information about many domains. Often people search for particular concepts of holy Quran based on the relations among concepts. An ontological modeling of holy Quran can be useful in such a scenario. In this paper, we have modeled nature related concepts of holy Quran using OWL (Web Ontology Language) / RDF (Resource Description Framework). Our methodology involves identifying nature related concepts mentioned in holy Quran and identifying relations among those concepts. These concepts and relations are represented as classes/instances and properties of an OWL ontology. Later, in the result section it is shown that, using the Ontological model, SPARQL queries can retrieve verses and concepts of interest. Thus, this modeling helps semantic search and query on the holy Quran. In this work, we have used English translation of the holy Quran by Sahih International, Protege OWL Editor and for querying we have used SPARQL.
Mitigating selfish primary user emulation attacks in multi-channel cognitive radio networks: A surveillance game
Venue: arXiv cs.GT 2016
Year: 2016

Primary User Emulation Attack (PUEA), in which attackers emulate primary user signals causing restriction of secondary access on the attacked channels, is a serious security problem in Cognitive Radio Networks (CRNs). An user performing a PUEA for selfishly occupying more channels is called a selfish PUEA attacker. Network managers could adopt a surveillance process on disallowed channels for identifying illegal channel occupation of selfish PUEA attackers and hence mitigating selfish PUEA. Determining surveillance strategies, particularly in multi-channel context, is necessary for ensuring network operation fairness. In this paper, we formulate a game, called multi-channel surveillance game, between the selfish attack and the surveillance process in multi-channel CRNs. The sequence-form representation method is adopted to determine the Nash Equilibrium (NE) of the game. We show that performing the obtained NE surveillance strategy significantly mitigates selfish PUEA.
An incremental linear-time learning algorithm for the Optimum-Path Forest classifier
Venue: arXiv cs.LG 2016
Year: 2016

We present a classification method with incremental capabilities based on the Optimum-Path Forest classifier (OPF). The OPF considers instances as nodes of a fully-connected training graph, arc weights represent distances between two feature vectors. Our algorithm includes new instances in an OPF in linear-time, while keeping similar accuracies when compared with the original quadratic-time model.
Network Formation Game with Different Cost Value for Players
Venue: arXiv cs.GT 2016
Year: 2016

In Social Networks, it is often interesting to study type of networks formed, its efficiency with respect to social objective and which networks are stable. Many work have already been there in this area. Players in network formation game will incur some cost to form a link. In previous work, all player will have same cost for forming a link int he network. Here we will the study the optimal network and Nash equilibrium network when each player have different cost value for forming the link in the social network.
A Summary of Team MIT's Approach to the Amazon Picking Challenge 2015
Venue: arXiv cs.RO 2016
Year: 2016

The Amazon Picking Challenge (APC), held alongside the International Conference on Robotics and Automation in May 2015 in Seattle, challenged roboticists from academia and industry to demonstrate fully automated solutions to the problem of picking objects from shelves in a warehouse fulfillment scenario. Packing density, object variability, speed, and reliability are the main complexities of the task. The picking challenge serves both as a motivation and an instrument to focus research efforts on a specific manipulation problem. In this document, we describe Team MIT's approach to the competition, including design considerations, contributions, and performance, and we compile the lessons learned. We also describe what we think are the main remaining challenges.
A Differentiable Transition Between Additive and Multiplicative Neurons
Venue: arXiv cs.LG 2016
Year: 2016

Existing approaches to combine both additive and multiplicative neural units either use a fixed assignment of operations or require discrete optimization to determine what function a neuron should perform. However, this leads to an extensive increase in the computational complexity of the training procedure. We present a novel, parameterizable transfer function based on the mathematical concept of non-integer functional iteration that allows the operation each neuron performs to be smoothly and, most importantly, differentiablely adjusted between addition and multiplication. This allows the decision between addition and multiplication to be integrated into the standard backpropagation training procedure.
Reversible Image Merging for Low-level Machine Vision
Venue: arXiv cs.CV 2016
Year: 2016

In this paper a hierarchical model for pixel clustering and image segmentation is developed. In the model an image is hierarchically structured. The original image is treated as a set of nested images, which are capable to reversibly merge with each other. An object is defined as a structural element of an image, so that, an image is regarded as a maximal object. The simulating of none-hierarchical optimal pixel clustering by hierarchical clustering is studied. To generate a hierarchy of optimized piecewise constant image approximations, estimated by the standard deviation of approximation from the image, the conversion of any hierarchy of approximations into the hierarchy described in relation to the number of intensity levels by convex sequence of total squared errors is proposed.
Maximum Entropy Functions: Approximate Gacs-Korner for Distributed Compression
Venue: arXiv cs.IT 2016
Year: 2016

Consider two correlated sources $X$ and $Y$ generated from a joint distribution $p_{X,Y}$. Their Gács-Körner Common Information, a measure of common information that exploits the combinatorial structure of the distribution $p_{X,Y}$, leads to a source decomposition that exhibits the latent common parts in $X$ and $Y$. Using this source decomposition we construct an efficient distributed compression scheme, which can be efficiently used in the network setting as well. Then, we relax the combinatorial conditions on the source distribution, which results in an efficient scheme with a helper node, which can be thought of as a front-end cache. This relaxation leads to an inherent trade-off between the rate of the helper and the rate reduction at the sources, which we capture by a notion of optimal decomposition. We formulate this as an approximate Gács-Körner optimization. We then discuss properties of this optimization, and provide connections with the maximal correlation coefficient, as well as an efficient algorithm, both through the application of spectral graph theory to the induced bipartite graph of $p_{X,Y}$.
The Effect of Distortions on the Prediction of Visual Attention
Venue: arXiv cs.CV 2016
Year: 2016

Existing saliency models have been designed and evaluated for predicting the saliency in distortion-free images. However, in practice, the image quality is affected by a host of factors at several stages of the image processing pipeline such as acquisition, compression and transmission. Several studies have explored the effect of distortion on human visual attention; however, none of them have considered the performance of visual saliency models in the presence of distortion. Furthermore, given that one potential application of visual saliency prediction is to aid pooling of objective visual quality metrics, it is important to compare the performance of existing saliency models on distorted images. In this paper, we evaluate several state-of-the-art visual attention models over different databases consisting of distorted images with various types of distortions such as blur, noise and compression with varying levels of distortion severity. This paper also introduces new improved performance evaluation metrics that are shown to overcome shortcomings in existing performance metrics. We find that the performance of most models improves with moderate and high levels of distortions as compared to the near distortion-free case. In addition, model performance is also found to decrease with an increase in image complexity.
Inverse Reinforcement Learning with Simultaneous Estimation of Rewards and Dynamics
Venue: arXiv cs.AI 2016
Year: 2016

Inverse Reinforcement Learning (IRL) describes the problem of learning an unknown reward function of a Markov Decision Process (MDP) from observed behavior of an agent. Since the agent's behavior originates in its policy and MDP policies depend on both the stochastic system dynamics as well as the reward function, the solution of the inverse problem is significantly influenced by both. Current IRL approaches assume that if the transition model is unknown, additional samples from the system's dynamics are accessible, or the observed behavior provides enough samples of the system's dynamics to solve the inverse problem accurately. These assumptions are often not satisfied. To overcome this, we present a gradient-based IRL approach that simultaneously estimates the system's dynamics. By solving the combined optimization problem, our approach takes into account the bias of the demonstrations, which stems from the generating policy. The evaluation on a synthetic MDP and a transfer learning task shows improvements regarding the sample efficiency as well as the accuracy of the estimated reward functions and transition models.
Beamforming for Simultaneous Wireless Information and Power Transfer in Two-Way Relay Channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies simultaneous wireless information and power transfer (SWIPT) systems in two-way relaying (TWR) channels. Here, two source nodes receive information and energy simultaneously via power splitting (PS) from the signals sent by a multi-antenna relay node. Our objective is to maximize the weighted sum of the harvested energy at two source nodes subject to quality of service (QoS) constraints and the relay power constraints. Three well-known and practical two-way relay strategies are considered, i.e., amplify-and-forward (AF), bit level XOR based decode-and-forward (DF-XOR) and symbol level superposition coding based DF (DF-SUP). For each relaying strategy, we formulate the joint energy transmit beamforming and PS ratios optimization as a nonconvex quadratically constrained problem. To find a closed-form solution of the formulated problem, we decouple the primal problem into two subproblems. In the first problem, we intend to optimize beamforming vector for a given PS ratio. In the second subproblem, we optimize the PS ratio with a given beamforming vector. It is worth noting that although the corresponding subproblem are nonconvex, the optimal solution of each subproblem can still be found by using certain techniques. We provide numerical results that demonstrate the advantage of adapting the different relaying strategies and weighted factors to harvest energy in two-way relaying channel.
Towards Automated Melanoma Screening: Proper Computer Vision & Reliable Results
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we survey, analyze and criticize current art on automated melanoma screening, reimplementing a baseline technique, and proposing two novel ones. Melanoma, although highly curable when detected early, ends as one of the most dangerous types of cancer, due to delayed diagnosis and treatment. Its incidence is soaring, much faster than the number of trained professionals able to diagnose it. Automated screening appears as an alternative to make the most of those professionals, focusing their time on the patients at risk while safely discharging the other patients. However, the potential of automated melanoma diagnosis is currently unfulfilled, due to the emphasis of current literature on outdated computer vision models. Even more problematic is the irreproducibility of current art. We show how streamlined pipelines based upon current Computer Vision outperform conventional models - a model based on an advanced bags of words reaches an AUC of 84.6%, and a model based on deep neural networks reaches 89.3%, while the baseline (a classical bag of words) stays at 81.2%. We also initiate a dialog to improve reproducibility in our community
Deep Feature Based Contextual Model for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

Object detection is one of the most active areas in computer vision, which has made significant improvement in recent years. Current state-of-the-art object detection methods mostly adhere to the framework of regions with convolutional neural network (R-CNN) and only use local appearance features inside object bounding boxes. Since these approaches ignore the contextual information around the object proposals, the outcome of these detectors may generate a semantically incoherent interpretation of the input image. In this paper, we propose an ensemble object detection system which incorporates the local appearance, the contextual information in term of relationships among objects and the global scene based contextual feature generated by a convolutional neural network. The system is formulated as a fully connected conditional random field (CRF) defined on object proposals and the contextual constraints among object proposals are modeled as edges naturally. Furthermore, a fast mean field approximation method is utilized to inference in this CRF model efficiently. The experimental results demonstrate that our approach achieves a higher mean average precision (mAP) on PASCAL VOC 2007 datasets compared to the baseline algorithm Faster R-CNN.
Filling in the details: Perceiving from low fidelity images
Venue: arXiv cs.CV 2016
Year: 2016

Humans perceive their surroundings in great detail even though most of our visual field is reduced to low-fidelity color-deprived (e.g. dichromatic) input by the retina. In contrast, most deep learning architectures are computationally wasteful in that they consider every part of the input when performing an image processing task. Yet, the human visual system is able to perform visual reasoning despite having only a small fovea of high visual acuity. With this in mind, we wish to understand the extent to which connectionist architectures are able to learn from and reason with low acuity, distorted inputs. Specifically, we train autoencoders to generate full-detail images from low-detail "foveations" of those images and then measure their ability to reconstruct the full-detail images from the foveated versions. By varying the type of foveation, we can study how well the architectures can cope with various types of distortion. We find that the autoencoder compensates for lower detail by learning increasingly global feature functions. In many cases, the learnt features are suitable for reconstructing the original full-detail image. For example, we find that the networks accurately perceive color in the periphery, even when 75\% of the input is achromatic.
Learning to Generate Genotypes with Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

Neural networks and evolutionary computation have a rich intertwined history. They most commonly appear together when an evolutionary algorithm optimises the parameters and topology of a neural network for reinforcement learning problems, or when a neural network is applied as a surrogate fitness function to aid the evolutionary optimisation of expensive fitness functions. In this paper we take a different approach, asking the question of whether a neural network can be used to provide a mutation distribution for an evolutionary algorithm, and what advantages this approach may offer? Two modern neural network models are investigated, a Denoising Autoencoder modified to produce stochastic outputs and the Neural Autoregressive Distribution Estimator. Results show that the neural network approach to learning genotypes is able to solve many difficult discrete problems, such as MaxSat and HIFF, and regularly outperforms other evolutionary techniques.
Analysis of Interference Correlation in Non-Poisson Networks
Venue: arXiv cs.IT 2016
Year: 2016

The correlation of interference has been well quantified in Poisson networks where the interferers are independent of each other. However, there exists dependence among the base stations (BSs) in wireless networks. In view of this, we quantify the interference correlation in non-Poisson networks where the interferers are distributed as a Matern cluster process (MCP) and a second-order cluster process (SOCP). Interestingly, it is found that the correlation coefficient of interference for the Matern cluster networks, $ζ_{MCP}$, is equal to that for second-order cluster networks, $ζ_{SOCP}$. Furthermore, they are greater than their counterpart for the Poisson networks. This shows that clustering in interferers enhances the interference correlation. In addition, we show that the correlation coefficients $ζ_{MCP}$ and $ζ_{SOCP}$ increase as the average number of points in each cluster, $c$, grows, but decrease with the increase in the cluster radius, $R$. More importantly, we point that the effects of clustering on interference correlation can be neglected as $\frac{c}{π^{2}R^{2}}\rightarrow0$. Finally, the analytical results are validated by simulations.
Topological Self-Stabilization with Name-Passing Process Calculi
Venue: arXiv cs.LO 2016
Year: 2016

Topological self-stabilization describes the ability of a distributed system to let the nodes themselves establish a meaningful overlay network. Independent from the initial network topology, the system converges to the desired topology via forwarding, inserting, and deleting links to neighboring nodes. Name-passing process calculi, like the pi-calculus, are a well-known and widely used method to model concurrent and distributed algorithms. The pi-calculus is designed to naturally express processes with a changing link infrastructure, as the communication between processes may carry information that can be used for a change in the linkage between the processes. We redesign a simple local linearization algorithm with asynchronous message-passing that was originally designed for a shared memory model. We use an extended localized pi-calculus, a variant of the pi-calculus, to model the algorithm. Subsequently, we formally prove the self-stabilizing properties closure, weak convergence for every arbitrary initial configuration, and strong convergence for two special cases. In our proofs we utilize rather an assertional reasoning than an action-based style. Furthermore, we describe the challenges in proving (strong) convergence in the general case. Additionally, we give strong arguments for strong convergence, supported by further proven lemmata, and discuss different approaches for a formal proof.
A New Method of Verification of Functional Programs
Venue: arXiv cs.LO 2016
Year: 2016

In the paper the problem of verification of functional programs (FPs) over strings is considered, where specifications of properties of FPs are defined by other FPs, and a FP S1 meets a specification defined by another FP S2 iff a composition of functions defined by the FPs S1 and S2 is equal to the constant 1. We introduce a concept of a state diagram of a FP, and reduce the verification problem to the problem of an analysis of the state diagrams of FPs. The proposed approach is illustrated by the example of verification of a sorting program.
Hypothetical Problems concerning the Theory of Relativity on Cryptographic Currency Implementations
Venue: arXiv cs.CR 2016
Year: 2016

Bitcoin has demonstrated there are many security improvements applicable to normal currency. As the human race expands and we colonize other planets, we have to consider how we are going to extend integral parts of of society, and that includes our currency system. Information transferring does not scale well with very large distances, entirely due to physical limitations. For example, there is a maximum speed that any information can travel, and it cannot be faster than the speed of light. In this paper we take these physical limitations into account to give treatment to the following question. Can a single crypto-currency be used across the entire universe? Trivially many currencies can be used with exchange rates but we will try to avoid this as our solution. The idea of this paper was inspired by a paper titled "The Theory of Interstellar Trade" by Paul Krugman, a Nobel Economist.