OpenRaiser/Intern-Atlas huggingface dataset:
An Algebraic Formalization of Forward and Forward-backward Algorithms
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we propose an algebraic formalization of the two important classes of dynamic programming algorithms called forward and forward-backward algorithms. They are generalized extensively in this study so that a wide range of other existing algorithms is subsumed. Forward algorithms generalized in this study subsume the ordinary forward algorithm on trellises for sequence labeling, the inside algorithm on derivation forests for CYK parsing, a unidirectional message passing on acyclic factor graphs, the forward mode of automatic differentiation on computation graphs with addition and multiplication, and so on. In addition, we reveal algebraic structures underlying complicated computation with forward algorithms. By the aid of the revealed algebraic structures, we also propose a systematic framework to design complicated variants of forward algorithms. Forward-backward algorithms generalized in this study subsume the ordinary forward-backward algorithm on trellises for sequence labeling, the inside-outside algorithm on derivation forests for CYK parsing, the sum-product algorithm on acyclic factor graphs, the reverse mode of automatic differentiation (a.k.a. back propagation) on computation graphs with addition and multiplication, and so on. We also propose an algebraic characterization of what can be computed by forward-backward algorithms and elucidate the relationship between forward and forward-backward algorithms.
A Heuristic Process for GUI Widget Matching Across Application Versions
Venue: arXiv cs.SE 2017
Year: 2017

This paper introduces an automated heuristic process able to achieve high accuracy when matching graphical user interface widgets across multiple versions of a target application. The proposed implementation is flexible as it allows full customization of the process and easy integration with existing tools for long term graphical user interface test case maintenance, software visualization and analysis.
Unsupervised Learning of Morphological Forests
Venue: arXiv cs.CL 2017
Year: 2017

This paper focuses on unsupervised modeling of morphological families, collectively comprising a forest over the language vocabulary. This formulation enables us to capture edgewise properties reflecting single-step morphological derivations, along with global distributional properties of the entire forest. These global properties constrain the size of the affix set and encourage formation of tight morphological families. The resulting objective is solved using Integer Linear Programming (ILP) paired with contrastive estimation. We train the model by alternating between optimizing the local log-linear model and the global ILP objective. We evaluate our system on three tasks: root detection, clustering of morphological families and segmentation. Our experiments demonstrate that our model yields consistent gains in all three tasks compared with the best published results.
DyAdHyTM: A Low Overhead Dynamically Adaptive Hybrid Transactional Memory on Big Data Graphs
Venue: arXiv cs.DC 2017
Year: 2017

Big data is a buzzword used to describe massive volumes of data that provides opportunities of exploring new insights through data analytics. However, big data is mostly structured but can be semi-structured or unstructured. It is normally so large that it is not only difficult but also slow to process using traditional computing systems. One of the solutions is to format the data as graph data structures and process them on shared memory architecture to use fast and novel policies such as transactional memory. In most graph applications in big data type problems such as bioinformatics, social networks, and cyber security, graphs are sparse in nature. Due to this sparsity, we have the opportunity to use Transactional Memory (TM) as the synchronization policy for critical sections to speedup applications. At low conflict probability TM performs better than most synchronization policies due to its inherent non-blocking characteristics. TM can be implemented in Software, Hardware or a combination of both. However, hardware TM implementations are fast but limited by scarce hardware resources while software implementations have high overheads which can degrade performance. In this paper, we develop a low overhead, yet simple, dynamically adaptive (i.e. at runtime) hybrid (i.e. combines hardware and software) TM (DyAdHyTM) scheme that combines the best features of both Hardware TM (HTM) and Software TM (STM) while adapting to application requirements. It performs better than coarse grain lock by up to 8.12x, a low overhead STM by up to 2.68x, a couple of implementations of HTMs (by up to 2.59x), and other HyTMs (by up to 1.55x) for SSCA2 graph benchmark running on a multicore machine with a large shared memory.
Design of a Cognitive VLC Network with Illumination and Handover Requirements
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a cognitive indoor visible light communications (VLC) system, comprised of multiple access points serving primary and secondary users through the orthogonal frequency division multiple access method. A cognitive lighting cell is divided into two non-overlapping regions that distinguish the primary and secondary users based on the region they are located in. Under the assumption of equal-power allocation among subcarriers, each region is defined in terms of its physical area and the number of allocated subcarriers within that region. In this paper, we provide the lighting cell design with cognitive constraints that guarantee fulfilling certain illumination, user mobility, and handover requirements in each cell. We further argue that, under some conditions, a careful assignment of the subcarriers in each region can mitigate the co-channel interference in the overlapping areas of adjacent cells. Numerical results depict the influence of different system parameters, such as user density, on defining both regions. Finally, a realistic example is implemented to assess the performance of the proposed scheme via Monte Carlo simulations.
Tight Bounds for Online Coloring of Basic Graph Classes
Venue: arXiv cs.DS 2017
Year: 2017

We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is $Θ(\log n)$, where $n$ is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size $O(n/\log n)$ or access to a reordering buffer of size $n^{1-ε}$, for any $0<ε\leq 1$. A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural $\textit{First Fit}$ coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms.
Steganalysis of 3D Objects Using Statistics of Local Feature Sets
Venue: arXiv cs.CR 2017
Year: 2017

3D steganalysis aims to identify subtle invisible changes produced in graphical objects through digital watermarking or steganography. Sets of statistical representations of 3D features, extracted from both cover and stego 3D mesh objects, are used as inputs into machine learning classifiers in order to decide whether any information was hidden in the given graphical object. According to previous studies, sets of local geometry features can be used to define the differences between stego and cover-objects. The features proposed in this paper include those representing the local object curvature, vertex normals, the local geometry representation in the spherical coordinate system and are considered in various combinations with others. We also analyze the effectiveness of various 3D feature sets applied for steganalysis based on the Pearson correlation coefficient. The classifiers proposed in this study for discriminating the 3D stego and cover-objects include Support Vector Machine and the Fisher Linear Discriminant ensemble. Three different watermarking and steganographic methods are used for hiding information in the 3D objects used for testing the performance of the proposed steganalysis methodology.
Control Theoretic Approach to Predict Shock Response in Yeast
Venue: arXiv cs.SY 2017
Year: 2017

This report formulates a minimal model based on a control theoretic framework to best describe the dynamics of perfect adaptation shown by the hyper osmotic shock response system in yeast. Using principles from adaptive control and stability theory, we step by step apply system identification methods to build a simple second order linear system with only a few parameters, that can concisely model the High Osmolarity Glycerol (HOG) Mitogen Activated Protein Kinase (MAPK) signaling dynamics. Validation with experimental data demonstrate that the model is sufficient to predict response of yeast to an arbitrary external osmotic shock stimulus.
How to Optimally Allocate Resources for Coded Distributed Computing?
Venue: arXiv cs.IT 2017
Year: 2017

Today's data centers have an abundance of computing resources, hosting server clusters consisting of as many as tens or hundreds of thousands of machines. To execute a complex computing task over a data center, it is natural to distribute computations across many nodes to take advantage of parallel processing. However, as we allocate more and more computing resources to a computation task and further distribute the computations, large amounts of (partially) computed data must be moved between consecutive stages of computation tasks among the nodes, hence the communication load can become the bottleneck. In this paper, we study the optimal allocation of computing resources in distributed computing, in order to minimize the total execution time in distributed computing accounting for both the duration of computation and communication phases. In particular, we consider a general MapReduce-type distributed computing framework, in which the computation is decomposed into three stages: \emph{Map}, \emph{Shuffle}, and \emph{Reduce}. We focus on a recently proposed \emph{Coded Distributed Computing} approach for MapReduce and study the optimal allocation of computing resources in this framework. For all values of problem parameters, we characterize the optimal number of servers that should be used for distributed processing, provide the optimal placements of the Map and Reduce tasks, and propose an optimal coded data shuffling scheme, in order to minimize the total execution time. To prove the optimality of the proposed scheme, we first derive a matching information-theoretic converse on the execution time, then we prove that among all possible resource allocation schemes that achieve the minimum execution time, our proposed scheme uses the exactly minimum possible number of servers.
Inherent Biases of Recurrent Neural Networks for Phonological Assimilation and Dissimilation
Venue: arXiv cs.CL 2017
Year: 2017

A recurrent neural network model of phonological pattern learning is proposed. The model is a relatively simple neural network with one recurrent layer, and displays biases in learning that mimic observed biases in human learning. Single-feature patterns are learned faster than two-feature patterns, and vowel or consonant-only patterns are learned faster than patterns involving vowels and consonants, mimicking the results of laboratory learning experiments. In non-recurrent models, capturing these biases requires the use of alpha features or some other representation of repeated features, but with a recurrent neural network, these elaborations are not necessary.
Feasibility of Principal Component Analysis in hand gesture recognition system
Venue: arXiv cs.CV 2017
Year: 2017

Nowadays actions are increasingly being handled in electronic ways, instead of physical interaction. From earlier times biometrics is used in the authentication of a person. It recognizes a person by using a human trait associated with it like eyes (by calculating the distance between the eyes) and using hand gestures, fingerprint detection, face detection etc. Advantages of using these traits for identification are that they uniquely identify a person and cannot be forgotten or lost. These are unique features of a human being which are being used widely to make the human life simpler. Hand gesture recognition system is a powerful tool that supports efficient interaction between the user and the computer. The main moto of hand gesture recognition research is to create a system which can recognise specific hand gestures and use them to convey useful information for device control. This paper presents an experimental study over the feasibility of principal component analysis in hand gesture recognition system. PCA is a powerful tool for analyzing data. The primary goal of PCA is dimensionality reduction. Frames are extracted from the Sheffield KInect Gesture (SKIG) dataset. The implementation is done by creating a training set and then training the recognizer. It uses Eigen space by processing the eigenvalues and eigenvectors of the images in training set. Euclidean distance with the threshold value is used as similarity metric to recognize the gestures. The experimental results show that PCA is feasible to be used for hand gesture recognition system.
Streaming supercomputing needs workflow-enabled programming-in-the-large
Venue: arXiv cs.DC 2017
Year: 2017

This is a position paper, submitted to the Future Online Analysis Platform Workshop (https://press3.mcs.anl.gov/futureplatform/), which argues that simple data analysis applications are common today, but future online supercomputing workloads will need to couple multiple advanced technologies (streams, caches, analysis, and simulations) to rapidly deliver scientific results. Each of these technologies are active research areas when integrated with high-performance computing. These components will interact in complex ways, therefore coupling them needs to be programmed. Programming in the large, on top of existing applications, enables us to build much more capable applications and to productively manage this complexity.
Software Defined Media: Virtualization of Audio-Visual Services
Venue: arXiv cs.MM 2017
Year: 2017

Internet-native audio-visual services are witnessing rapid development. Among these services, object-based audio-visual services are gaining importance. In 2014, we established the Software Defined Media (SDM) consortium to target new research areas and markets involving object-based digital media and Internet-by-design audio-visual environments. In this paper, we introduce the SDM architecture that virtualizes networked audio-visual services along with the development of smart buildings and smart cities using Internet of Things (IoT) devices and smart building facilities. Moreover, we design the SDM architecture as a layered architecture to promote the development of innovative applications on the basis of rapid advancements in software-defined networking (SDN). Then, we implement a prototype system based on the architecture, present the system at an exhibition, and provide it as an SDM API to application developers at hackathons. Various types of applications are developed using the API at these events. An evaluation of SDM API access shows that the prototype SDM platform effectively provides 3D audio reproducibility and interactiveness for SDM applications.
Learning Non-local Image Diffusion for Image Denoising
Venue: arXiv cs.CV 2017
Year: 2017

Image diffusion plays a fundamental role for the task of image denoising. Recently proposed trainable nonlinear reaction diffusion (TNRD) model defines a simple but very effective framework for image denoising. However, as the TNRD model is a local model, the diffusion behavior of which is purely controlled by information of local patches, it is prone to create artifacts in the homogenous regions and over-smooth highly textured regions, especially in the case of strong noise levels. Meanwhile, it is widely known that the non-local self-similarity (NSS) prior stands as an effective image prior for image denoising, which has been widely exploited in many non-local methods. In this work, we are highly motivated to embed the NSS prior into the TNRD model to tackle its weaknesses. In order to preserve the expected property that end-to-end training is available, we exploit the NSS prior by a set of non-local filters, and derive our proposed trainable non-local reaction diffusion (TNLRD) model for image denoising. Together with the local filters and influence functions, the non-local filters are learned by employing loss-specific training. The experimental results show that the trained TNLRD model produces visually plausible recovered images with more textures and less artifacts, compared to its local versions. Moreover, the trained TNLRD model can achieve strongly competitive performance to recent state-of-the-art image denoising methods in terms of peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM).
Renyi Differential Privacy
Venue: arXiv cs.CR 2017
Year: 2017

We propose a natural relaxation of differential privacy based on the Renyi divergence. Closely related notions have appeared in several recent papers that analyzed composition of differentially private mechanisms. We argue that the useful analytical tool can be used as a privacy definition, compactly and accurately representing guarantees on the tails of the privacy loss. We demonstrate that the new definition shares many important properties with the standard definition of differential privacy, while additionally allowing tighter analysis of composite heterogeneous mechanisms.
R$^3$PUF: A Highly Reliable Memristive Device based Reconfigurable PUF
Venue: arXiv cs.ET 2017
Year: 2017

We present a memristive device based R$ ^3 $PUF construction achieving highly desired PUF properties, which are not offered by most current PUF designs: (1) High reliability, almost 100\% that is crucial for PUF-based cryptographic key generations, significantly reducing, or even eliminating the expensive overhead of on-chip error correction logic and the associated helper on-chip data storage or off-chip storage and transfer. (2) Reconfigurability, while current PUF designs rarely exhibit such an attractive property. We validate our R$ ^3 $PUF via extensive Monte-Carlo simulations in Cadence based on parameters of real devices. The R$ ^3 $PUF is simple, cost-effective and easy to manage compared to other PUF constructions exhibiting high reliability or reconfigurability. None of previous PUF constructions is able to provide both desired high reliability and reconfigurability concurrently.
Toward high-performance online HCCR: a CNN approach with DropDistortion, path signature and spatial stochastic max-pooling
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents an investigation of several techniques that increase the accuracy of online handwritten Chinese character recognition (HCCR). We propose a new training strategy named DropDistortion to train a deep convolutional neural network (DCNN) with distorted samples. DropDistortion gradually lowers the degree of character distortion during training, which allows the DCNN to better generalize. Path signature is used to extract effective features for online characters. Further improvement is achieved by employing spatial stochastic max-pooling as a method of feature map distortion and model averaging. Experiments were carried out on three publicly available datasets, namely CASIA-OLHWDB 1.0, CASIA-OLHWDB 1.1, and the ICDAR2013 online HCCR competition dataset. The proposed techniques yield state-of-the-art recognition accuracies of 97.67%, 97.30%, and 97.99%, respectively.
An analysis of core- and chip-level architectural features in four generations of Intel server processors
Venue: arXiv cs.PF 2017
Year: 2017

This paper presents a survey of architectural features among four generations of Intel server processors (Sandy Bridge, Ivy Bridge, Haswell, and Broad- well) with a focus on performance with floating point workloads. Starting on the core level and going down the memory hierarchy we cover instruction throughput for floating-point instructions, L1 cache, address generation capabilities, core clock speed and its limitations, L2 and L3 cache bandwidth and latency, the impact of Cluster on Die (CoD) and cache snoop modes, and the Uncore clock speed. Using microbenchmarks we study the influence of these factors on code performance. This insight can then serve as input for analytic performance models. We show that the energy efficiency of the LINPACK and HPCG benchmarks can be improved considerably by tuning the Uncore clock speed without sacrificing performance, and that the Graph500 benchmark performance may profit from a suitable choice of cache snoop mode settings.
On the Total Energy Efficiency of Cell-Free Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

We consider the cell-free massive multiple-input multiple-output (MIMO) downlink, where a very large number of distributed multiple-antenna access points (APs) serve many single-antenna users in the same time-frequency resource. A simple (distributed) conjugate beamforming scheme is applied at each AP via the use of local channel state information (CSI). This CSI is acquired through time-division duplex operation and the reception of uplink training signals transmitted by the users. We derive a closed-form expression for the spectral efficiency taking into account the effects of channel estimation errors and power control. This closed-form result enables us to analyze the effects of backhaul power consumption, the number of APs, and the number of antennas per AP on the total energy efficiency, as well as, to design an optimal power allocation algorithm. The optimal power allocation algorithm aims at maximizing the total energy efficiency, subject to a per-user spectral efficiency constraint and a per-AP power constraint. Compared with the equal power control, our proposed power allocation scheme can double the total energy efficiency. Furthermore, we propose AP selections schemes, in which each user chooses a subset of APs, to reduce the power consumption caused by the backhaul links. With our proposed AP selection schemes, the total energy efficiency increases significantly, especially for large numbers of APs. Moreover, under a requirement of good quality-of-service for all users, cell-free massive MIMO outperforms the colocated counterpart in terms of energy efficiency.