OpenRaiser/Intern-Atlas huggingface dataset:
Dependency Language Models for Transition-based Dependency Parsing
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we present an approach to improve the accuracy of a strong transition-based dependency parser by exploiting dependency language models that are extracted from a large parsed corpus. We integrated a small number of features based on the dependency language models into the parser. To demonstrate the effectiveness of the proposed approach, we evaluate our parser on standard English and Chinese data where the base parser could achieve competitive accuracy scores. Our enhanced parser achieved state-of-the-art accuracy on Chinese data and competitive results on English data. We gained a large absolute improvement of one point (UAS) on Chinese and 0.5 points for English.
Gödel Logic: from Natural Deduction to Parallel Computation
Venue: arXiv cs.LO 2017
Year: 2017

Propositional Gödel logic extends intuitionistic logic with the non-constructive principle of linearity $A\rightarrow B\ \lor\ B\rightarrow A$. We introduce a Curry-Howard correspondence for this logic and show that a particularly simple natural deduction calculus can be used as a typing system. The resulting functional language enriches the simply typed lambda calculus with a synchronous communication mechanism between parallel processes. Our normalization proof employs original termination arguments and sophisticated proof transformations with a meaningful computational reading. Our results provide a computational interpretation of Gödel logic as a logic of communicating parallel processes, thus proving Avron's 1991 conjecture.
Improved Deep Learning of Object Category using Pose Information
Venue: arXiv cs.CV 2017
Year: 2017

Despite significant recent progress, the best available computer vision algorithms still lag far behind human capabilities, even for recognizing individual discrete objects under various poses, illuminations, and backgrounds. Here we present a new approach to using object pose information to improve deep network learning. While existing large-scale datasets, e.g. ImageNet, do not have pose information, we leverage the newly published turntable dataset, iLab-20M, which has ~22M images of 704 object instances shot under different lightings, camera viewpoints and turntable rotations, to do more controlled object recognition experiments. We introduce a new convolutional neural network architecture, what/where CNN (2W-CNN), built on a linear-chain feedforward CNN (e.g., AlexNet), augmented by hierarchical layers regularized by object poses. Pose information is only used as feedback signal during training, in addition to category information; during test, the feedforward network only predicts category. To validate the approach, we train both 2W-CNN and AlexNet using a fraction of the dataset, and 2W-CNN achieves 6% performance improvement in category prediction. We show mathematically that 2W-CNN has inherent advantages over AlexNet under the stochastic gradient descent (SGD) optimization procedure. Further more, we fine-tune object recognition on ImageNet by using the pretrained 2W-CNN and AlexNet features on iLab-20M, results show that significant improvements have been achieved, compared with training AlexNet from scratch. Moreover, fine-tuning 2W-CNN features performs even better than fine-tuning the pretrained AlexNet features. These results show pretrained features on iLab- 20M generalizes well to natural image datasets, and 2WCNN learns even better features for object recognition than AlexNet.
Evaluating On-demand Pseudonym Acquisition Policies in Vehicular Communication Systems
Venue: arXiv cs.CR 2017
Year: 2017

Standardization and harmonization efforts have reached a consensus towards using a special-purpose Vehicular Public-Key Infrastructure (VPKI) in upcoming Vehicular Communication (VC) systems. However, there are still several technical challenges with no conclusive answers; one such an important yet open challenge is the acquisition of shortterm credentials, pseudonym: how should each vehicle interact with the VPKI, e.g., how frequently and for how long? Should each vehicle itself determine the pseudonym lifetime? Answering these questions is far from trivial. Each choice can affect both the user privacy and the system performance and possibly, as a result, its security. In this paper, we make a novel systematic effort to address this multifaceted question. We craft three generally applicable policies and experimentally evaluate the VPKI system performance, leveraging two large-scale mobility datasets. We consider the most promising, in terms of efficiency, pseudonym acquisition policies; we find that within this class of policies, the most promising policy in terms of privacy protection can be supported with moderate overhead. Moreover, in all cases, this work is the first to provide tangible evidence that the state-of-the-art VPKI can serve sizable areas or domain with modest computing resources.
A Survey on Load Balancing Algorithms for VM Placement in Cloud Computing
Venue: arXiv cs.DC 2017
Year: 2017

The emergence of cloud computing based on virtualization technologies brings huge opportunities to host virtual resource at low cost without the need of owning any infrastructure. Virtualization technologies enable users to acquire, configure and be charged on pay-per-use basis. However, Cloud data centers mostly comprise heterogeneous commodity servers hosting multiple virtual machines (VMs) with potential various specifications and fluctuating resource usages, which may cause imbalanced resource utilization within servers that may lead to performance degradation and service level agreements (SLAs) violations. To achieve efficient scheduling, these challenges should be addressed and solved by using load balancing strategies, which have been proved to be NP-hard problem. From multiple perspectives, this work identifies the challenges and analyzes existing algorithms for allocating VMs to PMs in infrastructure Clouds, especially focuses on load balancing. A detailed classification targeting load balancing algorithms for VM placement in cloud data centers is investigated and the surveyed algorithms are classified according to the classification. The goal of this paper is to provide a comprehensive and comparative understanding of existing literature and aid researchers by providing an insight for potential future enhancements.
Approximation Schemes for Geometric Coverage Problems
Venue: arXiv cs.CG 2017
Year: 2017

In their seminal work, Mustafa and Ray (2009) showed that a wide class of geometric set cover (SC) problems admit a PTAS via local search -- this is one of the most general approaches known for such problems. Their result applies if a naturally defined "exchange graph" for two feasible solutions is planar and is based on subdividing this graph via a planar separator theorem due to Frederickson (1987). Obtaining similar results for the related maximum k-coverage problem (MC) seems non-trivial due to the hard cardinality constraint. In fact, while Badanidiyuru, Kleinberg, and Lee (2012) have shown (via a different analysis) that local search yields a PTAS for two-dimensional real halfspaces, they only conjectured that the same holds true for dimension three. Interestingly, at this point it was already known that local search provides a PTAS for the corresponding set cover case and this followed directly from the approach of Mustafa and Ray. In this work we provide a way to address the above-mentioned issue. First, we propose a color-balanced version of the planar separator theorem. The resulting subdivision approximates locally in each part the global distribution of the colors. Second, we show how this roughly balanced subdivision can be employed in a more careful analysis to strictly obey the hard cardinality constraint. More specifically, we obtain a PTAS for any "planarizable" instance of MC and thus essentially for all cases where the corresponding SC instance can be tackled via the approach of Mustafa and Ray. As a corollary, we confirm the conjecture of Badanidiyuru, Kleinberg, and Lee regarding real half spaces in dimension three. We feel that our ideas could also be helpful in other geometric settings involving a cardinality constraint.
Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide
Venue: arXiv cs.DS 2017
Year: 2017

A graph is $(H_1,H_2)$-free for a pair of graphs $H_1,H_2$ if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. In 2001, Král', Kratochv\'ıl, Tuza, and Woeginger initiated a study into the complexity of Colouring for $(H_1,H_2)$-free graphs. Since then, others have tried to complete their study, but many cases remain open. We focus on those $(H_1,H_2)$-free graphs where $H_2$ is $\overline{H_1}$, the complement of $H_1$. As these classes are closed under complementation, the computational complexities of Colouring and Clique Cover coincide. By combining new and known results, we are able to classify the complexity of Colouring and Clique Cover for $(H,\overline{H})$-free graphs for all cases except when $H=sP_1+ P_3$ for $s\geq 3$ or $H=sP_1+P_4$ for $s\geq 2$. We also classify the complexity of Colouring on graph classes characterized by forbidding a finite number of self-complementary induced subgraphs, and we initiate a study of $k$-Colouring for $(P_r,\overline{P_r})$-free graphs.
Restoring highly corrupted images by impulse noise using radial basis functions interpolation
Venue: arXiv cs.MM 2017
Year: 2017

Preserving details in restoring images highly corrupted by impulse noise remains a challenging problem. We proposed an algorithm based on radial basis functions (RBF) interpolation which estimates the intensities of corrupted pixels by their neighbors. In this algorithm, first intensity values of noisy pixels in the corrupted image are estimated using RBFs. Next, the image is smoothed. The proposed algorithm can effectively remove the highly dense impulse noise. Experimental results show the superiority of the proposed algorithm in comparison to the recent similar methods both in noise suppression and detail preservation. Extensive simulations show better results in measure of peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM), especially when the image is corrupted by very highly dense impulse noise.
Fixing improper colorings of graphs
Venue: arXiv cs.DM 2017
Year: 2017

In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper $r$-coloring $φ$ of a graph $G$. We investigate the problem of finding a proper $r$-coloring of $G$, which is "the most similar" to $φ$, i.e. the number $k$ of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any $r \geq 3$, even for bipartite planar graphs. On the other hand, the problem is fixed-parameter tractable, when parameterized by the number of allowed transformations $k$. We provide an $2^n \cdot n^{\mathcal{O}(1)}$ algorithm for the problem (for any fixed $r$) and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the {\em fixing number} of a graph $G$. It is the maximum possible distance (in the number of transformations) between some non-proper coloring of $G$ and a proper one.
The Costs and Benefits of Sharing: Sequential Individual Rationality and Sequential Fairness
Venue: arXiv cs.GT 2017
Year: 2017

In designing dynamic shared service systems that incentivize customers to opt for shared rather than exclusive service, the traditional notion of individual rationality may be insufficient, as a customer's estimated utility could fluctuate arbitrarily during their time in the shared system, as long as their realized utility at service completion is not worse than that for exclusive service. In this work, within a model that explicitly considers the "inconvenience costs" incurred by customers due to sharing, we introduce the notion of sequential individual rationality (SIR) that requires that the disutility of existing customers is nonincreasing as the system state changes due to new customer arrivals. Next, under SIR, we observe that cost sharing can also be viewed as benefit sharing, which inspires a natural definition of sequential fairness (SF) - the total incremental benefit due to a new customer is shared among existing customers in proportion to the incremental inconvenience suffered. We demonstrate the effectiveness of these notions by applying them to a ridesharing system, where unexpected detours to pick up subsequent passengers inconvenience the existing passengers. Imposing SIR and SF reveals interesting and surprising results, including: (a) natural limits on the incremental detours permissible, (b) exact characterization of "SIR-feasible" routes, which boast sublinear upper and lower bounds on the fractional detours, (c) exact characterization of sequentially fair cost sharing schemes, which includes a strong requirement that passengers must compensate each other for the detour inconveniences that they cause, and (d) new algorithmic problems related to and motivated by SIR.
Non-Convex Phase Retrieval from STFT Measurements
Venue: arXiv cs.IT 2017
Year: 2017

The problem of recovering a one-dimensional signal from its Fourier transform magnitude, called Fourier phase retrieval, is ill-posed in most cases. We consider the closely-related problem of recovering a signal from its phaseless short-time Fourier transform (STFT) measurements. This problem arises naturally in several applications, such as ultra-short laser pulse characterization and ptychography. The redundancy offered by the STFT enables unique recovery under mild conditions. We show that in some cases the unique solution can be obtained by the principal eigenvector of a matrix, constructed as the solution of a simple least-squares problem. When these conditions are not met, we suggest using the principal eigenvector of this matrix to initialize non-convex local optimization algorithms and propose two such methods. The first is based on minimizing the empirical risk loss function, while the second maximizes a quadratic function on the manifold of phases. We prove that under appropriate conditions, the proposed initialization is close to the underlying signal. We then analyze the geometry of the empirical risk loss function and show numerically that both gradient algorithms converge to the underlying signal even with small redundancy in the measurements. In addition, the algorithms are robust to noise.
Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
Venue: arXiv cs.GT 2017
Year: 2017

This work examines a stochastic formulation of the generalized Nash equilibrium problem (GNEP) where agents are subject to randomness in the environment of unknown statistical distribution. We focus on fully-distributed online learning by agents and employ penalized individual cost functions to deal with coupled constraints. Three stochastic gradient strategies are developed with constant step-sizes. We allow the agents to use heterogeneous step-sizes and show that the penalty solution is able to approach the Nash equilibrium in a stable manner within $O(μ_\text{max})$, for small step-size value $μ_\text{max}$ and sufficiently large penalty parameters. The operation of the algorithm is illustrated by considering the network Cournot competition problem.
TRIOT: Faster tensor manipulation in C++11
Venue: arXiv cs.MS 2017
Year: 2017

[abridged] Context: Multidimensional arrays are used by many different algorithms. As such, indexing and broadcasting complex operations over multidimensional arrays are ubiquitous tasks and can be performance limiting. Inquiry: Simultaneously indexing two or more multidimensional arrays with different shapes (e.g., copying data from one tensor to another larger, zero padded tensor in anticipation of a convolution) is difficult to do efficiently: Hard-coded nested for loops in C, Fortran, and Go cannot be applied when the dimension of a tensor is unknown at compile time. Likewise, boost::multi_array cannot be used unless the dimensions of the array are known at compile time, and the style of implementation restricts the user from using the index tuple inside a vectorized operation (as would be required to compute an expected value of a multidimensional distribution). On the other hand, iteration methods that do not require the dimensionality or shape to be known at compile time (e.g., incrementing and applying carry operations to index tuples or remapping integer indices in the flat array), can be substantially slower than hard-coded nested for loops. ... Importance: Manipulation of multidimensional arrays is a common task in software, especially in high performance numerical methods. This paper proposes a novel way to leverage template recursion to iterate over and apply operations to multidimensional arrays, and then demonstrates the superior performance and flexibility of operations that can be achieved using this new approach.
Enhanced Cellular Coverage and Throughput using Rateless Codes
Venue: arXiv cs.IT 2017
Year: 2017

Rateless codes have been shown to provide robust error correction over a wide range of binary and noisy channels. Using a stochastic geometry model, this paper studies the performance of rateless codes in the cellular downlink and compares it with the performance of fixed-rate codes. For the case of Rayleigh fading, an accurate approximation is proposed for the distribution of the packet transmission time of $K$-bit information packets using rateless codes. The two types of channel coding schemes are compared by evaluating the typical user and per-user success probability and the rate. Based on both the analytical results and simulations, the paper shows that rateless coding provides a significant throughput gain relative to fixed-rate coding. Moreover the benefit is not restricted to the typical user but applies to all users in the cellular network.
Horn: A System for Parallel Training and Regularizing of Large-Scale Neural Networks
Venue: arXiv cs.DC 2017
Year: 2017

I introduce a new distributed system for effective training and regularizing of Large-Scale Neural Networks on distributed computing architectures. The experiments demonstrate the effectiveness of flexible model partitioning and parallelization strategies based on neuron-centric computation model, with an implementation of the collective and parallel dropout neural networks training. Experiments are performed on MNIST handwritten digits classification including results.
Scaling the Kalman filter for large-scale traffic estimation
Venue: arXiv cs.SY 2017
Year: 2017

This work introduces a scalable filtering algorithm for multi-agent traffic estimation. Large-scale networks are spatially partitioned into overlapping road sections. The traffic dynamics of each section is given by the switching mode model (SMM) using a conservation principle, and the traffic state in each section is estimated by a local agent. In the proposed filter, a consensus term is applied to promote inter-agent agreement on overlapping sections. The new filter, termed a (spatially) distributed local Kalman consensus filter (DLKCF), is shown to maintain globally asymptotically stable (GAS) mean error dynamics when all sections switch among observable modes. When a section is unobservable, we show that the mean estimate of each state variable in the section is ultimately bounded, which is achieved by exploring the interaction between the properties of the traffic model and the measurement feedback of the filter. Based on the above results, the boundedness of the mean estimation error of the DLKCF under switching sequences with observable and unobservable modes is established to address the overall performance of the filter. Numerical experiments show the ability of the DLKCF to promote consensus, increase estimation accuracy compared to a local filter, and reduce the computational load compared to a centralized approach.
Lower Bounds on the mim-width of Some Graph Classes
Venue: arXiv cs.DM 2017
Year: 2017

mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower bounds for the mim-width of strongly chordal split graphs, co-comparability graphs and circle graphs. This improves and refines lower bounds that were known before, some of them only conditionally. In the case of strongly chordal graphs not even a conditional lower bound was known before. All of the bounds given are optimal up to constants.
Binarisation for Valued Constraint Satisfaction Problems
Venue: arXiv cs.DM 2017
Year: 2017

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. Second, we extend the reduction of CSPs to binary CSPs described by Bulin et al. [LMCS'15] to VCSPs. This reduction establishes that VCSPs over a fixed valued constraint language are polynomial-time equivalent to Minimum-Cost Homomorphism Problems over a fixed digraph.
Passive Taxonomy of Wifi Clients using MLME Frame Contents
Venue: arXiv cs.NI 2017
Year: 2017

In supporting Wifi networks it is useful to identify the type of client device connecting to an AP. Knowing the type of client can guide troubleshooting steps, allow searches for known issues, or allow specific workarounds to be implemented in the AP. For support purposes a passive method which analyzes normal traffic is preferable to active methods, which often send obscure combinations of packet options which might trigger client bugs. We have developed a method of passive client identification which observes the contents of Wifi management frames including Probes and Association requests. We show that the management frames populated by modern Wifi chipsets and device drivers are quite distinguishable, making it possible in many cases to identify the model of the device. Supplementing information from the Wifi management frames with additional information from DHCP further extends the set of clients which can be distinguished.
Coverage in Heterogeneous Downlink Millimeter Wave Cellular Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we provide an analytical framework to analyze heterogeneous downlink mmWave cellular networks consisting of K tiers of randomly located base stations (BSs) where each tier operates in a mmWave frequency band. Signal-to-interference-plus-noise ratio (SINR) coverage probability is derived for the entire network using tools from stochastic geometry. The distinguishing features of mmWave communications such as directional beamforming and having different path loss laws for line-of-sight (LOS) and non-line-of-sight (NLOS) links are incorporated into the coverage analysis by assuming averaged biased received power association and Nakagami-m fading. By using the noise-limited assumption for mmWave networks, a simpler expression requiring the computation of only one numerical integral for coverage probability is obtained. Also, effect of beamforming alignment errors on the coverage probability analysis is investigated to get insight on the performance in practical scenarios. Downlink rate coverage probability is derived as well to get more insights on the performance of the network. Moreover, effect of deploying low-power smaller cells and effect of biasing factor on energy efficiency is analyzed. Finally, a hybrid cellular network operating in both mmWave and microWave frequency bands is addressed.