OpenRaiser/Intern-Atlas huggingface dataset:
Automated Prototype Generation from Formal Requirements Model
Venue: arXiv cs.SE 2018
Year: 2018

Prototyping is an effective and efficient way of requirement validation to avoid introducing errors in the early stage of software development. However, manually developing a prototype of a software system requires additional efforts, which would increase the overall cost of software development. In this paper, we present an approach with a developed tool to automatic generation of prototypes from formal requirements models. A requirements model consists of a use case diagram, a conceptual class diagram, use case definitions specified by system sequence diagrams and the contracts of their system operations. We propose a method to decompose a contract into executable parts and non-executable parts. A set of transformation rules is given to decompose the executable part into pre-implemented primitive operations. A non-executable part is usually realized by significant algorithms such as sorting a list, finding the shortest path or domain-specific computation. It can be implemented manually or by using existing code. A CASE tool is developed that provides an interface for developers to develop a program for each non-executable part of a contract, and automatically transforms the executables into sequences of pre-implemented primitive operations. We have conducted four cases studies with over 50 use cases. The experimental result shows that the 93.65% of requirement specifications are executable, and only 6.35% are non-executable such as sorting and event-call, which can be implemented by developers manually or invoking the APIs of advanced algorithms in Java library. The one second generated the prototype of a case study requires approximate nine hours manual implementation by a skilled programmer. Overall, the result is satisfiable, and the proposed approach with the developed CASE tool can be applied to the software industry for requirements engineering.
A Formula That Generates Hash Collisions
Venue: arXiv cs.CR 2018
Year: 2018

We present an explicit formula that produces hash collisions for the Merkle-Damgård construction. The formula works for arbitrary choice of message block and irrespective of the standardized constants used in hash functions, although some padding schemes may cause the formula to fail. This formula bears no obvious practical implications because at least one of any pair of colliding messages will have length double exponential in the security parameter. However, due to ambiguity in existing definitions of collision resistance, this formula arguably breaks the collision resistance of some hash functions.
Multilevel Monte Carlo for uncertainty quantification in structural engineering
Venue: arXiv cs.CE 2018
Year: 2018

Practical structural engineering problems often exhibit a significant degree of uncertainty in the material properties being used, the dimensions of the modeled structures, etc. In this paper, we consider a cantilever beam and a beam clamped at both ends, both subjected to a static and a dynamic load. The material uncertainty resides in the Young's modulus, which is modeled by means of one random variable, sampled from a univariate Gamma distribution, or with multiple random variables, sampled from a Gamma random field. Three different responses are considered: the static elastic, the dynamic elastic and the static elastoplastic response. In the first two cases, we simulate the spatial displacement of a concrete beam and its frequency response in the elastic domain. The third case simulates the spatial displacement of a steel beam in the elastoplastic domain. In order to compute the statistical quantities of the static deflection and frequency response function, Multilevel Monte Carlo (MLMC) is combined with a Finite Element solver. In this paper, the computational costs and run times of the MLMC method are compared with those of the classical Monte Carlo method, demonstrating a significant speedup of up to several orders of magnitude for the studied cases.
PythonRobotics: a Python code collection of robotics algorithms
Venue: arXiv cs.RO 2018
Year: 2018

This paper describes an Open Source Software (OSS) project: PythonRobotics. This is a collection of robotics algorithms implemented in the Python programming language. The focus of the project is on autonomous navigation, and the goal is for beginners in robotics to understand the basic ideas behind each algorithm. In this project, the algorithms which are practical and widely used in both academia and industry are selected. Each sample code is written in Python3 and only depends on some standard modules for readability and ease of use. It includes intuitive animations to understand the behavior of the simulation.
Bayesian Classifier for Route Prediction with Markov Chains
Venue: arXiv cs.LG 2018
Year: 2018

We present here a general framework and a specific algorithm for predicting the destination, route, or more generally a pattern, of an ongoing journey, building on the recent work of [Y. Lassoued, J. Monteil, Y. Gu, G. Russo, R. Shorten, and M. Mevissen, "Hidden Markov model for route and destination prediction," in IEEE International Conference on Intelligent Transportation Systems, 2017]. In the presented framework, known journey patterns are modelled as stochastic processes, emitting the road segments visited during the journey, and the ongoing journey is predicted by updating the posterior probability of each journey pattern given the road segments visited so far. In this contribution, we use Markov chains as models for the journey patterns, and consider the prediction as final, once one of the posterior probabilities crosses a predefined threshold. Despite the simplicity of both, examples run on a synthetic dataset demonstrate high accuracy of the made predictions.
Victory Probability in the Fire Emblem Arena
Venue: arXiv cs.AI 2018
Year: 2018

We demonstrate how to efficiently compute the probability of victory in Fire Emblem arena battles. The probability can be expressed in terms of a multivariate recurrence relation which lends itself to a straightforward dynamic programming solution. Some implementation issues are addressed, and a full implementation is provided in code.
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
Venue: arXiv cs.DS 2018
Year: 2018

Let $\mathbb{F}[X]$ be the polynomial ring over the variables $X=\{x_1,x_2, \ldots, x_n\}$. An ideal $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$ generated by univariate polynomials $\{p_i(x_i)\}_{i=1}^n$ is a \emph{univariate ideal}. We study the ideal membership problem for the univariate ideals and show the following results. \item Let $f(X)\in\mathbb{F}[\ell_1, \ldots, \ell_r]$ be a (low rank) polynomial given by an arithmetic circuit where $\ell_i : 1\leq i\leq r$ are linear forms, and $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$ be a univariate ideal. Given $\vecα\in {\mathbb{F}}^n$, the (unique) remainder $f(X) \pmod I$ can be evaluated at $\vecα$ in deterministic time $d^{O(r)}\cdot poly(n)$, where $d=\max\{°(f),°(p_1)\ldots,°(p_n)\}$. This yields an $n^{O(r)}$ algorithm for minimum vertex cover in graphs with rank-$r$ adjacency matrices. It also yields an $n^{O(r)}$ algorithm for evaluating the permanent of a $n\times n$ matrix of rank $r$, over any field $\mathbb{F}$. Over $\mathbb{Q}$, an algorithm of similar run time for low rank permanent is due to Barvinok[Bar96] via a different technique. \item Let $f(X)\in\mathbb{F}[X]$ be given by an arithmetic circuit of degree $k$ ($k$ treated as fixed parameter) and $I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$. We show in the special case when $I=\langle x_1^{e_1}, \ldots, x_n^{e_n}\rangle$, we obtain a randomized $O^*(4.08^k)$ algorithm that uses $poly(n,k)$ space. \item Given $f(X)\in\mathbb{F}[X]$ by an arithmetic circuit and $I=\langle p_1(x_1), \ldots, p_k(x_k) \rangle$, membership testing is $W[1]$-hard, parameterized by $k$. The problem is $MINI[1]$-hard in the special case when $I=\langle x_1^{e_1}, \ldots, x_k^{e_k}\rangle$.
Seeing Colors: Learning Semantic Text Encoding for Classification
Venue: arXiv cs.CV 2018
Year: 2018

The question we answer with this work is: can we convert a text document into an image to exploit best image classification models to classify documents? To answer this question we present a novel text classification method which converts a text document into an encoded image, using word embedding and capabilities of Convolutional Neural Networks (CNNs), successfully employed in image classification. We evaluate our approach by obtaining promising results on some well-known benchmark datasets for text classification. This work allows the application of many of the advanced CNN architectures developed for Computer Vision to Natural Language Processing. We test the proposed approach on a multi-modal dataset, proving that it is possible to use a single deep model to represent text and image in the same feature space.
Model-Free Data-Driven Inelasticity
Venue: arXiv cs.CE 2018
Year: 2018

We extend the Data-Driven formulation of problems in elasticity of Kirchdoerfer and Ortiz (2016) to inelasticity. This extension differs fundamentally from Data-Driven problems in elasticity in that the material data set evolves in time as a consequence of the history dependence of the material. We investigate three representational paradigms for the evolving material data sets: i) materials with memory, i.e., conditioning the material data set to the past history of deformation; ii) differential materials, i.e., conditioning the material data set to short histories of stress and strain; and iii) history variables, i.e., conditioning the material data set to ad hoc variables encoding partial information about the history of stress and strain. We also consider combinations of the three paradigms thereof and investigate their ability to represent the evolving data sets of different classes of inelastic materials, including viscoelasticity, viscoplasticity and plasticity. We present selected numerical examples that demonstrate the range and scope of Data-Driven inelasticity and the numerical performance of implementations thereof.
When to Finish? Optimal Beam Search for Neural Text Generation (modulo beam size)
Venue: arXiv cs.CL 2018
Year: 2018

In neural text generation such as neural machine translation, summarization, and image captioning, beam search is widely used to improve the output text quality. However, in the neural generation setting, hypotheses can finish in different steps, which makes it difficult to decide when to end beam search to ensure optimality. We propose a provably optimal beam search algorithm that will always return the optimal-score complete hypothesis (modulo beam size), and finish as soon as the optimality is established (finishing no later than the baseline). To counter neural generation's tendency for shorter hypotheses, we also introduce a bounded length reward mechanism which allows a modified version of our beam search algorithm to remain optimal. Experiments on neural machine translation demonstrate that our principled beam search algorithm leads to improvement in BLEU score over previously proposed alternatives.
Multi-UAV Continuum Deformation Flight Optimization in Cluttered Urban Environments
Venue: arXiv cs.SY 2018
Year: 2018

This paper studies collective motion optimization of a fleet of UAVs flying over a populated and geometrically constrained area. The paper treats UAVs as particles of a deformable body, thus, UAV coordination is defined by a homeomorphic continuum deformation function. Under continuum deformation, the distance between individual UAVs can significantly change while assuring the UAVs dont collide, enabling a swarm to travel through the potentially cluttered environment. To ensure inter-agent and obstacle collision avoidance, the paper formulates safety requirements as inequality constraints of the coordination optimization problem. The main objective of the paper is then to optimize continuum deformation of the UAV team satisfying all continuum deformation inequality constraints. Given initial and target configurations, the cost is defined as a weighted sum of the travel distance and distributed cost proportional to the likelihood of the human presence
On Triangluar Separation of Bichromatic Point Sets in Polygonal Environment
Venue: arXiv cs.CG 2018
Year: 2018

Let $\mathcal P$ be a simple polygonal environment with $k$ vertices in the plane. Assume that a set $B$ of $b$ blue points and a set $R$ of $r$ red points are distributed in $\mathcal P$. We study the problem of computing triangles that separate the sets $B$ and $R$, and fall in $\mathcal P$. We call these triangles \emph{inscribed triangular separators}. We propose an output-sensitive algorithm to solve this problem in $O(r \cdot (r+c_B+k)+h_\triangle)$ time, where $c_B$ is the size of convex hull of $B$, and $h_\triangle$ is the number of inscribed triangular separators. We also study the case where there does not exist any inscribed triangular separators. This may happen due to the tight distribution of red points around convex hull of $B$ while no red points are inside this hull. In this case we focus to compute a triangle that separates most of the blue points from the red points. We refer to these triangles as \emph{maximum triangular separators}. Assuming $n=r+b$, we design a constant-factor approximation algorithm to compute such a separator in $O(n^{4/3} \log^3 n)$ time. "Eligible for best student paper"
Attack Tolerance of Link Prediction Algorithms: How to Hide Your Relations in a Social Network
Venue: arXiv cs.SI 2018
Year: 2018

Link prediction is one of the fundamental research problems in network analysis. Intuitively, it involves identifying the edges that are most likely to be added to a given network, or the edges that appear to be missing from the network when in fact they are present. Various algorithms have been proposed to solve this problem over the past decades. For all their benefits, such algorithms raise serious privacy concerns, as they could be used to expose a connection between two individuals who wish to keep their relationship private. With this in mind, we investigate the ability of such individuals to evade link prediction algorithms. More precisely, we study their ability to strategically alter their connections so as to increase the probability that some of their connections remain unidentified by link prediction algorithms. We formalize this question as an optimization problem, and prove that finding an optimal solution is NP-complete. Despite this hardness, we show that the situation is not bleak in practice. In particular, we propose two heuristics that can easily be applied by members of the general public on existing social media. We demonstrate the effectiveness of those heuristics on a wide variety of networks and against a plethora of link prediction algorithms.
Implications of Ocular Pathologies for Iris Recognition Reliability
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an analysis of how iris recognition is influenced by eye disease and an appropriate dataset comprising 2996 images of irises taken from 230 distinct eyes (including 184 affected by more than 20 different eye conditions). The images were collected in near infrared and visible light during routine ophthalmological examination. The experimental study carried out utilizing four independent iris recognition algorithms (MIRLIN, VeriEye, OSIRIS and IriCore) renders four valuable results. First, the enrollment process is highly sensitive to those eye conditions that obstruct the iris or cause geometrical distortions. Second, even those conditions that do not produce visible changes to the structure of the iris may increase the dissimilarity between samples of the same eyes. Third, eye conditions affecting the geometry or the tissue structure of the iris or otherwise producing obstructions significantly decrease same-eye similarity and have a lower, yet still statistically significant, influence on impostor comparison scores. Fourth, for unhealthy eyes, the most prominent effect of disease on iris recognition is to cause segmentation errors. To our knowledge this paper describes the largest database of iris images for disease-affected eyes made publicly available to researchers and offers the most comprehensive study of what we can expect when iris recognition is employed for diseased eyes.
Assessment of iris recognition reliability for eyes affected by ocular pathologies
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an analysis of how the iris recognition is impacted by eye diseases and an appropriate dataset comprising 2996 iris images of 230 distinct eyes (including 184 illness-affected eyes representing more than 20 different eye conditions). The images were collected in near infrared and visible light during a routine ophthalmological practice. The experimental study shows four valuable results. First, the enrollment process is highly sensitive to those eye conditions that make the iris obstructed or introduce geometrical distortions. Second, even those conditions that do not produce visible changes to the iris structure may increase the dissimilarity among samples of the same eyes. Third, eye conditions affecting iris geometry, its tissue structure or producing obstructions significantly decrease the iris recognition reliability. Fourth, for eyes afflicted by a disease, the most prominent effect of the disease on iris recognition is to cause segmentation errors. To our knowledge this is the first database of iris images for disease-affected eyes made publicly available to researchers, and the most comprehensive study of what we can expect when the iris recognition is deployed for non-healthy eyes.
Cataract influence on iris recognition performance
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents the experimental study revealing weaker performance of the automatic iris recognition methods for cataract-affected eyes when compared to healthy eyes. There is little research on the topic, mostly incorporating scarce databases that are often deficient in images representing more than one illness. We built our own database, acquiring 1288 eye images of 37 patients of the Medical University of Warsaw. Those images represent several common ocular diseases, such as cataract, along with less ordinary conditions, such as iris pattern alterations derived from illness or eye trauma. Images were captured in near-infrared light (used in biometrics) and for selected cases also in visible light (used in ophthalmological diagnosis). Since cataract is a disorder that is most populated by samples in the database, in this paper we focus solely on this illness. To assess the extent of the performance deterioration we use three iris recognition methodologies (commercial and academic solutions) to calculate genuine match scores for healthy eyes and those influenced by cataract. Results show a significant degradation in iris recognition reliability manifesting by worsening the genuine scores in all three matchers used in this study (12% of genuine score increase for an academic matcher, up to 175% of genuine score increase obtained for an example commercial matcher). This increase in genuine scores affected the final false non-match rate in two matchers. To our best knowledge this is the only study of such kind that employs more than one iris matcher, and analyzes the iris image segmentation as a potential source of decreased reliability.
Iris and periocular recognition in arabian race horses using deep convolutional neural networks
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a study devoted to recognizing horses by means of their iris and periocular features using deep convolutional neural networks (DCNNs). Identification of race horses is crucial for animal identity confirmation prior to racing. As this is usually done shortly before a race, fast and reliable methods that are friendly and inflict no harm upon animals are important. Iris recognition has been shown to work with horse irides, provided that algorithms deployed for such task are fine-tuned for horse irides and input data is of very high quality. In our work, we examine a possibility of utilizing deep convolutional neural networks for a fusion of both iris and periocular region features. With such methodology, ocular biometrics in horses could perform well without employing complicated algorithms that require a lot of fine-tuning and prior knowledge of the input image, while at the same time being rotation, translation, and to some extent also image quality invariant. We were able to achieve promising results, with EER=9.5% using two network architectures with score-level fusion.
Evaluation of Neural Networks for Image Recognition Applications: Designing a 0-1 MILP Model of a CNN to create adversarials
Venue: arXiv cs.CV 2018
Year: 2018

Image Recognition is a central task in computer vision with applications ranging across search, robotics, self-driving cars and many others. There are three purposes of this document: 1. We follow up on (Fischetti & Jo, December, 2017) and show how standard convolutional neural network can be optimized to a more sophisticated capsule architecture. 2. We introduce a MILP model based on CNN to create adversarials. 3. We compare and evaluate each network for image recognition tasks.
Evaluation of the performance challenges in automatic traffic report generation with huge data volumes
Venue: arXiv cs.NI 2018
Year: 2018

In this paper we analyze the performance issues involved in the generation of auto- mated traffic reports for large IT infrastructures. Such reports allows the IT manager to proactively detect possible abnormal situations and roll out the corresponding cor- rective actions. With the ever-increasing bandwidth of current networks, the design of automated traffic report generation systems is very challenging. In a first step, the huge volumes of collected traffic are transformed into enriched flow records obtained from diverse collectors and dissectors. Then, such flow records, along with time series obtained from the raw traffic, are further processed to produce a usable report. As will be shown, the data volume in flow records is very large as well and requires careful selection of the Key Performance Indicators (KPIs) to be included in the report. In this regard, we discuss the use of high-level languages versus low- level approaches, in terms of speed and versatility. Furthermore, our design approach is targeted for rapid development in commodity hardware, which is essential to cost-effectively tackle demanding traffic analysis scenarios.