OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Selection of Virtual Machines for Application Servers in Cloud Environments
Venue: arXiv cs.DC 2016
Year: 2016

Autoscaling is a hallmark of cloud computing as it allows flexible just-in-time allocation and release of computational resources in response to dynamic and often unpredictable workloads. This is especially important for web applications whose workload is time dependent and prone to flash crowds. Most of them follow the 3-tier architectural pattern, and are divided into presentation, application/domain and data layers. In this work we focus on the application layer. Reactive autoscaling policies of the type "Instantiate a new Virtual Machine (VM) when the average server CPU utilisation reaches X%" have been used successfully since the dawn of cloud computing. But which VM type is the most suitable for the specific application at the moment remains an open question. In this work, we propose an approach for dynamic VM type selection. It uses a combination of online machine learning techniques, works in real time and adapts to changes in the users' workload patterns, application changes as well as middleware upgrades and reconfigurations. We have developed a prototype, which we tested with the CloudStone benchmark deployed on AWS EC2. Results show that our method quickly adapts to workload changes and reduces the total cost compared to the industry standard approach.
On the circuit complexity of the standard and the Karatsuba methods of multiplying integers
Venue: arXiv cs.DS 2016
Year: 2016

We provide accurate upper bounds on the Boolean circuit complexity of the standard and the Karatsuba methods of integer multiplication
Find an Optimal Path in Static System and Dynamical System within Polynomial Runtime
Venue: arXiv cs.DS 2016
Year: 2016

We study an ancient problem that in a static or dynamical system, sought an optimal path, which the context always means within an extremal condition. In fact, through those discussions about this theme, we established a universal essential calculated model to serve for these complex systems. Meanwhile we utilize the sample space to character the system. These contents in this paper would involve in several major areas including the geometry, probability, graph algorithms and some prior approaches, which stands the ultimately subtle linear algorithm to solve this class problem. Along with our progress, our discussion would demonstrate more general meaning and robust character, which provides clear ideas or notion to support our concrete applications, who work in a more popular complex system.
Wikipedia Tools for Google Spreadsheets
Venue: arXiv cs.IR 2016
Year: 2016

In this paper, we introduce the Wikipedia Tools for Google Spreadsheets. Google Spreadsheets is part of a free, Web-based software office suite offered by Google within its Google Docs service. It allows users to create and edit spreadsheets online, while collaborating with other users in realtime. Wikipedia is a free-access, free-content Internet encyclopedia, whose content and data is available, among other means, through an API. With the Wikipedia Tools for Google Spreadsheets, we have created a toolkit that facilitates working with Wikipedia data from within a spreadsheet context. We make these tools available as open-source on GitHub [https://github.com/tomayac/wikipedia-tools-for-google-spreadsheets], released under the permissive Apache 2.0 license.
A Semi-Automated Method for Object Segmentation in Infant's Egocentric Videos to Study Object Perception
Venue: arXiv cs.CV 2016
Year: 2016

Object segmentation in infant's egocentric videos is a fundamental step in studying how children perceive objects in early stages of development. From the computer vision perspective, object segmentation in such videos pose quite a few challenges because the child's view is unfocused, often with large head movements, effecting in sudden changes in the child's point of view which leads to frequent change in object properties such as size, shape and illumination. In this paper, we develop a semi-automated, domain specific, method to address these concerns and facilitate the object annotation process for cognitive scientists allowing them to select and monitor the object under segmentation. The method starts with an annotation from the user of the desired object and employs graph cut segmentation and optical flow computation to predict the object mask for subsequent video frames automatically. To maintain accuracy, we use domain specific heuristic rules to re-initialize the program with new user input whenever object properties change dramatically. The evaluations demonstrate the high speed and accuracy of the presented method for object segmentation in voluminous egocentric videos. We apply the proposed method to investigate potential patterns in object distribution in child's view at progressive ages.
Scalability and Total Recall with Fast CoveringLSH
Venue: arXiv cs.DB 2016
Year: 2016

Locality-sensitive hashing (LSH) has emerged as the dominant algorithmic technique for similarity search with strong performance guarantees in high-dimensional spaces. A drawback of traditional LSH schemes is that they may have \emph{false negatives}, i.e., the recall is less than 100\%. This limits the applicability of LSH in settings requiring precise performance guarantees. Building on the recent theoretical "CoveringLSH" construction that eliminates false negatives, we propose a fast and practical covering LSH scheme for Hamming space called \emph{Fast CoveringLSH (fcLSH)}. Inheriting the design benefits of CoveringLSH our method avoids false negatives and always reports all near neighbors. Compared to CoveringLSH we achieve an asymptotic improvement to the hash function computation time from $\mathcal{O}(dL)$ to $\mathcal{O}(d + L\log{L})$, where $d$ is the dimensionality of data and $L$ is the number of hash tables. Our experiments on synthetic and real-world data sets demonstrate that \emph{fcLSH} is comparable (and often superior) to traditional hashing-based approaches for search radius up to 20 in high-dimensional Hamming space.
Automatic Face Reenactment
Venue: arXiv cs.CV 2016
Year: 2016

We propose an image-based, facial reenactment system that replaces the face of an actor in an existing target video with the face of a user from a source video, while preserving the original target performance. Our system is fully automatic and does not require a database of source expressions. Instead, it is able to produce convincing reenactment results from a short source video captured with an off-the-shelf camera, such as a webcam, where the user performs arbitrary facial gestures. Our reenactment pipeline is conceived as part image retrieval and part face transfer: The image retrieval is based on temporal clustering of target frames and a novel image matching metric that combines appearance and motion to select candidate frames from the source video, while the face transfer uses a 2D warping strategy that preserves the user's identity. Our system excels in simplicity as it does not rely on a 3D face model, it is robust under head motion and does not require the source and target performance to be similar. We show convincing reenactment results for videos that we recorded ourselves and for low-quality footage taken from the Internet.
LSTM Deep Neural Networks Postfiltering for Improving the Quality of Synthetic Voices
Venue: arXiv cs.SD 2016
Year: 2016

Recent developments in speech synthesis have produced systems capable of outcome intelligible speech, but now researchers strive to create models that more accurately mimic human voices. One such development is the incorporation of multiple linguistic styles in various languages and accents. HMM-based Speech Synthesis is of great interest to many researchers, due to its ability to produce sophisticated features with small footprint. Despite such progress, its quality has not yet reached the level of the predominant unit-selection approaches that choose and concatenate recordings of real speech. Recent efforts have been made in the direction of improving these systems. In this paper we present the application of Long-Short Term Memory Deep Neural Networks as a Postfiltering step of HMM-based speech synthesis, in order to obtain closer spectral characteristics to those of natural speech. The results show how HMM-voices could be improved using this approach.
The physical and circuit-theoretic significance of the Memristor : Full version
Venue: arXiv cs.ET 2016
Year: 2016

It is observed that the inductive and capacitive features of the memristor reflect (and are a quintessence of) such features of any resistor. The very presence of the voltage and current state variables, associated by their electrodynamics sense with electrical and magnetic fields, in the resistive characteristic v = f(i), forces any resister to accumulate some magnetic and electrostatic fields and energies around itself, i.e. L and C elements are always present. From the circuit-theoretic point of view, the role of the memristor is seen, first of all, in the elimination of the use of a unique v(i). This makes circuits with hysteresis characteristics relevant, and also suggests that the concept of memristor should influence the basic problem of definition of nonlinearity. Since the memristor mainly originates from the resistor, it was found necessary to overview some unusual cases of resistive circuits. The present opinion is that the framework of basic circuit theory and its connection with applications should be logically expanded in order to naturally include the new element.
Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
Venue: arXiv cs.LG 2016
Year: 2016

We introduce a method to train Binarized Neural Networks (BNNs) - neural networks with binary weights and activations at run-time. At training-time the binary weights and activations are used for computing the parameters gradients. During the forward pass, BNNs drastically reduce memory size and accesses, and replace most arithmetic operations with bit-wise operations, which is expected to substantially improve power-efficiency. To validate the effectiveness of BNNs we conduct two sets of experiments on the Torch7 and Theano frameworks. On both, BNNs achieved nearly state-of-the-art results over the MNIST, CIFAR-10 and SVHN datasets. Last but not least, we wrote a binary matrix multiplication GPU kernel with which it is possible to run our MNIST BNN 7 times faster than with an unoptimized GPU kernel, without suffering any loss in classification accuracy. The code for training and running our BNNs is available on-line.
Efficient Reassembling of Graphs, Part 2: The Balanced Case
Venue: arXiv cs.CC 2016
Year: 2016

The reassembling of a simple connected graph G = (V,E) is an abstraction of a problem arising in earlier studies of network analysis. The reassembling process has a simple formulation (there are several equivalent formulations) relative to a binary tree B (reassembling tree), with root node at the top and $n$ leaf nodes at the bottom, where every cross-section corresponds to a partition of V such that: - the bottom (or first) cross-section (all the leaves) is the finest partition of V with n one-vertex blocks, - the top (or last) cross-section (the root) is the coarsest partition with a single block, the entire set V, - a node (or block) in an intermediate cross-section (or partition) is the result of merging its two children nodes (or blocks) in the cross-section (or partition) below it. The maximum edge-boundary degree encountered during the reassembling process is what we call the alpha-measure of the reassembling, and the sum of all edge-boundary degrees is its beta-measure. The alpha-optimization (resp. beta-optimization) of the reassembling of G is to determine a reassembling tree B that minimizes its alpha-measure (resp. beta-measure). There are different forms of reassembling. In an earlier report, we studied linear reassembling, which is the case when the height of B is (n-1). In this report, we study balanced reassembling, when B has height [log n]. The two main results in this report are the NP-hardness of alpha-optimization and beta-optimization of balanced reassembling. The first result is obtained by a sequence of polynomial-time reductions from minimum bisection of graphs (known to be NP-hard), and the second by a sequence of polynomial-time reductions from clique cover of graphs (known to be NP-hard).
Challenges of Integrating A Priori Information Efficiently in the Discovery of Spatio-Temporal Objects in Large Databases
Venue: arXiv cs.CV 2016
Year: 2016

Using the knowledge discovery framework, it is possible to explore object databases and extract groups of objects with highly heterogeneous movement behavior by efficiently integrating a priori knowledge through interacting with the framework. The whole process is modular expandable and is therefore adaptive to any problem formulation. Further, the flexible use of different information allocation processes reveal a great potential to efficiently incorporate the a priori knowledge of different users in different ways. Therefore, the stepwise knowledge discovery process embedded in the knowledge discovery framework is described in detail to point out the flexibility of such a system incorporating object databases from different applications. The described framework can be used to gain knowledge out of object databases in many different fields. This knowledge can be used to gain further insights and improve the understanding of underlying phenomena. The functionality of the proposed framework is exemplarily demonstrated using a benchmark database based on real biological object data.
Weak oddness as an approximation of oddness and resistance in cubic graphs
Venue: arXiv cs.DM 2016
Year: 2016

We introduce weak oddness $ω_{\textrm w}$, a new measure of uncolourability of cubic graphs, defined as the least number of odd components in an even factor. For every bridgeless cubic graph $G$, $ρ(G)\leω_{\textrm w}(G)\leω(G)$, where $ρ(G)$ denotes the resistance of $G$ and $ω(G)$ denotes the oddness of $G$, so this new measure is an approximation of both oddness and resistance. We demonstrate that there are graphs $G$ satisfying $ρ(G) < ω_{\textrm w}(G) < ω(G)$, and that the difference between any two of those three measures can be arbitrarily large. The construction implies that if we replace a vertex of a cubic graph with a triangle, then its oddness can decrease by an arbitrarily large amount.
Self-organized control for musculoskeletal robots
Venue: arXiv cs.RO 2016
Year: 2016

With the accelerated development of robot technologies, optimal control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of the history of sensor values, guided by the goals, intentions, objectives, learning schemes, and so on planted into it. The idea is that the controller controls the world---the body plus its environment---as reliably as possible. However, in elastically actuated robots this approach faces severe difficulties. This paper advocates for a new paradigm of self-organized control. The paper presents a solution with a controller that is devoid of any functionalities of its own, given by a fixed, explicit and context-free function of the recent history of the sensor values. When applying this controller to a muscle-tendon driven arm-shoulder system from the Myorobotics toolkit, we observe a vast variety of self-organized behavior patterns: when left alone, the arm realizes pseudo-random sequences of different poses but one can also manipulate the system into definite motion patterns. But most interestingly, after attaching an object, the controller gets in a functional resonance with the object's internal dynamics: when given a half-filled bottle, the system spontaneously starts shaking the bottle so that maximum response from the dynamics of the water is being generated. After attaching a pendulum to the arm, the controller drives the pendulum into a circular mode. In this way, the robot discovers dynamical affordances of objects its body is interacting with. We also discuss perspectives for using this controller paradigm for intention driven behavior generation.
Open Sesame: The Password Hashing Competition and Argon2
Venue: arXiv cs.CR 2016
Year: 2016

In this document we present an overview of the background to and goals of the Password Hashing Competition (PHC) as well as the design of its winner, Argon2, and its security requirements and properties.
Time Resource Networks
Venue: arXiv cs.AI 2016
Year: 2016

The problem of scheduling under resource constraints is widely applicable. One prominent example is power management, in which we have a limited continuous supply of power but must schedule a number of power-consuming tasks. Such problems feature tightly coupled continuous resource constraints and continuous temporal constraints. We address such problems by introducing the Time Resource Network (TRN), an encoding for resource-constrained scheduling problems. The definition allows temporal specifications using a general family of representations derived from the Simple Temporal network, including the Simple Temporal Network with Uncertainty, and the probabilistic Simple Temporal Network (Fang et al. (2014)). We propose two algorithms for determining the consistency of a TRN: one based on Mixed Integer Programing and the other one based on Constraint Programming, which we evaluate on scheduling problems with Simple Temporal Constraints and Probabilistic Temporal Constraints.
Busy Beaver Machines and the Observant Otter Heuristic (or How to Tame Dreadful Dragons)
Venue: arXiv cs.FL 2016
Year: 2016

The busy beaver is a well-known specific example of a non-computable function. Whilst many aspect of this problem have been investigated, it is not always easy to find thorough and convincing evidence for the claims made about the maximality of particular machines, and the phenomenal size of some of the numbers involved means that it is not obvious that the problem can be feasibly addressed at all. In this paper we address both of these issues. We discuss a framework in which the busy beaver problem and similar problems may be addressed, and the appropriate processes for providing evidence of claims made. We also show how a simple heuristic, which we call the observant otter, can be used to evaluate machines with an extremely large number of execution steps required to terminate. We also show empirical results for an implementation of this heuristic which show how this heuristic is effective for all known `monster' machines.
Improved Eigenfeature Regularization for Face Identification
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose to divide each class (a person) into subclasses using spatial partition trees which helps in better capturing the intra-personal variances arising from the appearances of the same individual. We perform a comprehensive analysis on within-class and within-subclass eigenspectrums of face images and propose a novel method of eigenspectrum modeling which extracts discriminative features of faces from both within-subclass and total or between-subclass scatter matrices. Effective low-dimensional face discriminative features are extracted for face recognition (FR) after performing discriminant evaluation in the entire eigenspace. Experimental results on popular face databases (AR, FERET) and the challenging unconstrained YouTube Face database show the superiority of our proposed approach on all three databases.
Complexity of regular abstractions of one-counter languages
Venue: arXiv cs.FL 2016
Year: 2016

We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L(A): its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown if appropriate NFA of sub-exponential size exist.
Automatic Sarcasm Detection: A Survey
Venue: arXiv cs.CL 2016
Year: 2016

Automatic sarcasm detection is the task of predicting sarcasm in text. This is a crucial step to sentiment analysis, considering prevalence and challenges of sarcasm in sentiment-bearing text. Beginning with an approach that used speech-based features, sarcasm detection has witnessed great interest from the sentiment analysis community. This paper is the first known compilation of past work in automatic sarcasm detection. We observe three milestones in the research so far: semi-supervised pattern extraction to identify implicit sentiment, use of hashtag-based supervision, and use of context beyond target text. In this paper, we describe datasets, approaches, trends and issues in sarcasm detection. We also discuss representative performance values, shared tasks and pointers to future work, as given in prior works. In terms of resources that could be useful for understanding state-of-the-art, the survey presents several useful illustrations - most prominently, a table that summarizes past papers along different dimensions such as features, annotation techniques, data forms, etc.
Super-Resolved Retinal Image Mosaicing
Venue: arXiv cs.CV 2016
Year: 2016

The acquisition of high-resolution retinal fundus images with a large field of view (FOV) is challenging due to technological, physiological and economic reasons. This paper proposes a fully automatic framework to reconstruct retinal images of high spatial resolution and increased FOV from multiple low-resolution images captured with non-mydriatic, mobile and video-capable but low-cost cameras. Within the scope of one examination, we scan different regions on the retina by exploiting eye motion conducted by a patient guidance. Appropriate views for our mosaicing method are selected based on optic disk tracking to trace eye movements. For each view, one super-resolved image is reconstructed by fusion of multiple video frames. Finally, all super-resolved views are registered to a common reference using a novel polynomial registration scheme and combined by means of image mosaicing. We evaluated our framework for a mobile and low-cost video fundus camera. In our experiments, we reconstructed retinal images of up to 30° FOV from 10 complementary views of 15° FOV. An evaluation of the mosaics by human experts as well as a quantitative comparison to conventional color fundus images encourage the clinical usability of our framework.
Research Priorities for Robust and Beneficial Artificial Intelligence
Venue: arXiv cs.AI 2016
Year: 2016

Success in the quest for artificial intelligence has the potential to bring unprecedented benefits to humanity, and it is therefore worthwhile to investigate how to maximize these benefits while avoiding potential pitfalls. This article gives numerous examples (which should by no means be construed as an exhaustive list) of such worthwhile research aimed at ensuring that AI remains robust and beneficial.