OpenRaiser/Intern-Atlas huggingface dataset:
Analogy-Based Preference Learning with Kernels
Venue: arXiv cs.LG 2019
Year: 2019

Building on a specific formalization of analogical relationships of the form "A relates to B as C relates to D", we establish a connection between two important subfields of artificial intelligence, namely analogical reasoning and kernel-based machine learning. More specifically, we show that so-called analogical proportions are closely connected to kernel functions on pairs of objects. Based on this result, we introduce the analogy kernel, which can be seen as a measure of how strongly four objects are in analogical relationship. As an application, we consider the problem of object ranking in the realm of preference learning, for which we develop a new method based on support vector machines trained with the analogy kernel. Our first experimental results for data sets from different domains (sports, education, tourism, etc.) are promising and suggest that our approach is competitive to state-of-the-art algorithms in terms of predictive accuracy.
On the Dimensionality of Embeddings for Sparse Features and Data
Venue: arXiv cs.LG 2019
Year: 2019

In this note we discuss a common misconception, namely that embeddings are always used to reduce the dimensionality of the item space. We show that when we measure dimensionality in terms of information entropy then the embedding of sparse probability distributions, that can be used to represent sparse features or data, may or not reduce the dimensionality of the item space. However, the embeddings do provide a different and often more meaningful representation of the items for a particular task at hand. Also, we give upper bounds and more precise guidelines for choosing the embedding dimension.
On the effect of the activation function on the distribution of hidden nodes in a deep network
Venue: arXiv cs.LG 2019
Year: 2019

We analyze the joint probability distribution on the lengths of the vectors of hidden variables in different layers of a fully connected deep network, when the weights and biases are chosen randomly according to Gaussian distributions, and the input is in $\{ -1, 1\}^N$. We show that, if the activation function $ϕ$ satisfies a minimal set of assumptions, satisfied by all activation functions that we know that are used in practice, then, as the width of the network gets large, the `length process' converges in probability to a length map that is determined as a simple function of the variances of the random weights and biases, and the activation function $ϕ$. We also show that this convergence may fail for $ϕ$ that violate our assumptions.
Solar-Sail Deep Space Trajectory Optimization Using Successive Convex Programming
Venue: arXiv cs.CE 2019
Year: 2019

This paper presents a novel methodology for solving the time-optimal trajectory optimization problem for interplanetary solar-sail missions using successive convex programming. Based on the non-convex problem, different convexification technologies, such as change of variables, successive linearization, trust regions and virtual control, are discussed to convert the original problem into the formulation of successive convex programming. Because of the free final-time, successive linearization is performed iteratively for the nonconvex terminal state constraints. After the convexification process, each of problems becomes a convex problem, which can be solved effectively. An augmented objective function is introduced to ensure the convergence performance and effectiveness of our algorithm. After that, algorithms are designed to solve the discrete sub-problems in a successive solution procedure. Finally, numerical results demonstrate the effectiveness and accuracy of our algorithms.
StaBL - State Based Language for Specification of Web Applications
Venue: arXiv cs.SE 2019
Year: 2019

Context and motivation: Usage of Formal Specification languages is scarce in web application development as compared to safety critical/hardware systems. Question/problem: An apt formal specification language should provide the following features: Firstly, it should have well-defined semantics, so that specifications written in it can not be inherently ambiguous. Secondly, it should have tool support for automatic detection of specification bugs. Additionally, for domains like web development, it is important that specification formalisms build over familiar notations, as the benefits of learning highly mathematical notations in such domains are perceived to be low. Principal ideas/results: This work presents a State Based Language inspired by Statecharts called StaBL for specification of web applications, and how StaBL can be used for writing such specifications. We also present modifications to the language w.r.t Statechart which facilitate writing modular and scalable specification. Contribution: In particular, we present the feature of locally scoped variables with inter-state data-flow. We summarise our experience of developing specifications with StaBL, which shows that StaBL specifications, on the one hand, are able to capture most essential elements of the functional aspects of a web application while foregoing much of the verbosity of a regular programming language.
Languages ordered by the subword order
Venue: arXiv cs.FL 2019
Year: 2019

We consider a language together with the subword relation, the cover relation, and regular predicates. For such structures, we consider the extension of first-order logic by threshold- and modulo-counting quantifiers. Depending on the language, the used predicates, and the fragment of the logic, we determine four new combinations that yield decidable theories. These results extend earlier ones where only the language of all words without the cover relation and fragments of first-order logic were considered.
Superlight -- A Permissionless, Light-client Only Blockchain with Self-Contained Proofs and BLS Signatures
Venue: arXiv cs.DC 2019
Year: 2019

Blockchain protocols are based on a distributed database where stored data is guaranteed to be immutable. The requirement that all nodes have to maintain their own local copy of the database ensures security while consensus mechanisms help deciding which data gets added to the database and keep powerful adversaries from derailing the system. However, since the database that forms the foundation of a blockchain is a continuously growing list of blocks, scalability is an inherent problem of this technology. Some public blockchains need a few 100 GB to Terabytes of storage. In this work, we present the concept Superlight with self-contained proofs, which is designed to improve scalability of a public blockchain, while preserving security and decentralization. Instead of all nodes having a local copy of the whole blockchain to verify a transaction, nodes can derive the validity of a transaction by only using block headers. To keep the block headers compact, BLS signatures are used to combine signatures. We provide a definition of SCPs and show the required steps of a client to create a proof that is accepted by other nodes for transferring funds. The advantage of such a light-client-only blockchain is the lower storage requirement, while the drawback is an increased computational complexity due to BLS signatures, limited use-cases due to lack of a global state, and the requirement for an interactive protocol between sender, receiver, and miner to create a transaction.
Improved encoding and decoding for non-adaptive threshold group testing
Venue: arXiv cs.IT 2019
Year: 2019

The goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. A test is positive if it has at least $u$ defective items and negative otherwise. Our objective is to identify defective items in sublinear time the number of items, e.g., $\mathrm{poly}(d, \ln{n}),$ by using the number of tests as low as possible. In this paper, we reduce the number of tests to $O \left( h \times \frac{d^2 \ln^2{n}}{\mathsf{W}^2(d \ln{n})} \right)$ and the decoding time to $O \left( \mathrm{dec}_0 \times h \right),$ where $\\mathrm{dec}_0 = O \left( \frac{d^{3.57} \ln^{6.26}{n}}{\mathsf{W}^{6.26}(d \ln{n})} \right) + O \left( \frac{d^6 \ln^4{n}}{\mathsf{W}^4(d \ln{n})} \right)$, $h = O\left( \frac{d_0^2 \ln{\frac{n}{d_0}}}{(1-p)^2} \right)$ , $d_0 = \max\{u, d - u \}$, $p \in [0, 1),$ and $\mathsf{W}(x) = Θ\left( \ln{x} - \ln{\ln{x}} \right).$ If the number of tests is increased to $O\left( h \times \frac{d^2\ln^3{n}}{\mathsf{W}^2(d \ln{n})} \right),$ the decoding complexity is reduced to $O \left(\mathrm{dec}_1 \times h \right),$ where $\mathrm{dec}_1 = \max \left\{ \frac{d^2 \ln^3{n}}{\mathsf{W}^2(d \ln{n})}, \frac{ud \ln^4{n}}{\mathsf{W}^3(d \ln{n})} \right\}.$ Moreover, our proposed scheme is capable of handling errors in test outcomes.
On Relativistic $f$-Divergences
Venue: arXiv cs.LG 2019
Year: 2019

This paper provides a more rigorous look at Relativistic Generative Adversarial Networks (RGANs). We prove that the objective function of the discriminator is a statistical divergence for any concave function $f$ with minimal properties ($f(0)=0$, $f'(0) \neq 0$, $\sup_x f(x)>0$). We also devise a few variants of relativistic $f$-divergences. Wasserstein GAN was originally justified by the idea that the Wasserstein distance (WD) is most sensible because it is weak (i.e., it induces a weak topology). We show that the WD is weaker than $f$-divergences which are weaker than relativistic $f$-divergences. Given the good performance of RGANs, this suggests that WGAN does not performs well primarily because of the weak metric, but rather because of regularization and the use of a relativistic discriminator. We also take a closer look at estimators of relativistic $f$-divergences. We introduce the minimum-variance unbiased estimator (MVUE) for Relativistic paired GANs (RpGANs; originally called RGANs which could bring confusion) and show that it does not perform better. Furthermore, we show that the estimator of Relativistic average GANs (RaGANs) is only asymptotically unbiased, but that the finite-sample bias is small. Removing this bias does not improve performance.
Problem Formulation and Fairness
Venue: arXiv cs.CY 2019
Year: 2019

Formulating data science problems is an uncertain and difficult process. It requires various forms of discretionary work to translate high-level objectives or strategic goals into tractable problems, necessitating, among other things, the identification of appropriate target variables and proxies. While these choices are rarely self-evident, normative assessments of data science projects often take them for granted, even though different translations can raise profoundly different ethical concerns. Whether we consider a data science project fair often has as much to do with the formulation of the problem as any property of the resulting model. Building on six months of ethnographic fieldwork with a corporate data science team---and channeling ideas from sociology and history of science, critical data studies, and early writing on knowledge discovery in databases---we describe the complex set of actors and activities involved in problem formulation. Our research demonstrates that the specification and operationalization of the problem are always negotiated and elastic, and rarely worked out with explicit normative considerations in mind. In so doing, we show that careful accounts of everyday data science work can help us better understand how and why data science problems are posed in certain ways---and why specific formulations prevail in practice, even in the face of what might seem like normatively preferable alternatives. We conclude by discussing the implications of our findings, arguing that effective normative interventions will require attending to the practical work of problem formulation.
High-Fidelity Vector Space Models of Structured Data
Venue: arXiv cs.AI 2019
Year: 2019

Machine learning systems regularly deal with structured data in real-world applications. Unfortunately, such data has been difficult to faithfully represent in a way that most machine learning techniques would expect, i.e. as a real-valued vector of a fixed, pre-specified size. In this work, we introduce a novel approach that compiles structured data into a satisfiability problem which has in its set of solutions at least (and often only) the input data. The satisfiability problem is constructed from constraints which are generated automatically a priori from a given signature, thus trivially allowing for a bag-of-words-esque vector representation of the input to be constructed. The method is demonstrated in two areas, automated reasoning and natural language processing, where it is shown to produce vector representations of natural-language sentences and first-order logic clauses that can be precisely translated back to their original, structured input forms.
Data Querying and Access Control for Secure Multiparty Computation
Venue: arXiv cs.CR 2019
Year: 2019

In the Internet of Things and smart environments data, collected from distributed sensors, is typically stored and processed by a central middleware. This allows applications to query the data they need for providing further services. However, centralization of data causes several privacy threats: The middleware becomes a third party which has to be trusted, linkage and correlation of data from different context becomes possible and data subject lose control over their data. Hence, other approaches than centralized processing should be considered. Here, Secure Multiparty Computation is a promising candidate for secure and privacy-preserving computation happening close to the sources of the data. In order to make SMC fit for application in these contexts, we extend SMC to act as a service: We provide elements which allow third parties to query computed data from a group of peers performing SMC. Furthermore, we establish fine-granular access control on the level of individual data queries, yielding data protection of the computed results. By adding measures to inform data sources about requests and the usage of their data, we show how a fully privacy-preserving service can be built on the foundation of SMC.
Image Recognition of Tea Leaf Diseases Based on Convolutional Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

In order to identify and prevent tea leaf diseases effectively, convolution neural network (CNN) was used to realize the image recognition of tea disease leaves. Firstly, image segmentation and data enhancement are used to preprocess the images, and then these images were input into the network for training. Secondly, to reach a higher recognition accuracy of CNN, the learning rate and iteration numbers were adjusted frequently and the dropout was added properly in the case of over-fitting. Finally, the experimental results show that the recognition accuracy of CNN is 93.75%, while the accuracy of SVM and BP neural network is 89.36% and 87.69% respectively. Therefore, the recognition algorithm based on CNN is better in classification and can improve the recognition efficiency of tea leaf diseases effectively.
Guess What's on my Screen? Clustering Smartphone Screenshots with Active Learning
Venue: arXiv cs.CV 2019
Year: 2019

A significant proportion of individuals' daily activities is experienced through digital devices. Smartphones in particular have become one of the preferred interfaces for content consumption and social interaction. Identifying the content embedded in frequently-captured smartphone screenshots is thus a crucial prerequisite to studies of media behavior and health intervention planning that analyze activity interplay and content switching over time. Screenshot images can depict heterogeneous contents and applications, making the a priori definition of adequate taxonomies a cumbersome task, even for humans. Privacy protection of the sensitive data captured on screens means the costs associated with manual annotation are large, as the effort cannot be crowd-sourced. Thus, there is need to examine utility of unsupervised and semi-supervised methods for digital screenshot classification. This work introduces the implications of applying clustering on large screenshot sets when only a limited amount of labels is available. In this paper we develop a framework for combining K-Means clustering with Active Learning for efficient leveraging of labeled and unlabeled samples, with the goal of discovering latent classes and describing a large collection of screenshot data. We tested whether SVM-embedded or XGBoost-embedded solutions for class probability propagation provide for more well-formed cluster configurations. Visual and textual vector representations of the screenshot images are derived and combined to assess the relative contribution of multi-modal features to the overall performance.
Transfer Representation Learning with TSK Fuzzy System
Venue: arXiv cs.LG 2019
Year: 2019

Transfer learning can address the learning tasks of unlabeled data in the target domain by leveraging plenty of labeled data from a different but related source domain. A core issue in transfer learning is to learn a shared feature space in where the distributions of the data from two domains are matched. This learning process can be named as transfer representation learning (TRL). The feature transformation methods are crucial to ensure the success of TRL. The most commonly used feature transformation method in TRL is kernel-based nonlinear mapping to the high-dimensional space followed by linear dimensionality reduction. But the kernel functions are lack of interpretability and are difficult to be selected. To this end, the TSK fuzzy system (TSK-FS) is combined with transfer learning and a more intuitive and interpretable modeling method, called transfer representation learning with TSK-FS (TRL-TSK-FS) is proposed in this paper. Specifically, TRL-TSK-FS realizes TRL from two aspects. On one hand, the data in the source and target domains are transformed into the fuzzy feature space in which the distribution distance of the data between two domains is min-imized. On the other hand, discriminant information and geo-metric properties of the data are preserved by linear discriminant analysis and principal component analysis. In addition, another advantage arises with the proposed method, that is, the nonlinear transformation is realized by constructing fuzzy mapping with the antecedent part of the TSK-FS instead of kernel functions which are difficult to be selected. Extensive experiments are conducted on the text and image datasets. The results obviously show the superiority of the proposed method.
Macroscopic Lattice Boltzmann Method (MacLAB)
Venue: arXiv cs.CE 2019
Year: 2019

The birth of the lattice Boltzmann method (LBM) fulfils a dream that simple arithmetic calculations can simulate complex fluid flows without solving complicated partial differential flow equations. Its power and potential of resolving more and more challenging physical problems have been and are being demonstrated in science and engineering covering a wide range of disciplines such as physics, chemistry, biology, material science and image analysis. The method is a highly simplified model for fluid flows using a few limited fictitious particles that move one grid at a constant time interval and collide each other at a grid point on uniform lattices, which are the two routine steps for implementation of the method to simulate fluid flows. As such, a real complex particle dynamics is approximated as a regular particle model using three parameters of lattice size, particle speed and collision operator. A fundamental question is "Are the two steps integral to the method or can the three parameters be reduced to one for a minimal lattice Boltzmann method?". Here, I show that the collision step can be removed and the standard LBM can be reformulated into a simple macroscopic lattice Boltzmann method (MacLAB). This model relies on macroscopic physical variables only and is completely defined by one basic parameter of lattice size dx, bringing the LBM into a precise "Lattice" Boltzmann method. The viscous effect on flows is naturally embedded through the particle speed, making it an ideal automatic simulator for fluid flows. The findings have been demonstrated and confirmed with numerical tests including flows that are independent of and dependent on fluid viscosity, 2D and 3D cavity flows, and an unsteady Taylor-Green vortex flow. This provides an efficient and powerful model for resolving physical problems in various disciplines of science and engineering.
Generalized Deduplication: Bounds, Convergence, and Asymptotic Properties
Venue: arXiv cs.IT 2019
Year: 2019

We study a generalization of deduplication, which enables lossless deduplication of highly similar data and show that standard deduplication with fixed chunk length is a special case. We provide bounds on the expected length of coded sequences for generalized deduplication and show that the coding has asymptotic near-entropy cost under the proposed source model. More importantly, we show that generalized deduplication allows for multiple orders of magnitude faster convergence than standard deduplication. This means that generalized deduplication can provide compression benefits much earlier than standard deduplication, which is key in practical systems. Numerical examples demonstrate our results, showing that our lower bounds are achievable, and illustrating the potential gain of using the generalization over standard deduplication. In fact, we show that even for a simple case of generalized deduplication, the gain in convergence speed is linear with the size of the data chunks.
Attack-resistant Spanning Tree Construction in Route-Restricted Overlay Networks
Venue: arXiv cs.CR 2019
Year: 2019

Nodes in route-restricted overlays have an immutable set of neighbors, explicitly specified by their users. Popular examples include payment networks such as the Lightning network as well as social overlays such as the Dark Freenet. Routing algorithms are central to such overlays as they enable communication between nodes that are not directly connected. Recent results show that algorithms based on spanning trees are the most promising provably efficient choice. However, all suggested solutions fail to address how distributed spanning tree algorithms can deal with active denial of service attacks by malicious nodes. In this work, we design a novel self-stabilizing spanning tree construction algorithm that utilizes cryptographic signatures and prove that it reduces the set of nodes affected by active attacks. Our simulations substantiate this theoretical result with concrete values based on real-world data sets. In particular, our results indicate that our algorithm reduces the number of affected nodes by up to 74% compared to state-of-the-art attack-resistant spanning tree constructions.
On NP-completeness of the cell formation problem
Venue: arXiv cs.CC 2019
Year: 2019

In the current paper we provide a proof of NP-completeness for the CFP problem with the fractional grouping efficacy objective. For this purpose we first consider the CFP with the linear objective minimizing the total number of exceptions and voids. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete (Amit, 2004). Then we suggest a reduction of the CFP problem with the linear objective function to the CFP with the grouping efficacy objective.