OpenRaiser/Intern-Atlas huggingface dataset:
On an Equivalence Between Single-Server PIR with Side Information and Locally Recoverable Codes
Venue: arXiv cs.IT 2019
Year: 2019

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way. In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRC), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in 'cooperative' locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols. In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.
One Network for Multi-Domains: Domain Adaptive Hashing with Intersectant Generative Adversarial Network
Venue: arXiv cs.CV 2019
Year: 2019

With the recent explosive increase of digital data, image recognition and retrieval become a critical practical application. Hashing is an effective solution to this problem, due to its low storage requirement and high query speed. However, most of past works focus on hashing in a single (source) domain. Thus, the learned hash function may not adapt well in a new (target) domain that has a large distributional difference with the source domain. In this paper, we explore an end-to-end domain adaptive learning framework that simultaneously and precisely generates discriminative hash codes and classifies target domain images. Our method encodes two domains images into a semantic common space, followed by two independent generative adversarial networks arming at crosswise reconstructing two domains' images, reducing domain disparity and improving alignment in the shared space. We evaluate our framework on {four} public benchmark datasets, all of which show that our method is superior to the other state-of-the-art methods on the tasks of object recognition and image retrieval.
Using Database Rule for Weak Supervised Text-to-SQL Generation
Venue: arXiv cs.CL 2019
Year: 2019

We present a simple way to do the task of text-to-SQL problem with weak supervision. We call it Rule-SQL. Given the question and the answer from the database table without the SQL logic form, Rule-SQL use the rules based on table column names and question string for the SQL exploration first and then use the explored SQL for supervised training. We design several rules for reducing the exploration search space. For the deep model, we leverage BERT for the representation layer and separate the model to SELECT, AGG and WHERE parts. The experiment result on WikiSQL outperforms the strong baseline of full supervision and is comparable to the start-of-the-art weak supervised mothods.
Using Deep Learning to Predict Plant Growth and Yield in Greenhouse Environments
Venue: arXiv cs.LG 2019
Year: 2019

Effective plant growth and yield prediction is an essential task for greenhouse growers and for agriculture in general. Developing models which can effectively model growth and yield can help growers improve the environmental control for better production, match supply and market demand and lower costs. Recent developments in Machine Learning (ML) and, in particular, Deep Learning (DL) can provide powerful new analytical tools. The proposed study utilises ML and DL techniques to predict yield and plant growth variation across two different scenarios, tomato yield forecasting and Ficus benjamina stem growth, in controlled greenhouse environments. We deploy a new deep recurrent neural network (RNN), using the Long Short-Term Memory (LSTM) neuron model, in the prediction formulations. Both the former yield, growth and stem diameter values, as well as the microclimate conditions, are used by the RNN architecture to model the targeted growth parameters. A comparative study is presented, using ML methods, such as support vector regression and random forest regression, utilising the mean square error criterion, in order to evaluate the performance achieved by the different methods. Very promising results, based on data that have been obtained from two greenhouses, in Belgium and the UK, in the framework of the EU Interreg SMARTGREEN project (2017-2021), are presented.
Dermtrainer: A Decision Support System for Dermatological Diseases
Venue: arXiv cs.IR 2019
Year: 2019

Dermtrainer is a medical decision support system that assists general practitioners in diagnosing skin diseases and serves as a training platform for dermatologists. Its key components are a comprehensive dermatological knowledge base, a clinical algorithm for diagnosing skin diseases, a reasoning component for deducing the most likely differential diagnoses for a patient, and a library of high-quality images. This report describes the technical components of the system, in particular the ranking algorithm for retrieving appropriate diseases as diagnoses.
Towards the Definition of Enterprise Architecture Debts
Venue: arXiv cs.SE 2019
Year: 2019

In the software development industry, technical debt is regarded as a critical issue in term of the negative consequences such as increased software development cost, low product quality, decreased maintainability, and slowed progress to the long-term success of developing software. However, despite the vast research contributions in technical debt management for software engineering, the idea of technical debt fails to provide a holistic consideration to include both IT and business aspects. Further, implementing an enterprise architecture (EA) project might not always be a success due to uncertainty and unavailability of resources. Therefore, we relate the consequences of EA implementation failure with a new metaphor --Enterprise Architecture Debt (EA Debt). We anticipate that the accumulation of EA Debt will negatively influence EA quality, also expose the business into risk.
A Capsule Network for Recommendation and Explaining What You Like and Dislike
Venue: arXiv cs.IR 2019
Year: 2019

User reviews contain rich semantics towards the preference of users to features of items. Recently, many deep learning based solutions have been proposed by exploiting reviews for recommendation. The attention mechanism is mainly adopted in these works to identify words or aspects that are important for rating prediction. However, it is still hard to understand whether a user likes or dislikes an aspect of an item according to what viewpoint the user holds and to what extent, without examining the review details. Here, we consider a pair of a viewpoint held by a user and an aspect of an item as a logic unit. Reasoning a rating behavior by discovering the informative logic units from the reviews and resolving their corresponding sentiments could enable a better rating prediction with explanation. To this end, in this paper, we propose a capsule network based model for rating prediction with user reviews, named CARP. For each user-item pair, CARP is devised to extract the informative logic units from the reviews and infer their corresponding sentiments. The model firstly extracts the viewpoints and aspects from the user and item review documents respectively. Then we derive the representation of each logic unit based on its constituent viewpoint and aspect. A sentiment capsule architecture with a novel Routing by Bi-Agreement mechanism is proposed to identify the informative logic unit and the sentiment based representations in user-item level for rating prediction. Extensive experiments are conducted over seven real-world datasets with diverse characteristics. Our results demonstrate that the proposed CARP obtains substantial performance gain over recently proposed state-of-the-art models in terms of prediction accuracy. Further analysis shows that our model can successfully discover the interpretable reasons at a finer level of granularity.
An Improvement of PAA on Trend-Based Approximation for Time Series
Venue: arXiv cs.LG 2019
Year: 2019

Piecewise Aggregate Approximation (PAA) is a competitive basic dimension reduction method for high-dimensional time series mining. When deployed, however, the limitations are obvious that some important information will be missed, especially the trend. In this paper, we propose two new approaches for time series that utilize approximate trend feature information. Our first method is based on relative mean value of each segment to record the trend, which divide each segment into two parts and use the numerical average respectively to represent the trend. We proved that this method satisfies lower bound which guarantee no false dismissals. Our second method uses a binary string to record the trend which is also relative to mean in each segment. Our methods are applied on similarity measurement in classification and anomaly detection, the experimental results show the improvement of accuracy and effectiveness by extracting the trend feature suitably.
Verifying that a compiler preserves concurrent value-dependent information-flow security
Venue: arXiv cs.LO 2019
Year: 2019

It is common to prove by reasoning over source code that programs do not leak sensitive data. But doing so leaves a gap between reasoning and reality that can only be filled by accounting for the behaviour of the compiler. This task is complicated when programs enforce value-dependent information-flow security properties (in which classification of locations can vary depending on values in other locations) and complicated further when programs exploit shared-variable concurrency. Prior work has formally defined a notion of concurrency-aware refinement for preserving value-dependent security properties. However, that notion is considerably more complex than standard refinement definitions typically applied in the verification of semantics preservation by compilers. To date it remains unclear whether it can be applied to a realistic compiler, because there exist no general decomposition principles for separating it into smaller, more familiar, proof obligations. In this work, we provide such a decomposition principle, which we show can almost halve the complexity of proving secure refinement. Further, we demonstrate its applicability to secure compilation, by proving in Isabelle/HOL the preservation of value-dependent security by a proof-of-concept compiler from an imperative While language to a generic RISC-style assembly language, for programs with shared-memory concurrency mediated by locking primitives. Finally, we execute our compiler in Isabelle on a While language model of the Cross Domain Desktop Compositor, demonstrating to our knowledge the first use of a compiler verification result to carry an information-flow security property down to the assembly-level model of a non-trivial concurrent program.
TRIDENT: A load-balancing Clos-network Packet Switch with Queues between Input and Central Stages and In-Order Forwarding
Venue: arXiv cs.NI 2019
Year: 2019

We propose a three-stage load balancing packet switch and its configuration scheme. The input- and central-stage switches are bufferless crossbars, and the output-stage switches are buffered crossbars. We call this switch ThRee-stage Clos-network swItch with queues at the middle stage and DEtermiNisTic scheduling (TRIDENT), and the switch is cell based. The proposed configuration scheme uses predetermined and periodic interconnection patterns in the input and central modules to load-balance and route traffic, therefore; it has low configuration complexity. The operation of the switch includes a mechanism applied at input and output modules to forward cells in sequence. TRIDENT achieves 100% throughput under uniform and nonuniform admissible traffic with independent and identical distributions (i.i.d.). The switch achieves this high performance using a low-complexity architecture while performing in-sequence forwarding and no central-stage expansion or memory speedup. Our discussion includes throughput analysis, where we describe the operations the configuration mechanism performs on the traffic traversing the switch, and proof of in-sequence forwarding. We present a simulation analysis as a practical demonstration of the switch performance under uniform and nonuniform i.i.d. traffic.
Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
Venue: arXiv cs.LG 2019
Year: 2019

We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.
Translating Asynchronous Games for Distributed Synthesis (Full Version)
Venue: arXiv cs.LO 2019
Year: 2019

In distributed synthesis, we generate a set of process implementations that, together, accomplish an objective against all possible behaviors of the environment. A lot of recent work has focussed on systems with causal memory, i.e., sets of asynchronous processes that exchange their causal histories upon synchronization. Decidability results for this problem have been stated either in terms of control games, which extend Zielonka's asynchronous automata by partitioning the actions into controllable and uncontrollable, or in terms of Petri games, which extend Petri nets by partitioning the tokens into system and environment players. The precise connection between these two models was so far, however, an open question. In this paper, we provide the first formal connection between control games and Petri games. We establish the equivalence of the two game models based on weak bisimulations between their strategies. For both directions, we show that a game of one type can be translated into an equivalent game of the other type. We provide exponential upper and lower bounds for the translations. Our translations make it possible to transfer and combine decidability results between the two types of games. Exemplarily, we translate decidability in acyclic communication architectures, originally obtained for control games, to Petri games, and decidability in single-process systems, originally obtained for Petri games, to control games.
iPool -- Information-based Pooling in Hierarchical Graph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

With the advent of data science, the analysis of network or graph data has become a very timely research problem. A variety of recent works have been proposed to generalize neural networks to graphs, either from a spectral graph theory or a spatial perspective. The majority of these works however focus on adapting the convolution operator to graph representation. At the same time, the pooling operator also plays an important role in distilling multiscale and hierarchical representations but it has been mostly overlooked so far. In this paper, we propose a parameter-free pooling operator, called iPool, that permits to retain the most informative features in arbitrary graphs. With the argument that informative nodes dominantly characterize graph signals, we propose a criterion to evaluate the amount of information of each node given its neighbors, and theoretically demonstrate its relationship to neighborhood conditional entropy. This new criterion determines how nodes are selected and coarsened graphs are constructed in the pooling layer. The resulting hierarchical structure yields an effective isomorphism-invariant representation of networked data in arbitrary topologies. The proposed strategy is evaluated in terms of graph classification on a collection of public graph datasets, including bioinformatics and social networks, and achieves state-of-the-art performance on most of the datasets.
Coherence of Type Class Resolution
Venue: arXiv cs.PL 2019
Year: 2019

Elaboration-based type class resolution, as found in languages like Haskell, Mercury and PureScript, is generally nondeterministic: there can be multiple ways to satisfy a wanted constraint in terms of global instances and locally given constraints. Coherence is the key property that keeps this sane; it guarantees that, despite the nondeterminism, programs still behave predictably. Even though elaboration-based resolution is generally assumed coherent, as far as we know, there is no formal proof of this property in the presence of sources of nondeterminism, like superclasses and flexible contexts. This paper provides a formal proof to remedy the situation. The proof is non-trivial because the semantics elaborates resolution into a target language where different elaborations can be distinguished by contexts that do not have a source language counterpart. Inspired by the notion of full abstraction, we present a two-step strategy that first elaborates nondeterministically into an intermediate language that preserves contextual equivalence, and then deterministically elaborates from there into the target language. We use an approach based on logical relations to establish contextual equivalence and thus coherence for the first step of elaboration, while the second step's determinism straightforwardly preserves this coherence property.
Understanding GCC Builtins to Develop Better Tools
Venue: arXiv cs.PL 2019
Year: 2019

C programs can use compiler builtins to provide functionality that the C language lacks. On Linux, GCC provides several thousands of builtins that are also supported by other mature compilers, such as Clang and ICC. Maintainers of other tools lack guidance on whether and which builtins should be implemented to support popular projects. To assist tool developers who want to support GCC builtins, we analyzed builtin use in 4,913 C projects from GitHub. We found that 37% of these projects relied on at least one builtin. Supporting an increasing proportion of projects requires support of an exponentially increasing number of builtins; however, implementing only 10 builtins already covers over 30% of the projects. Since we found that many builtins in our corpus remained unused, the effort needed to support 90% of the projects is moderate, requiring about 110 builtins to be implemented. For each project, we analyzed the evolution of builtin use over time and found that the majority of projects mostly added builtins. This suggests that builtins are not a legacy feature and must be supported in future tools. Systematic testing of builtin support in existing tools revealed that many lacked support for builtins either partially or completely; we also discovered incorrect implementations in various tools, including the formally verified CompCert compiler.
Improved hardness for H-colourings of G-colourable graphs
Venue: arXiv cs.CC 2019
Year: 2019

We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems. First, we show NP-hardness of colouring $k$-colourable graphs with $\binom{k}{\lfloor k/2\rfloor}-1$ colours for every $k\geq 4$. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring $k$-colourable graphs with $2k-1$ colours for $k\geq 3$, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring $k$-colourable graphs with $2^{k^{1/3}}$ colours for sufficiently large $k$. Thus, for $k\geq 4$, we improve from known linear/sub-exponential gaps to exponential gaps. Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS'19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond $K_3$, including square-free graphs and circular cliques (leaving $K_4$ and larger cliques open). Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems.
Post-editese: an Exacerbated Translationese
Venue: arXiv cs.CL 2019
Year: 2019

Post-editing (PE) machine translation (MT) is widely used for dissemination because it leads to higher productivity than human translation from scratch (HT). In addition, PE translations are found to be of equal or better quality than HTs. However, most such studies measure quality solely as the number of errors. We conduct a set of computational analyses in which we compare PE against HT on three different datasets that cover five translation directions with measures that address different translation universals and laws of translation: simplification, normalisation and interference. We find out that PEs are simpler and more normalised and have a higher degree of interference from the source language than HTs.
An Open Source AutoML Benchmark
Venue: arXiv cs.LG 2019
Year: 2019

In recent years, an active field of research has developed around automated machine learning (AutoML). Unfortunately, comparing different AutoML systems is hard and often done incorrectly. We introduce an open, ongoing, and extensible benchmark framework which follows best practices and avoids common mistakes. The framework is open-source, uses public datasets and has a website with up-to-date results. We use the framework to conduct a thorough comparison of 4 AutoML systems across 39 datasets and analyze the results.
Mise en abyme with artificial intelligence: how to predict the accuracy of NN, applied to hyper-parameter tuning
Venue: arXiv cs.LG 2019
Year: 2019

In the context of deep learning, the costliest phase from a computational point of view is the full training of the learning algorithm. However, this process is to be used a significant number of times during the design of a new artificial neural network, leading therefore to extremely expensive operations. Here, we propose a low-cost strategy to predict the accuracy of the algorithm, based only on its initial behaviour. To do so, we train the network of interest up to convergence several times, modifying its characteristics at each training. The initial and final accuracies observed during this beforehand process are stored in a database. We then make use of both curve fitting and Support Vector Machines techniques, the latter being trained on the created database, to predict the accuracy of the network, given its accuracy on the primary iterations of its learning. This approach can be of particular interest when the space of the characteristics of the network is notably large or when its full training is highly time-consuming. The results we obtained are promising and encouraged us to apply this strategy to a topical issue: hyper-parameter optimisation (HO). In particular, we focused on the HO of a convolutional neural network for the classification of the databases MNIST and CIFAR-10. By using our method of prediction, and an algorithm implemented by us for a probabilistic exploration of the hyper-parameter space, we were able to find the hyper-parameter settings corresponding to the optimal accuracies already known in literature, at a quite low-cost.