OpenRaiser/Intern-Atlas huggingface dataset:
A Unification and Generalization of Exact Distributed First Order Methods
Venue: arXiv cs.IT 2017
Year: 2017

Recently, there has been significant progress in the development of distributed first order methods. (At least) two different types of methods, designed from very different perspectives, have been proposed that achieve both exact and linear convergence when a constant step size is used -- a favorable feature that was not achievable by most prior methods. In this paper, we unify, generalize, and improve convergence speed of these exact distributed first order methods. We first carry out a novel unifying analysis that sheds light on how the different existing methods compare. The analysis reveals that a major difference between the methods is on how a past dual gradient of an associated augmented Lagrangian dual function is weighted. We then capitalize on the insights from the analysis to derive a novel method -- with a tuned past gradient weighting -- that improves upon the existing methods. We establish for the proposed generalized method global R-linear convergence rate under strongly convex costs with Lipschitz continuous gradients.
A Generic Formation Controller and State Observer for Multiple Unmanned Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we present a novel decentralized controller to drive multiple unmanned aerial vehicles (UAVs) into a symmetric formation of regular polygon shape surrounding a mobile target. The proposed controller works for time-varying information exchange topologies among agents and preserves a network connectivity while steering UAVs into a formation. The proposed nonlinear controller is highly generalized and offers flexibility in achieving the control objective due to the freedom of choosing controller parameters from a range of values. By the virtue of additional tuning parameters, i.e. fractional powers on proportional and derivative difference terms, the nonlinear controller procures a family of UAV trajectories satisfying the same control objective. An appropriate adjustment of the parameters facilitates in generating smooth UAV trajectories without causing abrupt position jumps. The convergence of the closed-loop system is analyzed and established using the Lyapunov approach. Simulation results validate the effectiveness of the proposed controller which outperforms an existing formation controller by driving a team of UAVs elegantly in a target-centric formation. We also present a nonlinear observer to estimate vehicle velocities with the availability of position coordinates and heading angles. Simulation results show that the proposed nonlinear observer results in quick convergence of the estimates to its true values.
Random Pilot and Data Access in Massive MIMO for Machine-type Communications
Venue: arXiv cs.IT 2017
Year: 2017

A massive MIMO system, represented by a base station with hundreds of antennas, is capable of spatially multiplexing many devices and thus naturally suited to serve dense crowds of wireless devices in emerging applications, such as machine-type communications. Crowd scenarios pose new challenges in the pilot-based acquisition of channel state information and call for pilot access protocols that match the intermittent pattern of device activity. A joint pilot assignment and data transmission protocol based on random access is proposed in this paper for the uplink of a massive MIMO system. The protocol relies on the averaging across multiple transmission slots of the pilot collision events that result from the random access process. We derive new uplink sum rate expressions that take pilot collisions, intermittent device activity, and interference into account. Simplified bounds are obtained and used to optimize the device activation probability and pilot length. A performance analysis indicates how performance scales as a function of the number of antennas and the transmission slot duration.
Coalitional game with opinion exchange
Venue: arXiv cs.GT 2017
Year: 2017

In coalitional games, traditional coalitional game theory does not apply if different participants hold different opinions about the payoff function that corresponds to each subset of the coalition. In this paper, we propose a framework in which players can exchange opinions about their views of payoff functions and then decide the distribution of the value of the grand coalition. When all players are truth-telling, the problem of opinion consensus is decoupled from the coalitional game, but interesting dynamics will arise when players are strategic in the consensus phase. Assuming that all players are rational, the model implies that, if influential players are risk-averse, an efficient fusion of the distributed data is achieved at pure strategy Nash equilibrium, meaning that the average opinion will not drift. Also, without the assumption that all players are rational, each player can use an algorithmic R-learning process, which gives the same result as the pure strategy Nash equilibrium with rational players.
An Exact Approach for the Balanced k-Way Partitioning Problem with Weight Constraints and its Application to Sports Team Realignment
Venue: arXiv cs.DM 2017
Year: 2017

In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations, where the total distance of the road trips that all teams must travel to play a Double Round Robin Tournament in each group is minimized. Two integer programming formulations for this problem are introduced, and the validity of three families of inequalities associated to the polytope of these formulations is proved. The performance of a tabu search procedure and a Branch & Cut algorithm, which uses the valid inequalities as cuts, is evaluated over simulated and real-world instances. In particular, an optimal solution for the realignment of the Ecuadorian Football league is reported and the methodology can be suitable adapted for the realignment of other sports leagues.
A Statistical Approach to Increase Classification Accuracy in Supervised Learning Algorithms
Venue: arXiv cs.LG 2017
Year: 2017

Probabilistic mixture models have been widely used for different machine learning and pattern recognition tasks such as clustering, dimensionality reduction, and classification. In this paper, we focus on trying to solve the most common challenges related to supervised learning algorithms by using mixture probability distribution functions. With this modeling strategy, we identify sub-labels and generate synthetic data in order to reach better classification accuracy. It means we focus on increasing the training data synthetically to increase the classification accuracy.
Locality-Aware Hybrid Coded MapReduce for Server-Rack Architecture
Venue: arXiv cs.DC 2017
Year: 2017

MapReduce is a widely used framework for distributed computing. Data shuffling between the Map phase and Reduce phase of a job involves a large amount of data transfer across servers, which in turn accounts for increase in job completion time. Recently, Coded MapReduce has been proposed to offer savings with respect to the communication cost incurred in data shuffling. This is achieved by creating coded multicast opportunities for shuffling through repeating Map tasks at multiple servers. We consider a server-rack architecture for MapReduce and in this architecture, propose to divide the total communication cost into two: intra-rack communication cost and cross-rack communication cost. Having noted that cross-rack data transfer operates at lower speed as compared to intra-rack data transfer, we present a scheme termed as Hybrid Coded MapReduce which results in lower cross-rack communication than Coded MapReduce at the cost of increase in intra-rack communication. In addition, we pose the problem of assigning Map tasks to servers to maximize data locality in the framework of Hybrid Coded MapReduce as a constrained integer optimization problem. We show through simulations that data locality can be improved considerably by using the solution of optimization to assign Map tasks to servers.
Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Venue: arXiv cs.CG 2017
Year: 2017

Let $T$ be an $n$-node tree of maximum degree 4, and let $P$ be a set of $n$ points in the plane with no two points on the same horizontal or vertical line. It is an open question whether $T$ always has a planar drawing on $P$ such that each edge is drawn as an orthogonal path with one bend (an "L-shaped" edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set $P$ for which such drawings are possible to: $O(n^{1.55})$ for maximum degree 4 trees; $O(n^{1.22})$ for maximum degree 3 (binary) trees; and $O(n^{1.142})$ for perfect binary trees. Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of $O(n \log n)$ points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.
Subspace Segmentation by Successive Approximations: A Method for Low-Rank and High-Rank Data with Missing Entries
Venue: arXiv cs.CV 2017
Year: 2017

We propose a method to reconstruct and cluster incomplete high-dimensional data lying in a union of low-dimensional subspaces. Exploring the sparse representation model, we jointly estimate the missing data while imposing the intrinsic subspace structure. Since we have a non-convex problem, we propose an iterative method to reconstruct the data and provide a sparse similarity affinity matrix. This method is robust to initialization and achieves greater reconstruction accuracy than current methods, which dramatically improves clustering performance. Extensive experiments with synthetic and real data show that our approach leads to significant improvements in the reconstruction and segmentation, outperforming current state of the art for both low and high-rank data.
Queueing systems with renovation vs. queues with RED. Supplementary Material
Venue: arXiv cs.PF 2017
Year: 2017

In this note we consider M/D/1/N queue with renovation and derive analytic expressions for the following performance characteristics: stationary loss rate, moments of the number in the system. Moments of consecutive losses, waiting/sojourn time are out of scope. The motivation for studying these characteristics is in the comparison of renovation with known active queue mechanisms like RED.
PageNet: Page Boundary Extraction in Historical Handwritten Documents
Venue: arXiv cs.CV 2017
Year: 2017

When digitizing a document into an image, it is common to include a surrounding border region to visually indicate that the entire document is present in the image. However, this border should be removed prior to automated processing. In this work, we present a deep learning based system, PageNet, which identifies the main page region in an image in order to segment content from both textual and non-textual border noise. In PageNet, a Fully Convolutional Network obtains a pixel-wise segmentation which is post-processed into the output quadrilateral region. We evaluate PageNet on 4 collections of historical handwritten documents and obtain over 94% mean intersection over union on all datasets and approach human performance on 2 of these collections. Additionally, we show that PageNet can segment documents that are overlayed on top of other documents.
A Comparative Study of 2D Numerical Methods with GPU Computing
Venue: arXiv cs.DC 2017
Year: 2017

Graphics Processing Unit (GPU) computing is becoming an alternate computing platform for numerical simulations. However, it is not clear which numerical scheme will provide the highest computational efficiency for different types of problems. To this end, numerical accuracies and computational work of several numerical methods are compared using a GPU computing implementation. The Correction Procedure via Reconstruction (CPR), Discontinuous Galerkin (DG), Nodal Discontinuous Galerkin (NDG), Spectral Difference (SD), and Finite Volume (FV) methods are investigated using various reconstruction orders. Both smooth and discontinuous cases are considered for two-dimensional simulations. For discontinuous problems, MUSCL schemes are employed with FV, while CPR, DG, NDG, and SD use slope limiting. The computation time to reach a set error criteria and total time to complete solutions are compared across the methods. It is shown that while FV methods can produce solutions with low computational times, they produce larger errors than high-order methods for smooth problems at the same order of accuracy. For discontinuous problems, the methods show good agreement with one another in terms of solution profiles, and the total computational times between FV, CPR, and SD are comparable.
Antenna Selection in MIMO Cognitive Radio-Inspired NOMA Systems
Venue: arXiv cs.IT 2017
Year: 2017

This letter investigates a joint antenna selection (AS) problem for a MIMO cognitive radio-inspired non-orthogonal multiple access (CR-NOMA) network. In particular, a new computationally efficient joint AS algorithm, namely subset-based joint AS (SJ-AS), is proposed to maximize the signal-to-noise ratio of the secondary user under the condition that the quality of service (QoS) of the primary user is satisfied. The asymptotic closed-form expression of the outage performance for SJ-AS is derived, and the minimal outage probability achieved by SJ-AS among all possible joint AS schemes is proved. The provided numerical results demonstrate the superior performance of the proposed scheme.
The Voynich Manuscript is Written in Natural Language: The Pahlavi Hypothesis
Venue: arXiv cs.CL 2017
Year: 2017

The late medieval Voynich Manuscript (VM) has resisted decryption and was considered a meaningless hoax or an unsolvable cipher. Here, we provide evidence that the VM is written in natural language by establishing a relation of the Voynich alphabet and the Iranian Pahlavi script. Many of the Voynich characters are upside-down versions of their Pahlavi counterparts, which may be an effect of different writing directions. Other Voynich letters can be explained as ligatures or departures from Pahlavi with the intent to cope with known problems due to the stupendous ambiguity of Pahlavi text. While a translation of the VM text is not attempted here, we can confirm the Voynich-Pahlavi relation at the character level by the transcription of many words from the VM illustrations and from parts of the main text. Many of the transcribed words can be identified as terms from Zoroastrian cosmology which is in line with the use of Pahlavi script in Zoroastrian communities from medieval times.
Cross-Domain Image Retrieval with Attention Modeling
Venue: arXiv cs.MM 2017
Year: 2017

With the proliferation of e-commerce websites and the ubiquitousness of smart phones, cross-domain image retrieval using images taken by smart phones as queries to search products on e-commerce websites is emerging as a popular application. One challenge of this task is to locate the attention of both the query and database images. In particular, database images, e.g. of fashion products, on e-commerce websites are typically displayed with other accessories, and the images taken by users contain noisy background and large variations in orientation and lighting. Consequently, their attention is difficult to locate. In this paper, we exploit the rich tag information available on the e-commerce websites to locate the attention of database images. For query images, we use each candidate image in the database as the context to locate the query attention. Novel deep convolutional neural network architectures, namely TagYNet and CtxYNet, are proposed to learn the attention weights and then extract effective representations of the images. Experimental results on public datasets confirm that our approaches have significant improvement over the existing methods in terms of the retrieval accuracy and efficiency.
CacheShield: Protecting Legacy Processes Against Cache Attacks
Venue: arXiv cs.CR 2017
Year: 2017

Cache attacks pose a threat to any code whose execution flow or memory accesses depend on sensitive information. Especially in public clouds, where caches are shared across several tenants, cache attacks remain an unsolved problem. Cache attacks rely on evictions by the spy process, which alter the execution behavior of the victim process. We show that hardware performance events of cryptographic routines reveal the presence of cache attacks. Based on this observation, we propose CacheShield, a tool to protect legacy code by monitoring its execution and detecting the presence of cache attacks, thus providing the opportunity to take preventative measures. CacheShield can be run by users and does not require alteration of the OS or hypervisor, while previously proposed software-based countermeasures require cooperation from the hypervisor. Unlike methods that try to detect malicious processes, our approach is lean, as only a fraction of the system needs to be monitored. It also integrates well into today's cloud infrastructure, as concerned users can opt to use CacheShield without support from the cloud service provider. Our results show that CacheShield detects cache attacks fast, with high reliability, and with few false positives, even in the presence of strong noise.
CNN-Based Projected Gradient Descent for Consistent Image Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

We present a new method for image reconstruction which replaces the projector in a projected gradient descent (PGD) with a convolutional neural network (CNN). CNNs trained as high-dimensional (image-to-image) regressors have recently been used to efficiently solve inverse problems in imaging. However, these approaches lack a feedback mechanism to enforce that the reconstructed image is consistent with the measurements. This is crucial for inverse problems, and more so in biomedical imaging, where the reconstructions are used for diagnosis. In our scheme, the gradient descent enforces measurement consistency, while the CNN recursively projects the solution closer to the space of desired reconstruction images. We provide a formal framework to ensure that the classical PGD converges to a local minimizer of a non-convex constrained least-squares problem. When the projector is replaced with a CNN, we propose a relaxed PGD, which always converges. Finally, we propose a simple scheme to train a CNN to act like a projector. Our experiments on sparse view Computed Tomography (CT) reconstruction for both noiseless and noisy measurements show an improvement over the total-variation (TV) method and a recent CNN-based technique.
Towards Automated Cadastral Boundary Delineation from UAV Data
Venue: arXiv cs.CV 2017
Year: 2017

Unmanned aerial vehicles (UAV) are evolving as an alternative tool to acquire land tenure data. UAVs can capture geospatial data at high quality and resolution in a cost-effective, transparent and flexible manner, from which visible land parcel boundaries, i.e., cadastral boundaries are delineable. This delineation is to no extent automated, even though physical objects automatically retrievable through image analysis methods mark a large portion of cadastral boundaries. This study proposes (i) a workflow that automatically extracts candidate cadastral boundaries from UAV orthoimages and (ii) a tool for their semi-automatic processing to delineate final cadastral boundaries. The workflow consists of two state-of-the-art computer vision methods, namely gPb contour detection and SLIC superpixels that are transferred to remote sensing in this study. The tool combines the two methods, allows a semi-automatic final delineation and is implemented as a publicly available QGIS plugin. The approach does not yet aim to provide a comparable alternative to manual cadastral mapping procedures. However, the methodological development of the tool towards this goal is developed in this paper. A study with 13 volunteers investigates the design and implementation of the approach and gathers initial qualitative as well as quantitate results. The study revealed points for improvement, which are prioritized based on the study results and which will be addressed in future work.
Foundation for a series of efficient simulation algorithms
Venue: arXiv cs.LO 2017
Year: 2017

Compute the coarsest simulation preorder included in an initial preorder is used to reduce the resources needed to analyze a given transition system. This technique is applied on many models like Kripke structures, labeled graphs, labeled transition systems or even word and tree automata. Let (Q, $\rightarrow$) be a given transition system and Rinit be an initial preorder over Q. Until now, algorithms to compute Rsim , the coarsest simulation included in Rinit , are either memory efficient or time efficient but not both. In this paper we propose the foundation for a series of efficient simulation algorithms with the introduction of the notion of maximal transitions and the notion of stability of a preorder with respect to a coarser one. As an illustration we solve an open problem by providing the first algorithm with the best published time complexity, O(|Psim |.|$\rightarrow$|), and a bit space complexity in O(|Psim |^2. log(|Psim |) + |Q|. log(|Q|)), with Psim the partition induced by Rsim.
Measuring the Similarity of Sentential Arguments in Dialog
Venue: arXiv cs.CL 2017
Year: 2017

When people converse about social or political topics, similar arguments are often paraphrased by different speakers, across many different conversations. Debate websites produce curated summaries of arguments on such topics; these summaries typically consist of lists of sentences that represent frequently paraphrased propositions, or labels capturing the essence of one particular aspect of an argument, e.g. Morality or Second Amendment. We call these frequently paraphrased propositions ARGUMENT FACETS. Like these curated sites, our goal is to induce and identify argument facets across multiple conversations, and produce summaries. However, we aim to do this automatically. We frame the problem as consisting of two steps: we first extract sentences that express an argument from raw social media dialogs, and then rank the extracted arguments in terms of their similarity to one another. Sets of similar arguments are used to represent argument facets. We show here that we can predict ARGUMENT FACET SIMILARITY with a correlation averaging 0.63 compared to a human topline averaging 0.68 over three debate topics, easily beating several reasonable baselines.
Towards Neural Machine Translation with Latent Tree Attention
Venue: arXiv cs.CL 2017
Year: 2017

Building models that take advantage of the hierarchical structure of language without a priori annotation is a longstanding goal in natural language processing. We introduce such a model for the task of machine translation, pairing a recurrent neural network grammar encoder with a novel attentional RNNG decoder and applying policy gradient reinforcement learning to induce unsupervised tree structures on both the source and target. When trained on character-level datasets with no explicit segmentation or parse annotation, the model learns a plausible segmentation and shallow parse, obtaining performance close to an attentional baseline.
Implicit Regularization in Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

In an attempt to better understand generalization in deep learning, we study several possible explanations. We show that implicit regularization induced by the optimization method is playing a key role in generalization and success of deep learning models. Motivated by this view, we study how different complexity measures can ensure generalization and explain how optimization algorithms can implicitly regularize complexity measures. We empirically investigate the ability of these measures to explain different observed phenomena in deep learning. We further study the invariances in neural networks, suggest complexity measures and optimization algorithms that have similar invariances to those in neural networks and evaluate them on a number of learning tasks.