OpenRaiser/Intern-Atlas huggingface dataset:
Random Sampling for Fast Face Sketch Synthesis
Venue: arXiv cs.CV 2017
Year: 2017

Exemplar-based face sketch synthesis plays an important role in both digital entertainment and law enforcement. It generally consists of two parts: neighbor selection and reconstruction weight representation. The most time-consuming or main computation complexity for exemplar-based face sketch synthesis methods lies in the neighbor selection process. State-of-the-art face sketch synthesis methods perform neighbor selection online in a data-driven manner by $K$ nearest neighbor ($K$-NN) searching. Actually, the online search increases the time consuming for synthesis. Moreover, since these methods need to traverse the whole training dataset for neighbor selection, the computational complexity increases with the scale of the training database and hence these methods have limited scalability. In this paper, we proposed a simple but effective offline random sampling in place of online $K$-NN search to improve the synthesis efficiency. Extensive experiments on public face sketch databases demonstrate the superiority of the proposed method in comparison to state-of-the-art methods, in terms of both synthesis quality and time consumption. The proposed method could be extended to other heterogeneous face image transformation problems such as face hallucination. We release the source codes of our proposed methods and the evaluation metrics for future study online: http://www.ihitworld.com/RSLCR.html.
Cheating-Resilient Incentive Scheme for Mobile Crowdsensing Systems
Venue: arXiv cs.NI 2017
Year: 2017

Mobile Crowdsensing is a promising paradigm for ubiquitous sensing, which explores the tremendous data collected by mobile smart devices with prominent spatial-temporal coverage. As a fundamental property of Mobile Crowdsensing Systems, temporally recruited mobile users can provide agile, fine-grained, and economical sensing labors, however their self-interest cannot guarantee the quality of the sensing data, even when there is a fair return. Therefore, a mechanism is required for the system server to recruit well-behaving users for credible sensing, and to stimulate and reward more contributive users based on sensing truth discovery to further increase credible reporting. In this paper, we develop a novel Cheating-Resilient Incentive (CRI) scheme for Mobile Crowdsensing Systems, which achieves credibility-driven user recruitment and payback maximization for honest users with quality data. Via theoretical analysis, we demonstrate the correctness of our design. The performance of our scheme is evaluated based on extensive realworld trace-driven simulations. Our evaluation results show that our scheme is proven to be effective in terms of both guaranteeing sensing accuracy and resisting potential cheating behaviors, as demonstrated in practical scenarios, as well as those that are intentionally harsher.
$O(\mbox{depth})$-Competitive Algorithm for Online Multi-level Aggregation
Venue: arXiv cs.DS 2017
Year: 2017

We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. (2015). In this problem requests arrive over time at the nodes of the tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply-chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online $O(D)$-competitive algorithm for the problem, where $D$ is the depth, or number of levels, of the aggregation tree. This result improves upon the $D^2 2^D$-competitive algorithm obtained recently by Bienkowski et al. (2015).
Polar Coding for the Binary Erasure Channel with Deletions
Venue: arXiv cs.IT 2017
Year: 2017

We study the application of polar codes in deletion channels by analyzing the cascade of a binary erasure channel (BEC) and a deletion channel. We show how polar codes can be used effectively on a BEC with a single deletion, and propose a list decoding algorithm with a cyclic redundancy check for this case. The decoding complexity is $O(N^2\log N)$, where $N$ is the blocklength of the code. An important contribution is an optimization of the amount of redundancy added to minimize the overall error probability. Our theoretical results are corroborated by numerical simulations which show that the list size can be reduced to one and the original message can be recovered with high probability as the length of the code grows.
On eccentricity version of Laplacian energy of a graph
Venue: arXiv cs.DM 2017
Year: 2017

The energy of a graph G is equal to the sum of absolute values of the eigenvalues of the adjacency matrix of G, whereas the Laplacian energy of a graph G is equal to the sum of the absolute value of the difference between the eigenvalues of the Laplacian matrix of G and average degree of the vertices of G. Motivated by the work from Sharafdini et al. [R. Sharafdini, H. Panahbar, Vertex weighted Laplacian graph energy and other topological indices. J. Math. Nanosci. 2016, 6, 49-57.], in this paper we investigate the eccentricity version of Laplacian energy of a graph G.
IRA codes derived from Gruenbaum graph
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider coding of short data frames (192 bits) by IRA codes. A new interleaver for the IRA codes based on a Gruenbaum graph is proposed. The difference of the proposed algorithm from known methods consists in the following: permutation is performed by using a match smaller interleaver which is derived from the Gruenbaum graph by finding in this graph a Hamiltonian path, enumerating the passed vertices in ascending order and passing them again in the permuted order through the edges which are not included in the Hamiltonian path. For the IRA code the obtained interleaver provides 0.7-0.8 db gain over a convolutional code decoded by Viterbi algorithm.
A Review of Localization and Tracking Algorithms in Wireless Sensor Networks
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, a comprehensive survey of the pioneer as well as the state of-the-art localization and tracking methods in the wireless sensor networks is presented. Localization is mostly applicable for the static sensor nodes, whereas, tracking for the mobile sensor nodes. The localization algorithms are broadly classified as range-based and range-free methods. The estimated range (distance) between an anchor and an unknown node is highly erroneous in an indoor scenario. This limitation can be handled up to a large extent by employing a large number of existing access points (APs) in the range free localization method. Recent works emphasize on the use multi-sensor data like magnetic, inertial, compass, gyroscope, ultrasound, infrared, visual and/or odometer to improve the localization accuracy further. Additionally, tracking method does the future prediction of location based on the past location history. A smooth trajectory is noted even if some of the received measurements are erroneous. Real experimental set-ups such as National Instruments (NI) wireless sensor nodes, Crossbow motes and hand-held devices for carrying out the localization and tracking are also highlighted herein.
Light Field Super-Resolution Via Graph-Based Regularization
Venue: arXiv cs.CV 2017
Year: 2017

Light field cameras capture the 3D information in a scene with a single exposure. This special feature makes light field cameras very appealing for a variety of applications: from post-capture refocus, to depth estimation and image-based rendering. However, light field cameras suffer by design from strong limitations in their spatial resolution, which should therefore be augmented by computational methods. On the one hand, off-the-shelf single-frame and multi-frame super-resolution algorithms are not ideal for light field data, as they do not consider its particular structure. On the other hand, the few super-resolution algorithms explicitly tailored for light field data exhibit significant limitations, such as the need to estimate an explicit disparity map at each view. In this work we propose a new light field super-resolution algorithm meant to address these limitations. We adopt a multi-frame alike super-resolution approach, where the complementary information in the different light field views is used to augment the spatial resolution of the whole light field. We show that coupling the multi-frame approach with a graph regularizer, that enforces the light field structure via nonlocal self similarities, permits to avoid the costly and challenging disparity estimation step for all the views. Extensive experiments show that the new algorithm compares favorably to the other state-of-the-art methods for light field super-resolution, both in terms of PSNR and visual quality.
Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem
Venue: arXiv cs.CC 2017
Year: 2017

The \emph{Orbit Problem} consists of determining, given a linear transformation $A$ on $\mathbb{Q}^d$, together with vectors $x$ and $y$, whether the orbit of $x$ under repeated applications of $A$ can ever reach $y$. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s. In this paper, we are concerned with the problem of synthesising suitable \emph{invariants} $\mathcal{P} \subseteq \mathbb{R}^d$, \emph{i.e.}, sets that are stable under $A$ and contain $x$ and not $y$, thereby providing compact and versatile certificates of non-reachability. We show that whether a given instance of the Orbit Problem admits a semialgebraic invariant is decidable, and moreover in positive instances we provide an algorithm to synthesise suitable invariants of polynomial size. It is worth noting that the existence of \emph{semilinear} invariants, on the other hand, is (to the best of our knowledge) not known to be decidable.
MatlabCompat.jl: helping Julia understand Your Matlab/Octave Code
Venue: arXiv cs.SE 2017
Year: 2017

Scientific legacy code in MATLAB/Octave not compatible with modernization of research workflows is vastly abundant throughout academic community. Performance of non-vectorized code written in MATLAB/Octave represents a major burden. A new programming language for technical computing Julia, promises to address these issues. Although Julia syntax is similar to MATLAB/Octave, porting code to Julia may be cumbersome for researchers. Here we present MatlabCompat.jl - a library aimed at simplifying the conversion of your MATLAB/Octave code to Julia. We show using a simplistic image analysis use case that MATLAB/Octave code can be easily ported to high performant Julia using MatlabCompat.jl.
JSON: data model, query languages and schema specification
Venue: arXiv cs.DB 2017
Year: 2017

Despite the fact that JSON is currently one of the most popular formats for exchanging data on the Web, there are very few studies on this topic and there are no agreement upon theoretical framework for dealing with JSON. There- fore in this paper we propose a formal data model for JSON documents and, based on the common features present in available systems using JSON, we define a lightweight query language allowing us to navigate through JSON documents. We also introduce a logic capturing the schema proposal for JSON and study the complexity of basic computational tasks associated with these two formalisms.
$k^{τ,ε}$-anonymity: Towards Privacy-Preserving Publishing of Spatiotemporal Trajectory Data
Venue: arXiv cs.CY 2017
Year: 2017

Mobile network operators can track subscribers via passive or active monitoring of device locations. The recorded trajectories offer an unprecedented outlook on the activities of large user populations, which enables developing new networking solutions and services, and scaling up studies across research disciplines. Yet, the disclosure of individual trajectories raises significant privacy concerns: thus, these data are often protected by restrictive non-disclosure agreements that limit their availability and impede potential usages. In this paper, we contribute to the development of technical solutions to the problem of privacy-preserving publishing of spatiotemporal trajectories of mobile subscribers. We propose an algorithm that generalizes the data so that they satisfy $k^{τ,ε}$-anonymity, an original privacy criterion that thwarts attacks on trajectories. Evaluations with real-world datasets demonstrate that our algorithm attains its objective while retaining a substantial level of accuracy in the data. Our work is a step forward in the direction of open, privacy-preserving datasets of spatiotemporal trajectories.
An Analytical Framework for Modeling a Spatially Repulsive Cellular Network
Venue: arXiv cs.IT 2017
Year: 2017

We propose a new cellular network model that captures both deterministic and random aspects of base station deployments. Namely, the base station locations are modeled as the superposition of two independent stationary point processes: a random shifted grid with intensity $λ_g$ and a Poisson point process (PPP) with intensity $λ_p$. Grid and PPP deployments are special cases with $λ_p \to 0$ and $λ_g \to 0$, with actual deployments in between these two extremes, as we demonstrate with deployment data. Assuming that each user is associated with the base station that provides the strongest average received signal power, we obtain the probability that a typical user is associated with either a grid or PPP base station. Assuming Rayleigh fading channels, we derive the expression for the coverage probability of the typical user, resulting in the following observations. First, the association and the coverage probability of the typical user are fully characterized as functions of intensity ratio $ρ_λ= λ_p/λ_g$. Second, the user association is biased towards the base stations located on a grid. Finally, the proposed model predicts the coverage probability of the actual deployment with great accuracy.
Resolution Simulates Ordered Binary Decision Diagrams for Formulas in Conjunctive Normal Form
Venue: arXiv cs.LO 2017
Year: 2017

A classical question of propositional logic is one of the shortest proof of a tautology. A related fundamental problem is to determine the relative efficiency of standard proof systems, where the relative complexity is measured using the notion of polynomial simulation. Presently, the state-of-the-art satisfiability algorithms are based on resolution in combination with search. An Ordered Binary Decision Diagram (OBDD) is a data structure that is used to represent Boolean functions. Groote and Zantema have proved that there is exponential separation between resolution and a proof system based on limited OBDD derivations. However, formal comparison of these methods is not straightforward because OBDDs work on arbitrary formulas, whereas resolution can only be applied to formulas in Conjunctive Normal Form (CNFs). Contrary to popular belief, we argue that resolution simulates OBDDs polynomially if we limit both to CNFs and thus answer negatively the open question of Groote and Zantema whether there exist unsatisfiable CNFs having polynomial OBDD refutations and requiring exponentially long resolution refutations.
QuickNet: Maximizing Efficiency and Efficacy in Deep Architectures
Venue: arXiv cs.LG 2017
Year: 2017

We present QuickNet, a fast and accurate network architecture that is both faster and significantly more accurate than other fast deep architectures like SqueezeNet. Furthermore, it uses less parameters than previous networks, making it more memory efficient. We do this by making two major modifications to the reference Darknet model (Redmon et al, 2015): 1) The use of depthwise separable convolutions and 2) The use of parametric rectified linear units. We make the observation that parametric rectified linear units are computationally equivalent to leaky rectified linear units at test time and the observation that separable convolutions can be interpreted as a compressed Inception network (Chollet, 2016). Using these observations, we derive a network architecture, which we call QuickNet, that is both faster and more accurate than previous models. Our architecture provides at least four major advantages: (1) A smaller model size, which is more tenable on memory constrained systems; (2) A significantly faster network which is more tenable on computationally constrained systems; (3) A high accuracy of 95.7 percent on the CIFAR-10 Dataset which outperforms all but one result published so far, although we note that our works are orthogonal approaches and can be combined (4) Orthogonality to previous model compression approaches allowing for further speed gains to be realized.
Visualizing Residual Networks
Venue: arXiv cs.CV 2017
Year: 2017

Residual networks are the current state of the art on ImageNet. Similar work in the direction of utilizing shortcut connections has been done extremely recently with derivatives of residual networks and with highway networks. This work potentially challenges our understanding that CNNs learn layers of local features that are followed by increasingly global features. Through qualitative visualization and empirical analysis, we explore the purpose that residual skip connections serve. Our assessments show that the residual shortcut connections force layers to refine features, as expected. We also provide alternate visualizations that confirm that residual networks learn what is already intuitively known about CNNs in general.
The principle of cognitive action - Preliminary experimental analysis
Venue: arXiv cs.LG 2017
Year: 2017

In this document we shows a first implementation and some preliminary results of a new theory, facing Machine Learning problems in the frameworks of Classical Mechanics and Variational Calculus. We give a general formulation of the problem and then we studies basic behaviors of the model on simple practical implementations.
Reinforcement Learning via Recurrent Convolutional Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Deep Reinforcement Learning has enabled the learning of policies for complex tasks in partially observable environments, without explicitly learning the underlying model of the tasks. While such model-free methods achieve considerable performance, they often ignore the structure of task. We present a natural representation of to Reinforcement Learning (RL) problems using Recurrent Convolutional Neural Networks (RCNNs), to better exploit this inherent structure. We define 3 such RCNNs, whose forward passes execute an efficient Value Iteration, propagate beliefs of state in partially observable environments, and choose optimal actions respectively. Backpropagating gradients through these RCNNs allows the system to explicitly learn the Transition Model and Reward Function associated with the underlying MDP, serving as an elegant alternative to classical model-based RL. We evaluate the proposed algorithms in simulation, considering a robot planning problem. We demonstrate the capability of our framework to reduce the cost of replanning, learn accurate MDP models, and finally re-plan with learnt models to achieve near-optimal policies.
Generalizations of Divisor Methods to Approval and Score Voting
Venue: arXiv cs.GT 2017
Year: 2017

We introduce several electoral systems for multi-winner elections with approval ballots, generalizing the classical methods of Sainte-Laguë and D'Hondt. Our approach is based on the works of Phragmén and Thiele. In the last section we discuss possible generalizations to score voting.
Can scientists and their institutions become their own open access publishers?
Venue: arXiv cs.DL 2017
Year: 2017

This article offers a personal perspective on the current state of academic publishing, and posits that the scientific community is beset with journals that contribute little valuable knowledge, overload the community's capacity for high-quality peer review, and waste resources. Open access publishing can offer solutions that benefit researchers and other information users, as well as institutions and funders, but commercial journal publishers have influenced open access policies and practices in ways that favor their economic interests over those of other stakeholders in knowledge creation and sharing. One way to free research from constraints on access is the diamond route of open access publishing, in which institutions and funders that produce new knowledge reclaim responsibility for publication via institutional journals or other open platforms. I argue that research journals (especially those published for profit) may no longer be fit for purpose, and hope that readers will consider whether the time has come to put responsibility for publishing back into the hands of researchers and their institutions. The potential advantages and challenges involved in a shift away from for-profit journals in favor of institutional open access publishing are explored.
An efficient exact model for the cell formation problem with a variable number of production cells
Venue: arXiv cs.DS 2017
Year: 2017

The Cell Formation Problem has been studied as an optimization problem in manufacturing for more than 90 years. It consists of grouping machines and parts into manufacturing cells in order to maximize loading of cells and minimize movement of parts from one cell to another. Many heuristic algorithms have been proposed which are doing well even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: the first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-art approaches.
Implicitly Incorporating Morphological Information into Word Embedding
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we propose three novel models to enhance word embedding by implicitly using morphological information. Experiments on word similarity and syntactic analogy show that the implicit models are superior to traditional explicit ones. Our models outperform all state-of-the-art baselines and significantly improve the performance on both tasks. Moreover, our performance on the smallest corpus is similar to the performance of CBOW on the corpus which is five times the size of ours. Parameter analysis indicates that the implicit models can supplement semantic information during the word embedding training process.