OpenRaiser/Intern-Atlas huggingface dataset:
Neural Headline Generation with Sentence-wise Optimization
Venue: arXiv cs.CL 2016
Year: 2016

Recently, neural models have been proposed for headline generation by learning to map documents to headlines with recurrent neural networks. Nevertheless, as traditional neural network utilizes maximum likelihood estimation for parameter optimization, it essentially constrains the expected training objective within word level rather than sentence level. Moreover, the performance of model prediction significantly relies on training data distribution. To overcome these drawbacks, we employ minimum risk training strategy in this paper, which directly optimizes model parameters in sentence level with respect to evaluation metrics and leads to significant improvements for headline generation. Experiment results show that our models outperforms state-of-the-art systems on both English and Chinese headline generation tasks.
Computational Efficiency Requires Simple Taxation
Venue: arXiv cs.GT 2016
Year: 2016

We characterize the communication complexity of truthful mechanisms. Our departure point is the well known taxation principle. The taxation principle asserts that every truthful mechanism can be interpreted as follows: every player is presented with a menu that consists of a price for each bundle (the prices depend only on the valuations of the other players). Each player is allocated a bundle that maximizes his profit according to this menu. We define the taxation complexity of a truthful mechanism to be the logarithm of the maximum number of menus that may be presented to a player. Our main finding is that in general the taxation complexity essentially equals the communication complexity. The proof consists of two main steps. First, we prove that for rich enough domains the taxation complexity is at most the communication complexity. We then show that the taxation complexity is much smaller than the communication complexity only in "pathological" cases and provide a formal description of these extreme cases. Next, we study mechanisms that access the valuations via value queries only. In this setting we establish that the menu complexity -- a notion that was already studied in several different contexts -- characterizes the number of value queries that the mechanism makes in exactly the same way that the taxation complexity characterizes the communication complexity. Our approach yields several applications, including strengthening the solution concept with low communication overhead, fast computation of prices, and hardness of approximation by computationally efficient truthful mechanisms.
Analysis of higher order time delay systems using Lambert W function
Venue: arXiv cs.SY 2016
Year: 2016

In this note, analysis of time delay systems using Lambert W function approach is reassessed. A common canonical form of time delay systems is defined. We extended the recent results of [6] for second order into nth order system. The eigenvalues of a time delay system are either real or complex conjugate pairs and therefore, the whole eigenspectrum can be associated with only two real branches of the Lambert W function. A new class of time delay systems is characterized to extend the applicability of the above said method. A state variable transformation is used to transform the proposed class of systems into the common canonical form. Moreover, this approach has been exploited to design a controller which places a subset of eigenvalues at desired locations. Stability is analyesed by the help of Nyquist plot. The approach is validated through an example.
Keyboard Based Control of Four Dimensional Rotations
Venue: arXiv cs.GR 2016
Year: 2016

Aiming at applications to the scientific visualization of three dimensional simulations with time evolution, a keyboard based control method to specify rotations in four dimensions is proposed. It is known that four dimensional rotations are generally so-called double rotations, and a double rotation is a combination of simultaneously applied two simple rotations. The proposed method can specify both the simple and double rotations by single key typings of the keyboard. The method is tested in visualizations of a regular pentachoron in four dimensional space by a hyperplane slicing.
Combinatorial Topic Models using Small-Variance Asymptotics
Venue: arXiv cs.LG 2016
Year: 2016

Topic models have emerged as fundamental tools in unsupervised machine learning. Most modern topic modeling algorithms take a probabilistic view and derive inference algorithms based on Latent Dirichlet Allocation (LDA) or its variants. In contrast, we study topic modeling as a combinatorial optimization problem, and propose a new objective function derived from LDA by passing to the small-variance limit. We minimize the derived objective by using ideas from combinatorial optimization, which results in a new, fast, and high-quality topic modeling algorithm. In particular, we show that our results are competitive with popular LDA-based topic modeling approaches, and also discuss the (dis)similarities between our approach and its probabilistic counterparts.
3-D Hand Pose Estimation from Kinect's Point Cloud Using Appearance Matching
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel appearance-based approach for pose estimation of a human hand using the point clouds provided by the low-cost Microsoft Kinect sensor. Both the free-hand case, in which the hand is isolated from the surrounding environment, and the hand-object case, in which the different types of interactions are classified, have been considered. The hand-object case is clearly the most challenging task having to deal with multiple tracks. The approach proposed here belongs to the class of partial pose estimation where the estimated pose in a frame is used for the initialization of the next one. The pose estimation is obtained by applying a modified version of the Iterative Closest Point (ICP) algorithm to synthetic models to obtain the rigid transformation that aligns each model with respect to the input data. The proposed framework uses a "pure" point cloud as provided by the Kinect sensor without any other information such as RGB values or normal vector components. For this reason, the proposed method can also be applied to data obtained from other types of depth sensor, or RGB-D camera.
Sufficient Conditions for Existence of $J_α(X + \sqrt[α]ηN)$
Venue: arXiv cs.IT 2016
Year: 2016

In his technical report~\cite[sec. 6]{barrontech}, Barron states that the de Bruijn's identity for Gaussian perturbations holds for any RV having a finite variance. In this report, we follow Barron's steps as we prove the existence of $J_α\left(X + \sqrt[α]ηN\right)$, $η> 0$ for any Radom Variable (RV) $X \in \mathcal{L}$ where \begin{equation*} \mathcal{L} = \left\{ \text{RVs} \,\,U: \int \ln\left(1 + |U|\right)\,dF_{U}(u) \text{ is finite } \right\}, \end{equation*} and where $N \sim \mathcal{S}(α;1)$ is independent of $X$, $0< α<2$.
On Fully Dynamic Graph Sparsifiers
Venue: arXiv cs.DS 2016
Year: 2016

We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a $ (1 \pm ε) $-spectral sparsifier with amortized update time $poly(\log{n}, ε^{-1})$. Second, we give a fully dynamic algorithm for maintaining a $ (1 \pm ε) $-cut sparsifier with \emph{worst-case} update time $poly(\log{n}, ε^{-1})$. Both sparsifiers have size $ n \cdot poly(\log{n}, ε^{-1})$. Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a $(1 + ε)$-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time $poly(\log{n}, ε^{-1})$.
Service Chain and Virtual Network Embeddings: Approximations using Randomized Rounding
Venue: arXiv cs.NI 2016
Year: 2016

The SDN and NFV paradigms enable novel network services which can be realized and embedded in a flexible and rapid manner. For example, SDN can be used to flexibly steer traffic from a source to a destination through a sequence of virtualized middleboxes, in order to realize so-called service chains. The service chain embedding problem consists of three tasks: admission control, finding suitable locations to allocate the virtualized middleboxes and computing corresponding routing paths. This paper considers the offline batch embedding of multiple service chains. Concretely, we consider the objectives of maximizing the profit by embedding an optimal subset of requests or minimizing the costs when all requests need to be embedded. Interestingly, while the service chain embedding problem has recently received much attention, so far, only non- polynomial time algorithms (based on integer programming) as well as heuristics (which do not provide any formal guarantees) are known. This paper presents the first polynomial time service chain approximation algorithms both for the case with admission and without admission control. Our algorithm is based on a novel extension of the classic linear programming and randomized rounding technique, which may be of independent interest. In particular, we show that our approach can also be extended to more complex service graphs, containing cycles or sub-chains, hence also providing new insights into the classic virtual network embedding problem.
Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word
Venue: arXiv cs.DM 2016
Year: 2016

The combinatorics of squares in a word depends on how the equivalence of halves of the square is defined. We consider Abelian squares, parameterized squares, and order-preserving squares. The word $uv$ is an Abelian (parameterized, order-preserving) square if $u$ and $v$ are equivalent in the Abelian (parameterized, order-preserving) sense. The maximum number of ordinary squares in a word is known to be asymptotically linear, but the exact bound is still investigated. We present several results on the maximum number of distinct squares for nonstandard subword equivalence relations. Let $\mathit{SQ}_{\mathrm{Abel}}(n,σ)$ and $\mathit{SQ}'_{\mathrm{Abel}}(n,σ)$ denote the maximum number of Abelian squares in a word of length $n$ over an alphabet of size $σ$, which are distinct as words and which are nonequivalent in the Abelian sense, respectively. For $σ\ge 2$ we prove that $\mathit{SQ}_{\mathrm{Abel}}(n,σ)=Θ(n^2)$, $\mathit{SQ}'_{\mathrm{Abel}}(n,σ)=Ω(n^{3/2})$ and $\mathit{SQ}'_{\mathrm{Abel}}(n,σ) = O(n^{11/6})$. We also give linear bounds for parameterized and order-preserving squares for alphabets of constant size: $\mathit{SQ}_{\mathrm{param}}(n,O(1))=Θ(n)$, $\mathit{SQ}_{\mathrm{op}}(n,O(1))=Θ(n)$. The upper bounds have quadratic dependence on the alphabet size for order-preserving squares and exponential dependence for parameterized squares. As a side result we construct infinite words over the smallest alphabet which avoid nontrivial order-preserving squares and nontrivial parameterized cubes (nontrivial parameterized squares cannot be avoided in an infinite word).
Probabilistic classifiers with low rank indefinite kernels
Venue: arXiv cs.LG 2016
Year: 2016

Indefinite similarity measures can be frequently found in bio-informatics by means of alignment scores, but are also common in other fields like shape measures in image retrieval. Lacking an underlying vector space, the data are given as pairwise similarities only. The few algorithms available for such data do not scale to larger datasets. Focusing on probabilistic batch classifiers, the Indefinite Kernel Fisher Discriminant (iKFD) and the Probabilistic Classification Vector Machine (PCVM) are both effective algorithms for this type of data but, with cubic complexity. Here we propose an extension of iKFD and PCVM such that linear runtime and memory complexity is achieved for low rank indefinite kernels. Employing the Nyström approximation for indefinite kernels, we also propose a new almost parameter free approach to identify the landmarks, restricted to a supervised learning problem. Evaluations at several larger similarity data from various domains show that the proposed methods provides similar generalization capabilities while being easier to parametrize and substantially faster for large scale data.
Online Open World Recognition
Venue: arXiv cs.CV 2016
Year: 2016

As we enter into the big data age and an avalanche of images have become readily available, recognition systems face the need to move from close, lab settings where the number of classes and training data are fixed, to dynamic scenarios where the number of categories to be recognized grows continuously over time, as well as new data providing useful information to update the system. Recent attempts, like the open world recognition framework, tried to inject dynamics into the system by detecting new unknown classes and adding them incrementally, while at the same time continuously updating the models for the known classes. incrementally adding new classes and detecting instances from unknown classes, while at the same time continuously updating the models for the known classes. In this paper we argue that to properly capture the intrinsic dynamic of open world recognition, it is necessary to add to these aspects (a) the incremental learning of the underlying metric, (b) the incremental estimate of confidence thresholds for the unknown classes, and (c) the use of local learning to precisely describe the space of classes. We extend three existing metric learning algorithms towards these goals by using online metric learning. Experimentally we validate our approach on two large-scale datasets in different learning scenarios. For all these scenarios our proposed methods outperform their non-online counterparts. We conclude that local and online learning is important to capture the full dynamics of open world recognition.
A modified block Lanczos algorithm with fewer vectors
Venue: arXiv cs.CR 2016
Year: 2016

The block Lanczos algorithm proposed by Peter Montgomery is an efficient means to tackle the sparse linear algebra problem which arises in the context of the number field sieve factoring algorithm and its predecessors. We present here a modified version of the algorithm, which incorporates several improvements: we discuss how to efficiently handle homogeneous systems and how to reduce the number of vectors stored in the course of the computation. We also provide heuristic justification for the success probability of our modified algorithm. While the overall complexity and expected number of steps of the block Lanczos is not changed by the modifications presented in this article, we expect these to be useful for implementations of the block Lanczos algorithm where the storage of auxiliary vectors sometimes has a non-negligible cost. 1 Linear systems for integer factoring For factoring a composite integer N, algorithms based on the technique of combination of congruences look for several pairs of integers (x, y) such that x 2 $\not\equiv$ y 2 mod N. This equality is hoped to be non trivial for at least one of the obtained pairs, letting gcd(x -- y, N) unveil a factor of the integer N. Several algorithms use this strategy: the CFRAC algorithm, the quadratic sieve and its variants, and the number field sieve. Pairs (x, y) as above are obtained by combining relations which have been collected as a step of these algorithms. Relations are written multiplicatively as a set of valuations. All the algorithms considered seek a multiplicative combination of these relations which can be rewritten as an equality of squares. This is achieved by solving a system of linear equations defined over F 2, where equations are parity constraints on
A system of serial computation for classified rules prediction in non-regular ontology trees
Venue: arXiv cs.AI 2016
Year: 2016

Objects or structures that are regular take uniform dimensions. Based on the concepts of regular models, our previous research work has developed a system of a regular ontology that models learning structures in a multiagent system for uniform pre-assessments in a learning environment. This regular ontology has led to the modelling of a classified rules learning algorithm that predicts the actual number of rules needed for inductive learning processes and decision making in a multiagent system. But not all processes or models are regular. Thus this paper presents a system of polynomial equation that can estimate and predict the required number of rules of a non-regular ontology model given some defined parameters.
Back to the Basics: Bayesian extensions of IRT outperform neural networks for proficiency estimation
Venue: arXiv cs.AI 2016
Year: 2016

Estimating student proficiency is an important task for computer based learning systems. We compare a family of IRT-based proficiency estimation methods to Deep Knowledge Tracing (DKT), a recently proposed recurrent neural network model with promising initial results. We evaluate how well each model predicts a student's future response given previous responses using two publicly available and one proprietary data set. We find that IRT-based methods consistently matched or outperformed DKT across all data sets at the finest level of content granularity that was tractable for them to be trained on. A hierarchical extension of IRT that captured item grouping structure performed best overall. When data sets included non-trivial autocorrelations in student response patterns, a temporal extension of IRT improved performance over standard IRT while the RNN-based method did not. We conclude that IRT-based models provide a simpler, better-performing alternative to existing RNN-based models of student interaction data while also affording more interpretability and guarantees due to their formulation as Bayesian probabilistic models.
A Security Evaluation Framework for U.K. E-Goverment Services Agile Software Development
Venue: arXiv cs.CR 2016
Year: 2016

This study examines the traditional approach to software development within the United Kingdom Government and the accreditation process. Initially we look at the Waterfall methodology that has been used for several years. We discuss the pros and cons of Waterfall before moving onto the Agile Scrum methodology. Agile has been adopted by the majority of Government digital departments including the Government Digital Services. Agile, despite its ability to achieve high rates of productivity organized in short, flexible, iterations, has faced security professionals disbelief when working within the U.K. Government. One of the major issues is that we develop in Agile but the accreditation process is conducted using Waterfall resulting in delays to go live dates. Taking a brief look into the accreditation process that is used within Government for I.T. systems and applications, we focus on giving the accreditor the assurance they need when developing new applications and systems. A framework has been produced by utilizing the Open Web Application Security Project (OWASP) Application Security Verification Standard (ASVS). This framework will allow security and Agile to work side by side and produce secure code.
Image segmentation of cross-country scenes captured in IR spectrum
Venue: arXiv cs.CV 2016
Year: 2016

Computer vision has become a major source of information for autonomous navigation of robots of various types, self-driving cars, military robots and mars/lunar rovers are some examples. Nevertheless, the majority of methods focus on analysing images captured in visible spectrum. In this manuscript we elaborate on the problem of segmenting cross-country scenes captured in IR spectrum. For this purpose we proposed employing salient features. Salient features are robust to variations in scale, brightness and view angle. We suggest the Speeded-Up Robust Features as a basis for our salient features for a number of reasons discussed in the paper. We also provide a comparison of two SURF implementations. The SURF features are extracted from images of different terrain types. For every feature we estimate a terrain class membership function. The membership values are obtained by means of either the multi-layer perceptron or nearest neighbours. The features' class membership values and their spatial positions are then applied to estimate class membership values for all pixels in the image. To decrease the effect of segmentation blinking that is caused by rapid switching between different terrain types and to speed up segmentation, we are tracking camera position and predict features' positions. The comparison of the multi-layer perception and the nearest neighbour classifiers is presented in the paper. The error rate of the terrain segmentation using the nearest neighbours obtained on the testing set is 16.6+-9.17%.
Performance Limits for Noisy Multi-Measurement Vector Problems
Venue: arXiv cs.IT 2016
Year: 2016

Compressed sensing (CS) demonstrates that sparse signals can be estimated from under-determined linear systems. Distributed CS (DCS) further reduces the number of measurements by considering joint sparsity within signal ensembles. DCS with jointly sparse signals has applications in multi-sensor acoustic sensing, magnetic resonance imaging with multiple coils, remote sensing, and array signal processing. Multi-measurement vector (MMV) problems consider the estimation of jointly sparse signals under the DCS framework. Two related MMV settings are studied. In the first setting, each signal vector is measured by a different independent and identically distributed (i.i.d.) measurement matrix, while in the second setting, all signal vectors are measured by the same i.i.d. matrix. Replica analysis is performed for these two MMV settings, and the minimum mean squared error (MMSE), which turns out to be identical for both settings, is obtained as a function of the noise variance and number of measurements. To showcase the application of MMV models, the MMSE's of complex CS problems with both real and complex measurement matrices are also analyzed. Multiple performance regions for MMV are identified where the MMSE behaves differently as a function of the noise variance and the number of measurements. Belief propagation (BP) is a CS signal estimation framework that often achieves the MMSE asymptotically. A phase transition for BP is identified. This phase transition, verified by numerical results, separates the regions where BP achieves the MMSE and where it is suboptimal. Numerical results also illustrate that more signal vectors in the jointly sparse signal ensemble lead to a better phase transition.
On the Composition of Scientific Abstracts
Venue: arXiv cs.IR 2016
Year: 2016

Scientific abstracts contain what is considered by the author(s) as information that best describe documents' content. They represent a compressed view of the informational content of a document and allow readers to evaluate the relevance of the document to a particular information need. However, little is known on their composition. This paper contributes to the understanding of the structure of abstracts, by comparing similarity between scientific abstracts and the text content of research articles. More specifically, using sentence-based similarity metrics, we quantify the phenomenon of text re-use in abstracts and examine the positions of the sentences that are similar to sentences in abstracts in the IMRaD structure (Introduction, Methods, Results and Discussion), using a corpus of over 85,000 research articles published in the seven PLOS journals. We provide evidence that 84% of abstract have at least one sentence in common with the body of the article. Our results also show that the sections of the paper from which abstract sentence are taken are invariant across the PLOS journals, with sentences mainly coming from the beginning of the introduction and the end of the conclusion.