OpenRaiser/Intern-Atlas huggingface dataset:
Caching under Content Freshness Constraints
Venue: arXiv cs.NI 2017
Year: 2017

Several real-time delay-sensitive applications pose varying degrees of freshness demands on the requested content. The performance of cache replacement policies that are agnostic to these demands is likely to be sub-optimal. Motivated by this concern, in this paper, we study caching policies under a request arrival process which incorporates user freshness demands. We consider the performance metric to be the steady-state cache hit probability. We first provide a universal upper bound on the performance of any caching policy. We then analytically obtain the content-wise hit-rates for the Least Popular (LP) policy and provide sufficient conditions for the asymptotic optimality of cache performance under this policy. Next, we obtain an accurate approximation for the LRU hit-rates in the regime of large content population. To this end, we map the characteristic time of a content in the LRU policy to the classical Coupon Collector's Problem and show that it sharply concentrates around its mean. Further, we develop modified versions of these policies which eject cache redundancies present in the form of stale contents. Finally, we propose a new policy which outperforms the above policies by explicitly using freshness specifications of user requests to prioritize among the cached contents. We corroborate our analytical insights with extensive simulations.
Kernel Robust Bias-Aware Prediction under Covariate Shift
Venue: arXiv cs.LG 2017
Year: 2017

Under covariate shift, training (source) data and testing (target) data differ in input space distribution, but share the same conditional label distribution. This poses a challenging machine learning task. Robust Bias-Aware (RBA) prediction provides the conditional label distribution that is robust to the worstcase logarithmic loss for the target distribution while matching feature expectation constraints from the source distribution. However, employing RBA with insufficient feature constraints may result in high certainty predictions for much of the source data, while leaving too much uncertainty for target data predictions. To overcome this issue, we extend the representer theorem to the RBA setting, enabling minimization of regularized expected target risk by a reweighted kernel expectation under the source distribution. By applying kernel methods, we establish consistency guarantees and demonstrate better performance of the RBA classifier than competing methods on synthetically biased UCI datasets as well as datasets that have natural covariate shift.
Active Robotic Mapping through Deep Reinforcement Learning
Venue: arXiv cs.RO 2017
Year: 2017

We propose an approach to learning agents for active robotic mapping, where the goal is to map the environment as quickly as possible. The agent learns to map efficiently in simulated environments by receiving rewards corresponding to how fast it constructs an accurate map. In contrast to prior work, this approach learns an exploration policy based on a user-specified prior over environment configurations and sensor model, allowing it to specialize to the specifications. We evaluate the approach through a simulated Disaster Mapping scenario and find that it achieves performance slightly better than a near-optimal myopic exploration scheme, suggesting that it could be useful in more complicated problem scenarios.
Optimizing Wirelessly Powered Crowd Sensing: Trading energy for data
Venue: arXiv cs.IT 2017
Year: 2017

To overcome the limited coverage in traditional wireless sensor networks, \emph{mobile crowd sensing} (MCS) has emerged as a new sensing paradigm. To achieve longer battery lives of user devices and incentive human involvement, this paper presents a novel approach that seamlessly integrates MCS with wireless power transfer, called \emph{wirelessly powered crowd sensing} (WPCS), for supporting crowd sensing with energy consumption and offering rewards as incentives. The optimization problem is formulated to simultaneously maximize the data utility and minimize the energy consumption for service operator, by jointly controlling wireless-power allocation at the \emph{access point} (AP) as well as sensing-data size, compression ratio, and sensor-transmission duration at \emph{mobile sensor} (MS). Given the fixed compression ratios, the optimal power allocation policy is shown to have a \emph{threshold}-based structure with respect to a defined \emph{crowd-sensing priority} function for each MS. Given fixed sensing-data utilities, the compression policy achieves the optimal compression ratio. Extensive simulations are also presented to verify the efficiency of the contributed mechanisms.
Compute--Forward Multiple Access (CFMA): Practical Code Design
Venue: arXiv cs.IT 2017
Year: 2017

We present a practical strategy that aims to attain rate points on the dominant face of the multiple access channel capacity using a standard low complexity decoder. This technique is built upon recent theoretical developments of Zhu and Gastpar on compute-forward multiple access (CFMA) which achieves the capacity of the multiple access channel using a sequential decoder. We illustrate this strategy with off-the-shelf LDPC codes. In the first stage of decoding, the receiver first recovers a linear combination of the transmitted codewords using the sum-product algorithm (SPA). In the second stage, by using the recovered sum-of-codewords as side information, the receiver recovers one of the two codewords using a modified SPA, ultimately recovering both codewords. The main benefit of recovering the sum-of-codewords instead of the codeword itself is that it allows to attain points on the dominant face of the multiple access channel capacity without the need of rate-splitting or time sharing while maintaining a low complexity in the order of a standard point-to-point decoder. This property is also shown to be crucial for some applications, e.g., interference channels. For all the simulations with single-layer binary codes, our proposed practical strategy is shown to be within \SI{1.7}{\decibel} of the theoretical limits, without explicit optimization on the off-the-self LDPC codes.
Principles of Neuromorphic Photonics
Venue: arXiv cs.ET 2017
Year: 2017

In an age overrun with information, the ability to process reams of data has become crucial. The demand for data will continue to grow as smart gadgets multiply and become increasingly integrated into our daily lives. Next-generation industries in artificial intelligence services and high-performance computing are so far supported by microelectronic platforms. These data-intensive enterprises rely on continual improvements in hardware. Their prospects are running up against a stark reality: conventional one-size-fits-all solutions offered by digital electronics can no longer satisfy this need, as Moore's law (exponential hardware scaling), interconnection density, and the von Neumann architecture reach their limits. With its superior speed and reconfigurability, analog photonics can provide some relief to these problems; however, complex applications of analog photonics have remained largely unexplored due to the absence of a robust photonic integration industry. Recently, the landscape for commercially-manufacturable photonic chips has been changing rapidly and now promises to achieve economies of scale previously enjoyed solely by microelectronics. The scientific community has set out to build bridges between the domains of photonic device physics and neural networks, giving rise to the field of \emph{neuromorphic photonics}. This article reviews the recent progress in integrated neuromorphic photonics. We provide an overview of neuromorphic computing, discuss the associated technology (microelectronic and photonic) platforms and compare their metric performance. We discuss photonic neural network approaches and challenges for integrated neuromorphic photonic processors while providing an in-depth description of photonic neurons and a candidate interconnection architecture. We conclude with a future outlook of neuro-inspired photonic processing.
An introduction to Graph Data Management
Venue: arXiv cs.DB 2017
Year: 2017

A graph database is a database where the data structures for the schema and/or instances are modeled as a (labeled)(directed) graph or generalizations of it, and where querying is expressed by graph-oriented operations and type constructors. In this article we present the basic notions of graph databases, give an historical overview of its main development, and study the main current systems that implement them.
The origins of Zipf's meaning-frequency law
Venue: arXiv cs.CL 2017
Year: 2017

In his pioneering research, G. K. Zipf observed that more frequent words tend to have more meanings, and showed that the number of meanings of a word grows as the square root of its frequency. He derived this relationship from two assumptions: that words follow Zipf's law for word frequencies (a power law dependency between frequency and rank) and Zipf's law of meaning distribution (a power law dependency between number of meanings and rank). Here we show that a single assumption on the joint probability of a word and a meaning suffices to infer Zipf's meaning-frequency law or relaxed versions. Interestingly, this assumption can be justified as the outcome of a biased random walk in the process of mental exploration.
Game-theoretic Network Centrality: A Review
Venue: arXiv cs.AI 2017
Year: 2017

Game-theoretic centrality is a flexible and sophisticated approach to identify the most important nodes in a network. It builds upon the methods from cooperative game theory and network theory. The key idea is to treat nodes as players in a cooperative game, where the value of each coalition is determined by certain graph-theoretic properties. Using solution concepts from cooperative game theory, it is then possible to measure how responsible each node is for the worth of the network. The literature on the topic is already quite large, and is scattered among game-theoretic and computer science venues. We review the main game-theoretic network centrality measures from both bodies of literature and organize them into two categories: those that are more focused on the connectivity of nodes, and those that are more focused on the synergies achieved by nodes in groups. We present and explain each centrality, with a focus on algorithms and complexity.
Transfer learning for diagnosis of congenital abnormalities of the kidney and urinary tract in children based on Ultrasound imaging data
Venue: arXiv cs.CV 2017
Year: 2017

Classification of ultrasound (US) kidney images for diagnosis of congenital abnormalities of the kidney and urinary tract (CAKUT) in children is a challenging task. It is desirable to improve existing pattern classification models that are built upon conventional image features. In this study, we propose a transfer learning-based method to extract imaging features from US kidney images in order to improve the CAKUT diagnosis in children. Particularly, a pre-trained deep learning model (imagenet-caffe-alex) is adopted for transfer learning-based feature extraction from 3-channel feature maps computed from US images, including original images, gradient features, and distanced transform features. Support vector machine classifiers are then built upon different sets of features, including the transfer learning features, conventional imaging features, and their combination. Experimental results have demonstrated that the combination of transfer learning features and conventional imaging features yielded the best classification performance for distinguishing CAKUT patients from normal controls based on their US kidney images.
A New Approach for Measuring Sentiment Orientation based on Multi-Dimensional Vector Space
Venue: arXiv cs.CL 2017
Year: 2017

This study implements a vector space model approach to measure the sentiment orientations of words. Two representative vectors for positive/negative polarity are constructed using high-dimensional vec-tor space in both an unsupervised and a semi-supervised manner. A sentiment ori-entation value per word is determined by taking the difference between the cosine distances against the two reference vec-tors. These two conditions (unsupervised and semi-supervised) are compared against an existing unsupervised method (Turney, 2002). As a result of our experi-ment, we demonstrate that this novel ap-proach significantly outperforms the pre-vious unsupervised approach and is more practical and data efficient as well.
Particle Clustering Machine: A Dynamical System Based Approach
Venue: arXiv cs.LG 2017
Year: 2017

Identification of the clusters from an unlabeled data set is one of the most important problems in Unsupervised Machine Learning. The state of the art clustering algorithms are based on either the statistical properties or the geometric properties of the data set. In this work, we propose a novel method to cluster the data points using dynamical systems theory. After constructing a gradient dynamical system using interaction potential, we prove that the asymptotic dynamics of this system will determine the cluster centers, when the dynamical system is initialized at the data points. Most of the existing heuristic-based clustering techniques suffer from a disadvantage, namely the stochastic nature of the solution. Whereas, the proposed algorithm is deterministic, and the outcome would not change over multiple runs of the proposed algorithm with the same input data. Another advantage of the proposed method is that the number of clusters, which is difficult to determine in practice, does not have to be specified in advance. Simulation results with are presented, and comparisons are made with the existing methods.
IMU2Face: Real-time Gesture-driven Facial Reenactment
Venue: arXiv cs.CV 2017
Year: 2017

We present IMU2Face, a gesture-driven facial reenactment system. To this end, we combine recent advances in facial motion capture and inertial measurement units (IMUs) to control the facial expressions of a person in a target video based on intuitive hand gestures. IMUs are omnipresent, since modern smart-phones, smart-watches and drones integrate such sensors, e.g., for changing the orientation of the screen content, counting steps, or for flight stabilization. Face tracking and reenactment is based on the state-of-the-art real-time Face2Face facial reenactment system. Instead of transferring facial expressions from a source to a target actor, we employ an IMU to track the hand gestures of a source actor and use its orientation to modify the target actor's expressions.
3D Surface-to-Structure Translation using Deep Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Our demonstration shows a system that estimates internal body structures from 3D surface models using deep convolutional neural networks trained on CT (computed tomography) images of the human body. To take pictures of structures inside the body, we need to use a CT scanner or an MRI (Magnetic Resonance Imaging) scanner. However, assuming that the mutual information between outer shape of the body and its inner structure is not zero, we can obtain an approximate internal structure from a 3D surface model based on MRI and CT image database. This suggests that we could know where and what kind of disease a person is likely to have in his/her body simply by 3D scanning surface of the body. As a first prototype, we developed a system for estimating internal body structures from surface models based on Visible Human Project DICOM CT Datasets from the University of Iowa Magnetic Resonance Research Facility.
On the Scalability of the GPUexplore Explicit-State Model Checker
Venue: arXiv cs.DC 2017
Year: 2017

The use of graphics processors (GPUs) is a promising approach to speed up model checking to such an extent that it becomes feasible to instantly verify software systems during development. GPUexplore is an explicit-state model checker that runs all its computations on the GPU. Over the years it has been extended with various techniques, and the possibilities to further improve its performance have been continuously investigated. In this paper, we discuss how the hash table of the tool works, which is at the heart of its functionality. We propose an alteration of the hash table that in isolated experiments seems promising, and analyse its effect when integrated in the tool. Furthermore, we investigate the current scalability of GPUexplore, by experimenting both with input models of varying sizes and running the tool on one of the latest GPUs of NVIDIA.
A Study of Implanted and Wearable Body Sensor Networks
Venue: arXiv cs.NI 2018
Year: 2018

Recent advances in intelligent sensors, microelectronics and integrated circuit, system-on-chip design and low power wireless communication introduced the development of miniaturised and autonomous sensor nodes. These tiny sensor nodes can be deployed to develop a proactive Body Sensor Network (BSN). The rapid advancement in ultra low-power RF (radio frequency) technology enables invasive and non-invasive devices to communicate with a remote station. This communication revolutionizes healthcare system by enabling long term health monitoring of a patient and providing real time feedback to the medical experts. In this paper, we present In-body and On-body communication networks with a special focus on the methodologies of wireless communication between implanted medical devices with external monitoring equipment and recent technological growth in both areas. We also discuss open issues and challenges in a BSN.
Self-Reference Ultra-Wideband Systems
Venue: arXiv cs.NI 2018
Year: 2018

Towards employing low complexity transceivers for signal reception in Ultra-Wideband (UWB) systems, Transmitted Reference (TR) and Differential TR (DTR) schemes have attracted researchers attention. In this letter, we introduce an alternative, less complex scheme, called Self Reference (SR) UWB transceiver, which uses a modified replica of the received signal itself as reference pulse, resulting in double data rates compared to TR schemes. Moreover, SR eliminates the need for delay lines at the receiver side, which constitute a major drawback of the conventional TR and DTR schemes, while it also requires no channel estimations, resulting in lower complexity implementations and power savings. The performance of the SR scheme is investigated in high-frequency (HF) channels, showing that it offers a better or comparable performance to that of DTR, depending on the channel conditions.
Having Fun with Lambert W(x) Function
Venue: arXiv cs.MS 2018
Year: 2018

This short note presents the Lambert W(x) function and its possible application in the framework of physics related to the Pierre Auger Observatory. The actual numerical implementation in C++ consists of Halley's and Fritsch's iteration with branch-point expansion, asymptotic series and rational fits as initial approximations.
A generalization of Hopcroft-Karp algorithm for semi-matchings and covers in bipartite graphs (Maximum semi-matching problem in bipartite graphs)
Venue: arXiv cs.DS 2018
Year: 2018

An $(f,g)$-semi-matching in a bipartite graph $G=(U \cup V,E)$ is a set of edges $M \subseteq E$ such that each vertex $u\in U$ is incident with at most $f(u)$ edges of $M$, and each vertex $v\in V$ is incident with at most $g(v)$ edges of $M$. In this paper we give an algorithm that for a graph with $n$ vertices and $m$ edges, $n\le m$, constructs a maximum $(f,g)$-semi-matching in running time $O(m\cdot \min (\sqrt{\sum_{u\in U}f(u)}, \sqrt{\sum_{v\in V}g(v)}))$. Using the reduction of [5], our result on maximum $(f,g)$-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time $O(\sqrt{n}m \log n)$.
Finding Efficient Region in The Plane with Line segments
Venue: arXiv cs.DS 2018
Year: 2018

Let $\mathscr O$ be a set of $n$ disjoint obstacles in $\mathbb{R}^2$, $\mathscr M$ be a moving object. Let $s$ and $l$ denote the starting point and maximum path length of the moving object $\mathscr M$, respectively. Given a point $p$ in ${R}^2$, we say the point $p$ is achievable for $\mathscr M$ such that $π(s,p)\leq l$, where $π(\cdot)$ denotes the shortest path length in the presence of obstacles. One is to find a region $\mathscr R$ such that, for any point $p\in \mathbb{R}^2$, if it is achievable for $\mathscr M$, then $p\in \mathscr R$; otherwise, $p\notin \mathscr R$. In this paper, we restrict our attention to the case of line-segment obstacles. To tackle this problem, we develop three algorithms. We first present a simpler-version algorithm for the sake of intuition. Its basic idea is to reduce our problem to computing the union of a set of circular visibility regions (CVRs). This algorithm takes $O(n^3)$ time. By analysing its dominant steps, we break through its bottleneck by using the short path map (SPM) technique to obtain those circles (unavailable beforehand), yielding an $O(n^2\log n)$ algorithm. Owing to the finding above, the third algorithm also uses the SPM technique. It however, does not continue to construct the CVRs. Instead, it directly traverses each region of the SPM to trace the boundaries, the final algorithm obtains $O(n\log n)$ complexity.
A Linear Kernel for Planar Total Dominating Set
Venue: arXiv cs.DS 2018
Year: 2018

A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when parameterized by the solution size. By the meta-theorem of Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how such a kernel can be effectively constructed, and how to obtain explicit reduction rules with reasonably small constants. Following the approach of Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the solution. This result complements several known constructive linear kernels on planar graphs for other domination problems such as Dominating Set, Edge Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue Dominating Set.
Circuit complexity and Problem structure in Hamming space
Venue: arXiv cs.CC 2018
Year: 2018

This paper describes about relation between circuit complexity and accept inputs structure in Hamming space by using almost all monotone circuit that emulate deterministic Turing machine (DTM). Circuit family that emulate DTM are almost all monotone circuit family except some NOT-gate which connect input variables (like negation normal form (NNF)). Therefore, we can analyze DTM limitation by using this NNF Circuit family. NNF circuit have symmetry of OR-gate input line, so NNF circuit cannot identify from OR-gate output line which of OR-gate input line is 1. So NNF circuit family cannot compute sandwich structure effectively (Sandwich structure is two accept inputs that sandwich reject inputs in Hamming space). NNF circuit have to use unique AND-gate to identify each different vector of sandwich structure. That is, we can measure problem complexity by counting different vectors. Some decision problem have characteristic in sandwich structure. Different vectors of Negate HornSAT problem are at most constant length because we can delete constant part of each negative literal in Horn clauses by using definite clauses. Therefore, number of these different vector is at most polynomial size. The other hand, we can design high complexity problem with almost perfct nonlinear (APN) function.