OpenRaiser/Intern-Atlas huggingface dataset:
Decoupled Novel Object Captioner
Venue: arXiv cs.CV 2018
Year: 2018

Image captioning is a challenging task where the machine automatically describes an image by sentences or phrases. It often requires a large number of paired image-sentence annotations for training. However, a pre-trained captioning model can hardly be applied to a new domain in which some novel object categories exist, i.e., the objects and their description words are unseen during model training. To correctly caption the novel object, it requires professional human workers to annotate the images by sentences with the novel words. It is labor expensive and thus limits its usage in real-world applications. In this paper, we introduce the zero-shot novel object captioning task where the machine generates descriptions without extra sentences about the novel object. To tackle the challenging problem, we propose a Decoupled Novel Object Captioner (DNOC) framework that can fully decouple the language sequence model from the object descriptions. DNOC has two components. 1) A Sequence Model with the Placeholder (SM-P) generates a sentence containing placeholders. The placeholder represents an unseen novel object. Thus, the sequence model can be decoupled from the novel object descriptions. 2) A key-value object memory built upon the freely available detection model, contains the visual information and the corresponding word for each object. The SM-P will generate a query to retrieve the words from the object memory. The placeholder will then be filled with the correct word, resulting in a caption with novel object descriptions. The experimental results on the held-out MSCOCO dataset demonstrate the ability of DNOC in describing novel concepts in the zero-shot novel object captioning task.
Unsupervised Segmentation of 3D Medical Images Based on Clustering and Deep Representation Learning
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a novel unsupervised segmentation method for 3D medical images. Convolutional neural networks (CNNs) have brought significant advances in image segmentation. However, most of the recent methods rely on supervised learning, which requires large amounts of manually annotated data. Thus, it is challenging for these methods to cope with the growing amount of medical images. This paper proposes a unified approach to unsupervised deep representation learning and clustering for segmentation. Our proposed method consists of two phases. In the first phase, we learn deep feature representations of training patches from a target image using joint unsupervised learning (JULE) that alternately clusters representations generated by a CNN and updates the CNN parameters using cluster labels as supervisory signals. We extend JULE to 3D medical images by utilizing 3D convolutions throughout the CNN architecture. In the second phase, we apply k-means to the deep representations from the trained CNN and then project cluster labels to the target image in order to obtain the fully segmented image. We evaluated our methods on three images of lung cancer specimens scanned with micro-computed tomography (micro-CT). The automatic segmentation of pathological regions in micro-CT could further contribute to the pathological examination process. Hence, we aim to automatically divide each image into the regions of invasive carcinoma, noninvasive carcinoma, and normal tissue. Our experiments show the potential abilities of unsupervised deep representation learning for medical image segmentation.
E-commerce Anomaly Detection: A Bayesian Semi-Supervised Tensor Decomposition Approach using Natural Gradients
Venue: arXiv cs.LG 2018
Year: 2018

Anomaly Detection has several important applications. In this paper, our focus is on detecting anomalies in seller-reviewer data using tensor decomposition. While tensor-decomposition is mostly unsupervised, we formulate Bayesian semi-supervised tensor decomposition to take advantage of sparse labeled data. In addition, we use Polya-Gamma data augmentation for the semi-supervised Bayesian tensor decomposition. Finally, we show that the Pólya-Gamma formulation simplifies calculation of the Fisher information matrix for partial natural gradient learning. Our experimental results show that our semi-supervised approach outperforms state of the art unsupervised baselines. And that the partial natural gradient learning outperforms stochastic gradient learning and Online-EM with sufficient statistics.
Combinatorics of explicit substitutions
Venue: arXiv cs.LO 2018
Year: 2018

$λ\upsilon$ is an extension of the $λ$-calculus which internalises the calculus of substitutions. In the current paper, we investigate the combinatorial properties of $λ\upsilon$ focusing on the quantitative aspects of substitution resolution. We exhibit an unexpected correspondence between the counting sequence for $λ\upsilon$-terms and famous Catalan numbers. As a by-product, we establish effective sampling schemes for random $λ\upsilon$-terms. We show that typical $λ\upsilon$-terms represent, in a strong sense, non-strict computations in the classic $λ$-calculus. Moreover, typically almost all substitutions are in fact suspended, i.e. unevaluated, under closures. Consequently, we argue that $λ\upsilon$ is an intrinsically non-strict calculus of explicit substitutions. Finally, we investigate the distribution of various redexes governing the substitution resolution in $λ\upsilon$ and investigate the quantitative contribution of various substitution primitives.
Mobile Device Synchronisation with Central Database based on Data Relevance
Venue: arXiv cs.DC 2018
Year: 2018

Distributed applications are broadly used due the existence of mobile devices as are mobile phones, tablets and chrome books. They are often based on an architecture client-server. A server part contains a central storage where all application data are stored. A specific user accesses data using a client part of an application. The client part of the application can store data in its local storage to enable an offline mode. In the past, we were developing such a client-server software system and we realized that it doesn't exists a general way how to define, search and provide into a client part only those data that are important or relevant to a particular user. The aim of this article is a definition of the problem and a creation of its general solution, not how to achieve the most effective and complete data synchronization. Complete synchronization of data that has been already theoretically and practically solved on a general level and it is impractical for our case
Hybrid-IoT: Hybrid Blockchain Architecture for Internet of Things - PoW Sub-blockchains
Venue: arXiv cs.DC 2018
Year: 2018

From its early days the Internet of Things (IoT) has evolved into a decentralized system of cooperating smart objects with the requirement, among others, of achieving distributed consensus. Yet, current IoT platform solutions are centralized cloud based computing infrastructures, manifesting a number of significant disadvantages, such as, among others, high cloud server maintenance costs, weakness for supporting time-critical IoT applications, security and trust issues. Enabling blockchain technology into IoT can help to achieve a proper distributed consensus based IoT system that overcomes those disadvantages. While this is an ideal match, it is still a challenging endeavor. In this paper we take a first step towards that goal by designing Hybrid-IoT, a hybrid blockchain architecture for IoT. In Hybrid-IoT, subgroups of IoT devices form PoW blockchains, referred to as PoW sub-blockchains. Then, the connection among the PoW sub-blockchains employs a BFT inter-connector framework, such as Polkadot or Cosmos. In this paper we focus on the PoW sub-blockchains formation, guided by a set of guidelines based on a set of dimensions, metrics and bounds. In order to prove the validity of the approach we carry a performance and security evaluation.
Fusing Saliency Maps with Region Proposals for Unsupervised Object Localization
Venue: arXiv cs.CV 2018
Year: 2018

In this paper we address the problem of unsupervised localization of objects in single images. Compared to previous state-of-the-art method our method is fully unsupervised in the sense that there is no prior instance level or category level information about the image. Furthermore, we treat each image individually and do not rely on any neighboring image similarity. We employ deep-learning based generation of saliency maps and region proposals to tackle this problem. First salient regions in the image are determined using an encoder/decoder architecture. The resulting saliency map is matched with region proposals from a class agnostic region proposal network to roughly localize the candidate object regions. These regions are further refined based on the overlap and similarity ratios. Our experimental evaluations on a benchmark dataset show that the method gets close to current state-of-the-art methods in terms of localization accuracy even though these make use of multiple frames. Furthermore, we created a more challenging and realistic dataset with multiple object categories and varying viewpoint and illumination conditions for evaluating the method's performance in real world scenarios.
Von Neumann regularity, split epicness and elementary cellular automata
Venue: arXiv cs.FL 2018
Year: 2018

We show that a cellular automaton on a mixing subshift of finite type is a Von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that Von Neumann regularity is decidable condition, and we decide it for all elementary CA.
A Management Framework for Secure Multiparty Computation in Dynamic Environments
Venue: arXiv cs.CR 2018
Year: 2018

Secure multiparty computation (SMC) is a promising technology for privacy-preserving collaborative computation. In the last years several feasibility studies have shown its practical applicability in different fields. However, it is recognized that administration and management overhead of SMC solutions are still a problem. A vital next step is the incorporation of SMC in the emerging fields of the Internet of Things and (smart) dynamic environments. In these settings, the properties of these contexts make utilization of SMC even more challenging since some of its vital premises regarding environmental stability and preliminary configuration are not initially fulfilled. We bridge this gap by providing FlexSMC, a management and orchestration framework for SMC which supports the discovery of nodes, supports a trust establishment between them and realizes robustness of SMC session by handling nodes failures and communication interruptions. The practical evaluation of FlexSMC shows that it enables the application of SMC in dynamic environments with reasonable performance penalties and computation durations allowing soft real-time and interactive use cases.
The Evolution of User-Selected Passwords: A Quantitative Analysis of Publicly Available Datasets
Venue: arXiv cs.CR 2018
Year: 2018

The aim of this work is to study the evolution of password selection among users. We investigate whether users follow best practices when selecting passwords and identify areas in need of improvement. Four distinct publicly-available password datasets (obtained from security breaches, compiled by security experts, and designated as containing bad passwords) are employed. As these datasets were released at different times, the distributions characterizing these datasets suggest a chronological evolution of password selection. A similarity metric, Levenshtein distance, is used to compare passwords in each dataset against the designated benchmark of bad passwords. The resulting distributions of normalized similarity scores are then compared to each other. The comparison reveals an overall increase in the mean of the similarity distributions corresponding to more recent datasets, implying a shift away from the use of bad passwords. This conclusion is corroborated by the passwords' clustering behavior. An encoding capturing best practices maps passwords to a high dimensional space over which a $k$-means clustering (with silhouette coefficient) analysis is performed. Cluster comparison and character frequency analysis indicates an improvement in password selection over time with respect to certain features (length, mixing character types), yet certain discouraged practices (name inclusion, selection bias) still persist.
A Comparative Evaluation of Log-Based Process Performance Analysis Techniques
Venue: arXiv cs.PF 2018
Year: 2018

Process mining has gained traction over the past decade and an impressive body of research has resulted in the introduction of a variety of process mining approaches measuring process performance. Having this set of techniques available, organizations might find it difficult to identify which approach is best suited considering context, performance indicator, and data availability. In light of this challenge, this paper aims at introducing a framework for categorizing and selecting performance analysis approaches based on existing research. We start from a systematic literature review for identifying the existing works discussing how to measure process performance based on information retrieved from event logs. Then, the proposed framework is built starting from the information retrieved from these studies taking into consideration different aspects of performance analysis.
Sentiment Transfer using Seq2Seq Adversarial Autoencoders
Venue: arXiv cs.CL 2018
Year: 2018

Expressing in language is subjective. Everyone has a different style of reading and writing, apparently it all boil downs to the way their mind understands things (in a specific format). Language style transfer is a way to preserve the meaning of a text and change the way it is expressed. Progress in language style transfer is lagged behind other domains, such as computer vision, mainly because of the lack of parallel data, use cases, and reliable evaluation metrics. In response to the challenge of lacking parallel data, we explore learning style transfer from non-parallel data. We propose a model combining seq2seq, autoencoders, and adversarial loss to achieve this goal. The key idea behind the proposed models is to learn separate content representations and style representations using adversarial networks. Considering the problem of evaluating style transfer tasks, we frame the problem as sentiment transfer and evaluation using a sentiment classifier to calculate how many sentiments was the model able to transfer. We report our results on several kinds of models.
The Generalized Matrix Chain Algorithm
Venue: arXiv cs.MS 2018
Year: 2018

In this paper, we present a generalized version of the matrix chain algorithm to generate efficient code for linear algebra problems, a task for which human experts often invest days or even weeks of works. The standard matrix chain problem consists in finding the parenthesization of a matrix product $M := A_1 A_2 \cdots A_n$ that minimizes the number of scalar operations. In practical applications, however, one frequently encounters more complicated expressions, involving transposition, inversion, and matrix properties. Indeed, the computation of such expressions relies on a set of computational kernels that offer functionality well beyond the simple matrix product. The challenge then shifts from finding an optimal parenthesization to finding an optimal mapping of the input expression to the available kernels. Furthermore, it is often the case that a solution based on the minimization of scalar operations does not result in the optimal solution in terms of execution time. In our experiments, the generated code outperforms other libraries and languages on average by a factor of about 9. The motivation for this work comes from the fact that---despite great advances in the development of compilers---the task of mapping linear algebra problems to optimized kernels is still to be done manually. In order to relieve the user from this complex task, new techniques for the compilation of linear algebra expressions have to be developed.
Rapid mixing of Glauber dynamics for colorings below Vigoda's $11/6$ threshold
Venue: arXiv cs.DM 2018
Year: 2018

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $Δ$ is rapidly mixing for $k \geq Δ+2$. In FOCS 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper $k$-colorings for $k > \frac{11}{6}Δ$, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the $\frac{11}{6}Δ$ barrier for general graphs by showing rapid mixing for $k > (\frac{11}{6} - η)Δ$ for some positive constant $η$. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda's 2007 survey paper on Glauber dynamics for colorings.
Predicting Twitter User Socioeconomic Attributes with Network and Language Information
Venue: arXiv cs.CL 2018
Year: 2018

Inferring socioeconomic attributes of social media users such as occupation and income is an important problem in computational social science. Automated inference of such characteristics has applications in personalised recommender systems, targeted computational advertising and online political campaigning. While previous work has shown that language features can reliably predict socioeconomic attributes on Twitter, employing information coming from users' social networks has not yet been explored for such complex user characteristics. In this paper, we describe a method for predicting the occupational class and the income of Twitter users given information extracted from their extended networks by learning a low-dimensional vector representation of users, i.e. graph embeddings. We use this representation to train predictive models for occupational class and income. Results on two publicly available datasets show that our method consistently outperforms the state-of-the-art methods in both tasks. We also obtain further significant improvements when we combine graph embeddings with textual features, demonstrating that social network and language information are complementary.
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
Venue: arXiv cs.DS 2018
Year: 2018

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching". Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within a factor of $7$. We further extend this result to an $O(n^{1.781})$ quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to \textit{metric estimation} and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of $3$, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.
Evaluation of Kinematic Precise Point Positioning Convergence with an Incremental Graph Optimizer
Venue: arXiv cs.RO 2018
Year: 2018

Estimation techniques to precisely localize a kinematic platform with GNSS observables can be broadly partitioned into two categories: differential, or undifferenced. The differential techniques (e.g., real-time kinematic (RTK)) have several attractive properties, such as correlated error mitigation and fast convergence; however, to support a differential processing scheme, an infrastructure of reference stations within a proximity of the platform must be in place to construct observation corrections. This infrastructure requirement makes differential processing techniques infeasible in many locations. To mitigate the need for additional receivers within proximity of the platform, the precise point positioning (PPP) method utilizes accurate orbit and clock models to localize the platform. The autonomy of PPP from local reference stations make it an attractive processing scheme for several applications; however, a current disadvantage of PPP is the slow positioning convergence when compared to differential techniques. In this paper, we evaluate the convergence properties of PPP with an incremental graph optimization scheme (Incremental Smoothing and Mapping (iSAM2)), which allows for real-time filtering and smoothing. The characterization is first conducted through a Monte Carlo analysis within a simulation environment, which allows for the variations of parameters, such as atmospheric conditions, satellite geometry, and intensity of multipath. Then, an example collected data set is utilized to validate the trends presented in the simulation study.
Learning Topics using Semantic Locality
Venue: arXiv cs.LG 2018
Year: 2018

The topic modeling discovers the latent topic probability of the given text documents. To generate the more meaningful topic that better represents the given document, we proposed a new feature extraction technique which can be used in the data preprocessing stage. The method consists of three steps. First, it generates the word/word-pair from every single document. Second, it applies a two-way TF-IDF algorithm to word/word-pair for semantic filtering. Third, it uses the K-means algorithm to merge the word pairs that have the similar semantic meaning. Experiments are carried out on the Open Movie Database (OMDb), Reuters Dataset and 20NewsGroup Dataset. The mean Average Precision score is used as the evaluation metric. Comparing our results with other state-of-the-art topic models, such as Latent Dirichlet allocation and traditional Restricted Boltzmann Machines. Our proposed data preprocessing can improve the generated topic accuracy by up to 12.99\%.
A denotational account of C11-style memory
Venue: arXiv cs.PL 2018
Year: 2018

We introduce a denotational semantic framework for shared-memory concurrent programs in a C11-style memory model. This denotational approach is an alternative to techniques based on "execution graphs" and axiomatizations, and it allows for compositional reasoning. Our semantics generalizes from traces (sequences of actions) to pomsets (partial orders of actions): instead of traces and interleaving, we embrace "true" concurrency. We build on techniques from our prior work that gives a denotational semantics to SPARC TSO. We add support for C11's wider range of memory orderings, e.g., acquire-release and relaxed, and support for local variables and various synchronization primitives, while eliminating significant amounts of technical bookkeeping. Our approach features two main components. We first give programs a syntax-directed denotation in terms of sets of pomsets of memory actions. We then give a race-detecting executional interpretation of pomsets using footprints and a local view of state.