OpenRaiser/Intern-Atlas huggingface dataset:
A Joint Identification Approach for Argumentative Writing Revisions
Venue: arXiv cs.CL 2017
Year: 2017

Prior work on revision identification typically uses a pipeline method: revision extraction is first conducted to identify the locations of revisions and revision classification is then conducted on the identified revisions. Such a setting propagates the errors of the revision extraction step to the revision classification step. This paper proposes an approach that identifies the revision location and the revision type jointly to solve the issue of error propagation. It utilizes a sequence representation of revisions and conducts sequence labeling for revision identification. A mutation-based approach is utilized to update identification sequences. Results demonstrate that our proposed approach yields better performance on both revision location extraction and revision type classification compared to a pipeline baseline.
Minimum Enclosing Circle of a Set of Static Points with Dynamic Weight from One Free Point
Venue: arXiv cs.CG 2017
Year: 2017

Given a set $S$ of $n$ static points and a free point $p$ in the Euclidean plane, we study a new variation of the minimum enclosing circle problem, in which a dynamic weight that equals to the reciprocal of the distance from the free point $p$ to the undetermined circle center is included. In this work, we prove the optimal solution of the new problem is unique and lies on the boundary of the farthest-point Voronoi diagram of $S$, once $p$ does not coincide with any vertex of the convex hull of $S$. We propose a tree structure constructed from the boundary of the farthest-point Voronoi diagram and use the hierarchical relationship between edges to locate the optimal solution. The plane could be divide into at most $3n-4$ non-overlapping regions. When $p$ lies in one of the regions, the optimal solution locates at one node or lies on the interior of one edge in the boundary of the farthest-point Voronoi diagram. Moreover, we apply the new variation to calculate the maximum displacement of one point $p$ under the condition that the displacements of points in $S$ are restricted in 2D rigid motion.
Optical Flow-based 3D Human Motion Estimation from Monocular Video
Venue: arXiv cs.CV 2017
Year: 2017

We present a generative method to estimate 3D human motion and body shape from monocular video. Under the assumption that starting from an initial pose optical flow constrains subsequent human motion, we exploit flow to find temporally coherent human poses of a motion sequence. We estimate human motion by minimizing the difference between computed flow fields and the output of an artificial flow renderer. A single initialization step is required to estimate motion over multiple frames. Several regularization functions enhance robustness over time. Our test scenarios demonstrate that optical flow effectively regularizes the under-constrained problem of human shape and motion estimation from monocular video.
Two strings at Hamming distance 1 cannot be both quasiperiodic
Venue: arXiv cs.FL 2017
Year: 2017

We present a generalization of a known fact from combinatorics on words related to periodicity into quasiperiodicity. A string is called periodic if it has a period which is at most half of its length. A string $w$ is called quasiperiodic if it has a non-trivial cover, that is, there exists a string $c$ that is shorter than $w$ and such that every position in $w$ is inside one of the occurrences of $c$ in $w$. It is a folklore fact that two strings that differ at exactly one position cannot be both periodic. Here we prove a more general fact that two strings that differ at exactly one position cannot be both quasiperiodic. Along the way we obtain new insights into combinatorics of quasiperiodicities.
Test Case Generation for Program Repair: A Study of Feasibility and Effectiveness
Venue: arXiv cs.SE 2017
Year: 2017

Among the many different kinds of program repair techniques, one widely studied family of techniques is called test suite based repair. Test-suites are in essence input-output specifications and are therefore typically inadequate for completely specifying the expected behavior of the program under repair. Consequently, the patches generated by test suite based program repair techniques pass the test suite, yet may be incorrect. Patches that are overly specific to the used test suite and fail to generalize to other test cases are called overfitting patches. In this paper, we investigate the feasibility and effectiveness of test case generation in alleviating the overfitting issue. We propose two approaches for using test case generation to improve test suite based repair, and perform an extensive evaluation of the effectiveness of the proposed approaches in enabling better test suite based repair on 224 bugs of the Defects4J repository. The results indicate that test case generation can change the resulting patch, but is not effective at turning incorrect patches into correct ones. We identify the problems related with the ineffectiveness, and anticipate that our results and findings will lead to future research to build test-case generation techniques that are tailored to automatic repair systems.
Completeness of Hoare Logic over Nonstandard Models
Venue: arXiv cs.LO 2017
Year: 2017

The nonstandard approach to program semantics has successfully resolved the completeness problem of Floyd-Hoare logic. The known versions of nonstandard semantics, the Hungary semantics and axiomatic semantics, are so general that they are absent either from mathematical elegance or from practical usefulness. The aim of this paper is to exhibit a not only mathematically elegant but also practically useful nonstandard semantics. A basic property of computable functions in the standard model $N$ of Peano arithmetic $PA$ is $Σ_1$-definability. However, the functions induced by the standard interpretation of while-programs $S$ in nonstandard models $M$ of $PA$ are not always arithmetical. The problem consists in that the standard termination of $S$ in $M$ uses the finiteness in $N$, which is not the finiteness in $M$. To this end, we shall give a new interpretation of $S$ in $M$ such that the termination of $S$ uses $M$-finiteness, and the functions produced by $S$ in all models of $PA$ have the uniform $Σ_1$-definability. Then we define, based on the new semantics of while-programs, a new semantics of Hoare logic in nonstandard models of $PA$, and show that the standard axiom system of Hoare logic is sound and complete w.r.t. the new semantics. It will be established, in $PA$, that the Hungary semantics and axiomatic semantics coincide with the new semantics of while-programs. Moreover, various comparisons with the previous results, usefulness of the nonstandard semantics, and remarks on the completeness issues are presented.
Automatic Library Version Identification, an Exploration of Techniques
Venue: arXiv cs.CR 2017
Year: 2017

This paper is the result of a two month research internship on the topic of library version identification. In this paper, ideas and techniques from literature in the area of binary comparison and fingerprinting are outlined and applied to the problem of (version) identification of shared libraries and of libraries within statically linked binary executables. Six comparison techniques are chosen and implemented in an open-source tool which in turn makes use of the open-source radare2 framework for signature generation. The effectiveness of the techniques is empirically analyzed by comparing both artificial and real sample files against a reference dataset of multiple versions of dozens of libraries. The results show that out of these techniques, readable string--based techniques perform the best and that one of these techniques correctly identifies multiple libraries contained in a stripped statically linked executable file.
Analytical Modeling for Virtualized Network Functions
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) is considered one of the key technologies for the 5G mobile networks. In NFV, network functions are implemented in software components denominated Virtual Network Functions (VNFs) running on commodity hardware. In this paper, we propose an analytical model based on an open queuing network of G/G/m queues to model VNFs with single- or multi-tier designs, and chains of VNFs. Our model is flexible and generic enough to capture the behavior of such systems. We validate our model by simulation. Specifically, we validate it for an LTE virtualized Mobility Management Entity with a three-tiered architecture use case. We also compare our model with the estate of the art, in terms of computational complexity and estimation error. The results show that our model has a computational complexity similar to the method for analyzing Jackson's networks. Additionally, our model exhibits an estimation error, measured as the relative error for the estimation of the mean response time, approximately equal to 10%, whereas for the considered baseline systems it ranges roughly from 60% to 90%.
Multimodal Gaze Stabilization of a Humanoid Robot based on Reafferences
Venue: arXiv cs.RO 2017
Year: 2017

Gaze stabilization is fundamental for humanoid robots. By stabilizing vision, it enhances perception of the environment and keeps points of interest in the field of view. In this contribution, a multimodal gaze stabilization combining classic inverse kinematic control with vestibulo-ocular and optokinetic reflexes is introduced. Inspired by neuroscience, it implements a forward model that can modulate the reflexes based on the reafference principle. This principle filters self-generated movements out of the reflexive feedback loop. The versatility and effectiveness of this method are experimentally validated on the Armar-III humanoid robot. It is first demonstrated that each stabilization mechanism (inverse kinematics and reflexes) performs better than the others as a function of the type of perturbation to be stabilized. Furthermore, combining these three modalities by reafference provides a universal gaze stabilizer which can handle any kind of perturbation.
A tool for ECG signal analysis using standard and optimized Hermite transform
Venue: arXiv cs.CE 2017
Year: 2017

The development of a system that would ease the diagnosis of heart diseases would also fasten the work of the cardiologic department in hospitals and facilitate the monitoring of patients with portable devices. This paper presents a tool for ECG signal analysis which is designed in Matlab. The Hermite transform domain is exploited for the analysis. The proposed transform domain is very convenient for ECG signal analysis and classification. Parts of the ECG signals, i.e. QRS complexes, show shape similarity with the Hermite basis functions, which is one of the reasons for choosing this domain. Also, the information about the signal can be represented using a small set of coefficients in this domain, which makes data transmission and analysis faster. The signal concentration in the Hermite domain and consequently, the number of samples required for signal representation, can additionally be reduced by performing the parametization of the Hermite transform. For the comparison purpose, the Fourier transform domain is also implemented within the software, in order to compare the signal concentration in two transform domains.
Making 360$^{\circ}$ Video Watchable in 2D: Learning Videography for Click Free Viewing
Venue: arXiv cs.CV 2017
Year: 2017

360$^{\circ}$ video requires human viewers to actively control "where" to look while watching the video. Although it provides a more immersive experience of the visual content, it also introduces additional burden for viewers; awkward interfaces to navigate the video lead to suboptimal viewing experiences. Virtual cinematography is an appealing direction to remedy these problems, but conventional methods are limited to virtual environments or rely on hand-crafted heuristics. We propose a new algorithm for virtual cinematography that automatically controls a virtual camera within a 360$^{\circ}$ video. Compared to the state of the art, our algorithm allows more general camera control, avoids redundant outputs, and extracts its output videos substantially more efficiently. Experimental results on over 7 hours of real "in the wild" video show that our generalized camera control is crucial for viewing 360$^{\circ}$ video, while the proposed efficient algorithm is essential for making the generalized control computationally tractable.
Evolving Deep Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

The success of deep learning depends on finding an architecture to fit the task. As deep learning has scaled up to more challenging tasks, the architectures have become difficult to design by hand. This paper proposes an automated method, CoDeepNEAT, for optimizing deep learning architectures through evolution. By extending existing neuroevolution methods to topology, components, and hyperparameters, this method achieves results comparable to best human designs in standard benchmarks in object recognition and language modeling. It also supports building a real-world application of automated image captioning on a magazine website. Given the anticipated increases in available computing power, evolution of deep networks is promising approach to constructing deep learning applications in the future.
A Deep Cascade of Convolutional Neural Networks for MR Image Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

The acquisition of Magnetic Resonance Imaging (MRI) is inherently slow. Inspired by recent advances in deep learning, we propose a framework for reconstructing MR images from undersampled data using a deep cascade of convolutional neural networks to accelerate the data acquisition process. We show that for Cartesian undersampling of 2D cardiac MR images, the proposed method outperforms the state-of-the-art compressed sensing approaches, such as dictionary learning-based MRI (DLMRI) reconstruction, in terms of reconstruction error, perceptual quality and reconstruction speed for both 3-fold and 6-fold undersampling. Compared to DLMRI, the error produced by the method proposed is approximately twice as small, allowing to preserve anatomical structures more faithfully. Using our method, each image can be reconstructed in 23 ms, which is fast enough to enable real-time applications.
A resource-frugal probabilistic dictionary and applications in bioinformatics
Venue: arXiv cs.DS 2017
Year: 2017

Indexing massive data sets is extremely expensive for large scale problems. In many fields, huge amounts of data are currently generated, however extracting meaningful information from voluminous data sets, such as computing similarity between elements, is far from being trivial. It remains nonetheless a fundamental need. This work proposes a probabilistic data structure based on a minimal perfect hash function for indexing large sets of keys. Our structure out-compete the hash table for construction, query times and for memory usage, in the case of the indexation of a static set. To illustrate the impact of algorithms performances, we provide two applications based on similarity computation between collections of sequences, and for which this calculation is an expensive but required operation. In particular, we show a practical case in which other bioinformatics tools fail to scale up the tested data set or provide lower recall quality results.
Artificial Noise-Aided Biobjective Transmitter Optimization for Service Integration in Multi-User MIMO Gaussian Broadcast Channel
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers an artificial noise (AN)-aided transmit design for multi-user MIMO systems with integrated services. Specifically, two sorts of service messages are combined and served simultaneously: one multicast message intended for all receivers and one confidential message intended for only one receiver and required to be perfectly secure from other unauthorized receivers. Our interest lies in the joint design of input covariances of the multicast message, confidential message and artificial noise (AN), such that the achievable secrecy rate and multicast rate are simultaneously maximized. This problem is identified as a secrecy rate region maximization (SRRM) problem in the context of physical-layer service integration. Since this bi-objective optimization problem is inherently complex to solve, we put forward two different scalarization methods to convert it into a scalar optimization problem. First, we propose to prefix the multicast rate as a constant, and accordingly, the primal biobjective problem is converted into a secrecy rate maximization (SRM) problem with quality of multicast service (QoMS) constraint. By varying the constant, we can obtain different Pareto optimal points. The resulting SRM problem can be iteratively solved via a provably convergent difference-of-concave (DC) algorithm. In the second method, we aim to maximize the weighted sum of the secrecy rate and the multicast rate. Through varying the weighted vector, one can also obtain different Pareto optimal points. We show that this weighted sum rate maximization (WSRM) problem can be recast into a primal decomposable form, which is amenable to alternating optimization (AO). Then we compare these two scalarization methods in terms of their overall performance and computational complexity via theoretical analysis as well as numerical simulation, based on which new insights can be drawn.
Wireless Interference Identification with Convolutional Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

The steadily growing use of license-free frequency bands requires reliable coexistence management for deterministic medium utilization. For interference mitigation, proper wireless interference identification (WII) is essential. In this work we propose the first WII approach based upon deep convolutional neural networks (CNNs). The CNN naively learns its features through self-optimization during an extensive data-driven GPU-based training process. We propose a CNN example which is based upon sensing snapshots with a limited duration of 12.8 μs and an acquisition bandwidth of 10 MHz. The CNN differs between 15 classes. They represent packet transmissions of IEEE 802.11 b/g, IEEE 802.15.4 and IEEE 802.15.1 with overlapping frequency channels within the 2.4 GHz ISM band. We show that the CNN outperforms state-of-the-art WII approaches and has a classification accuracy greater than 95% for signal-to-noise ratio of at least -5 dB.
Evaluating Singleplayer and Multiplayer in Human Computation Games
Venue: arXiv cs.HC 2017
Year: 2017

Human computation games (HCGs) can provide novel solutions to intractable computational problems, help enable scientific breakthroughs, and provide datasets for artificial intelligence. However, our knowledge about how to design and deploy HCGs that appeal to players and solve problems effectively is incomplete. We present an investigatory HCG based on Super Mario Bros. We used this game in a human subjects study to investigate how different social conditions---singleplayer and multiplayer---and scoring mechanics---collaborative and competitive---affect players' subjective experiences, accuracy at the task, and the completion rate. In doing so, we demonstrate a novel design approach for HCGs, and discuss the benefits and tradeoffs of these mechanics in HCG design.
Depth Estimation using Modified Cost Function for Occlusion Handling
Venue: arXiv cs.MM 2017
Year: 2017

The paper presents a novel approach to occlusion handling problem in depth estimation using three views. A solution based on modification of similarity cost function is proposed. During the depth estimation via optimization algorithms like Graph Cut similarity metric is constantly updated so that only non-occluded fragments in side views are considered. At each iteration of the algorithm non-occluded fragments are detected based on side view virtual depth maps synthesized from the best currently estimated depth map of the center view. Then similarity metric is updated for correspondence search only in non-occluded regions of the side views. The experimental results, conducted on well-known 3D video test sequences, have proved that the depth maps estimated with the proposed approach provide about 1.25 dB virtual view quality improvement in comparison to the virtual view synthesized based on depth maps generated by the state-of-the-art MPEG Depth Estimation Reference Software.
On the Fine-grained Complexity of One-Dimensional Dynamic Programming
Venue: arXiv cs.CC 2017
Year: 2017

In this paper, we investigate the complexity of one-dimensional dynamic programming, or more specifically, of the Least-Weight Subsequence (LWS) problem: Given a sequence of $n$ data items together with weights for every pair of the items, the task is to determine a subsequence $S$ minimizing the total weight of the pairs adjacent in $S$. A large number of natural problems can be formulated as LWS problems, yielding obvious $O(n^2)$-time solutions. In many interesting instances, the $O(n^2)$-many weights can be succinctly represented. Yet except for near-linear time algorithms for some specific special cases, little is known about when an LWS instantiation admits a subquadratic-time algorithm and when it does not. In particular, no lower bounds for LWS instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the fine-grained complexity of succinct instantiations of the LWS problem. In particular, given an LWS instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS instantiation and the corresponding core problem) of problems: a low-rank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)-convolution. Using these equivalences and known SETH-hardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the (min,+)-convolution-hardness of the knapsack problem.
Outlier Cluster Formation in Spectral Clustering
Venue: arXiv cs.CV 2017
Year: 2017

Outlier detection and cluster number estimation is an important issue for clustering real data. This paper focuses on spectral clustering, a time-tested clustering method, and reveals its important properties related to outliers. The highlights of this paper are the following two mathematical observations: first, spectral clustering's intrinsic property of an outlier cluster formation, and second, the singularity of an outlier cluster with a valid cluster number. Based on these observations, we designed a function that evaluates clustering and outlier detection results. In experiments, we prepared two scenarios, face clustering in photo album and person re-identification in a camera network. We confirmed that the proposed method detects outliers and estimates the number of clusters properly in both problems. Our method outperforms state-of-the-art methods in both the 128-dimensional sparse space for face clustering and the 4,096-dimensional non-sparse space for person re-identification.