OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Attention Network for Visually-aware Food Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Food recommender systems play an important role in assisting users to identify the desired food to eat. Deciding what food to eat is a complex and multi-faceted process, which is influenced by many factors such as the ingredients, appearance of the recipe, the user's personal preference on food, and various contexts like what had been eaten in the past meals. In this work, we formulate the food recommendation problem as predicting user preference on recipes based on three key factors that determine a user's choice on food, namely, 1) the user's (and other users') history; 2) the ingredients of a recipe; and 3) the descriptive image of a recipe. To address this challenging problem, we develop a dedicated neural network based solution Hierarchical Attention based Food Recommendation (HAFR) which is capable of: 1) capturing the collaborative filtering effect like what similar users tend to eat; 2) inferring a user's preference at the ingredient level; and 3) learning user preference from the recipe's visual images. To evaluate our proposed method, we construct a large-scale dataset consisting of millions of ratings from AllRecipes.com. Extensive experiments show that our method outperforms several competing recommender solutions like Factorization Machine and Visual Bayesian Personalized Ranking with an average improvement of 12%, offering promising results in predicting user preference for food. Codes and dataset will be released upon acceptance.
A General Framework for Fair Regression
Venue: arXiv cs.LG 2019
Year: 2019

Fairness, through its many forms and definitions, has become an important issue facing the machine learning community. In this work, we consider how to incorporate group fairness constraints in kernel regression methods, applicable to Gaussian processes, support vector machines, neural network regression and decision tree regression. Further, we focus on examining the effect of incorporating these constraints in decision tree regression, with direct applications to random forests and boosted trees amongst other widespread popular inference techniques. We show that the order of complexity of memory and computation is preserved for such models and tightly bound the expected perturbations to the model in terms of the number of leaves of the trees. Importantly, the approach works on trained models and hence can be easily applied to models in current use and group labels are only required on training data.
FeatureLego: Volume Exploration Using Exhaustive Clustering of Super-Voxels
Venue: arXiv cs.CV 2019
Year: 2019

We present a volume exploration framework, FeatureLego, that uses a novel voxel clustering approach for efficient selection of semantic features. We partition the input volume into a set of compact super-voxels that represent the finest selection granularity. We then perform an exhaustive clustering of these super-voxels using a graph-based clustering method. Unlike the prevalent brute-force parameter sampling approaches, we propose an efficient algorithm to perform this exhaustive clustering. By computing an exhaustive set of clusters, we aim to capture as many boundaries as possible and ensure that the user has sufficient options for efficiently selecting semantically relevant features. Furthermore, we merge all the computed clusters into a single tree of meta-clusters that can be used for hierarchical exploration. We implement an intuitive user-interface to interactively explore volumes using our clustering approach. Finally, we show the effectiveness of our framework on multiple real-world datasets of different modalities.
Measuring Sample Path Causal Influences with Relative Entropy
Venue: arXiv cs.IT 2019
Year: 2019

We present a sample path dependent measure of causal influence between time series. The proposed causal measure is a random sequence, a realization of which enables identification of specific patterns that give rise to high levels of causal influence. We show that these patterns cannot be identified by existing measures such as directed information (DI). We demonstrate how sequential prediction theory may be leveraged to estimate the proposed causal measure and introduce a notion of regret for assessing the performance of such estimators. We prove a finite sample bound on this regret that is determined by the worst case regret of the sequential predictors used in the estimator. Justification for the proposed measure is provided through a series of examples, simulations, and application to stock market data. Within the context of estimating DI, we show that, because joint Markovicity of a pair of processes does not imply the marginal Markovicity of individual processes, commonly used plug-in estimators of DI will be biased for a large subset of jointly Markov processes. We introduce a notion of DI with "stale history", which can be combined with a plug-in estimator to upper and lower bound the DI when marginal Markovicity does not hold.
Aleph: A Leaderless, Asynchronous, Byzantine Fault Tolerant Consensus Protocol
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we propose Aleph, a leaderless, fully asynchronous, Byzantine fault tolerant consensus protocol for ordering messages exchanged among processes. It is based on a distributed construction of a partially ordered set and the algorithm for reaching a consensus on its extension to a total order. To achieve the consensus, the processes perform computations based only on a local copy of the data structure, however, they are bound to end with the same results. Our algorithm uses a dual-threshold coin-tossing scheme as a randomization strategy and establishes the agreement in an expected constant number of rounds. In addition, we introduce a fast way of validating messages that can occur prior to determining the total ordering. This version of the protocol is deprecated. For current version see arXiv:1908.05156.
Deep Reinforcement Learning Autoencoder with Noisy Feedback
Venue: arXiv cs.IT 2019
Year: 2019

End-to-end learning of communication systems enables joint optimization of transmitter and receiver, implemented as deep neural network-based autoencoders, over any type of channel and for an arbitrary performance metric. Recently, an alternating training procedure was proposed which eliminates the need for an explicit channel model. However, this approach requires feedback of real-valued losses from the receiver to the transmitter during training. In this paper, we first show that alternating training works even with a noisy feedback channel. Then, we design a system that learns to transmit real numbers over an unknown channel without a preexisting feedback link. Once trained, this feedback system can be used to communicate losses during alternating training of autoencoders. Evaluations over additive white Gaussian noise and Rayleigh block-fading channels show that end-to-end communication systems trained using the proposed feedback system achieve the same performance as when trained with a perfect feedback link.
Cats or CAT scans: transfer learning from natural or medical image source datasets?
Venue: arXiv cs.CV 2019
Year: 2019

Transfer learning is a widely used strategy in medical image analysis. Instead of only training a network with a limited amount of data from the target task of interest, we can first train the network with other, potentially larger source datasets, creating a more robust model. The source datasets do not have to be related to the target task. For a classification task in lung CT images, we could use both head CT images, or images of cats, as the source. While head CT images appear more similar to lung CT images, the number and diversity of cat images might lead to a better model overall. In this survey we review a number of papers that have performed similar comparisons. Although the answer to which strategy is best seems to be "it depends", we discuss a number of research directions we need to take as a community, to gain more understanding of this topic.
PointGrow: Autoregressively Learned Point Cloud Generation with Self-Attention
Venue: arXiv cs.CV 2019
Year: 2019

Generating 3D point clouds is challenging yet highly desired. This work presents a novel autoregressive model, PointGrow, which can generate diverse and realistic point cloud samples from scratch or conditioned on semantic contexts. This model operates recurrently, with each point sampled according to a conditional distribution given its previously-generated points, allowing inter-point correlations to be well-exploited and 3D shape generative processes to be better interpreted. Since point cloud object shapes are typically encoded by long-range dependencies, we augment our model with dedicated self-attention modules to capture such relations. Extensive evaluations show that PointGrow achieves satisfying performance on both unconditional and conditional point cloud generation tasks, with respect to realism and diversity. Several important applications, such as unsupervised feature learning and shape arithmetic operations, are also demonstrated.
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
Venue: arXiv cs.LG 2019
Year: 2019

Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not hold for arbitrary dissimilarities. PAM uses the medoid instead, the object with the smallest dissimilarity to all others in the cluster. This notion of centrality can be used with any (dis-)similarity, and thus is of high relevance to many domains such as biology that require the use of Jaccard, Gower, or more complex distances. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm to achieve an O(k)-fold speedup in the second SWAP phase of the algorithm, but will still find the same results as the original PAM algorithm. If we slightly relax the choice of swaps performed (at comparable quality), we can further accelerate the algorithm by performing up to k swaps in each iteration. With the substantially faster SWAP, we can now also explore alternative strategies for choosing the initial medoids. We also show how the CLARA and CLARANS algorithms benefit from these modifications. It can easily be combined with earlier approaches to use PAM and CLARA on big data (some of which use PAM as a subroutine, hence can immediately benefit from these improvements), where the performance with high k becomes increasingly important. In experiments on real data with k=100, we observed a 200-fold speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets as long as we can afford to compute a distance matrix, and in particular to higher k (at k=2, the new SWAP was only 1.5 times faster, as the speedup is expected to increase with k).
Subdivision Directional Fields
Venue: arXiv cs.GR 2019
Year: 2019

We present a novel linear subdivision scheme for face-based tangent directional fields on triangle meshes. Our subdivision scheme is based on a novel coordinate-free representation of directional fields as halfedge-based scalar quantities, bridging the finite-element representation with discrete exterior calculus. By commuting with differential operators, our subdivision is structure-preserving: it reproduces curl-free fields precisely, and reproduces divergence-free fields in the weak sense. Moreover, our subdivision scheme directly extends to directional fields with several vectors per face by working on the branched covering space. Finally, we demonstrate how our scheme can be applied to directional-field design, advection, and robust earth mover's distance computation, for efficient and robust computation.
A Substrate-Independent Framework to Characterise Reservoir Computers
Venue: arXiv cs.ET 2019
Year: 2019

The Reservoir Computing (RC) framework states that any non-linear, input-driven dynamical system (the reservoir) exhibiting properties such as a fading memory and input separability can be trained to perform computational tasks. This broad inclusion of systems has led to many new physical substrates for RC. Properties essential for reservoirs to compute are tuned through reconfiguration of the substrate, such as change in virtual topology or physical morphology. As a result, each substrate possesses a unique `quality' -- obtained through reconfiguration -- to realise different reservoirs for different tasks. Here we describe an experimental framework to characterise the quality of potentially any substrate for RC. Our framework reveals that a definition of quality is not only useful to compare substrates, but can help map the non-trivial relationship between properties and task performance. In the wider context, the framework offers a greater understanding as to what makes a dynamical system compute, helping improve the design of future substrates for RC.
Probabilistic Stability of Traffic Load Balancing on Wireless Complex Networks
Venue: arXiv cs.NI 2019
Year: 2019

Load balancing between adjacent base stations (BSs) is important for balancing load distributions and improving service provisioning. Whilst load balancing between any given pair of BSs is beneficial, cascade load sharing can cause network level instability that is hard to predict. The relationship between each BS's load balancing dynamics and the network topology is not understood. In this seminal work on stability analysis, we consider a frequency re-use network with no interference, whereby load balancing dynamics doesn't perturb the individual cells' capacity. Our novelty is to show an exact analytical and also a probabilistic relationship for stability, relating generalized local load balancing dynamics with generalized network topology, as well as the uncertainty we have in load balancing parameters. We prove that the stability analysis given is valid for any generalized load balancing dynamics and topological cell deployment and we believe this general relationship can inform the joint design of both the load balancing dynamics and the neighbour list of the network.
Progress, Justness and Fairness
Venue: arXiv cs.LO 2019
Year: 2019

Fairness assumptions are a valuable tool when reasoning about systems. In this paper, we classify several fairness properties found in the literature and argue that most of them are too restrictive for many applications. As an alternative we introduce the concept of justness.
Provable Robustness of ReLU networks via Maximization of Linear Regions
Venue: arXiv cs.LG 2019
Year: 2019

It has been shown that neural network classifiers are not robust. This raises concerns about their usage in safety-critical systems. We propose in this paper a regularization scheme for ReLU networks which provably improves the robustness of the classifier by maximizing the linear regions of the classifier as well as the distance to the decision boundary. Our techniques allow even to find the minimal adversarial perturbation for a fraction of test points for large networks. In the experiments we show that our approach improves upon adversarial training both in terms of lower and upper bounds on the robustness and is comparable or better than the state-of-the-art in terms of test error and robustness.
Intelligence Beyond the Edge: Inference on Intermittent Embedded Systems
Venue: arXiv cs.DC 2019
Year: 2019

Energy-harvesting technology provides a promising platform for future IoT applications. However, since communication is very expensive in these devices, applications will require inference "beyond the edge" to avoid wasting precious energy on pointless communication. We show that application performance is highly sensitive to inference accuracy. Unfortunately, accurate inference requires large amounts of computation and memory, and energy-harvesting systems are severely resource-constrained. Moreover, energy-harvesting systems operate intermittently, suffering frequent power failures that corrupt results and impede forward progress. This paper overcomes these challenges to present the first full-scale demonstration of DNN inference on an energy-harvesting system. We design and implement SONIC, an intermittence-aware software system with specialized support for DNN inference. SONIC introduces loop continuation, a new technique that dramatically reduces the cost of guaranteeing correct intermittent execution for loop-heavy code like DNN inference. To build a complete system, we further present GENESIS, a tool that automatically compresses networks to optimally balance inference accuracy and energy, and TAILS, which exploits SIMD hardware available in some microcontrollers to improve energy efficiency. Both SONIC & TAILS guarantee correct intermittent execution without any hand-tuning or performance loss across different power systems. Across three neural networks on a commercially available microcontroller, SONIC & TAILS reduce inference energy by 6.9x and 12.2x, respectively, over the state-of-the-art.
Coded Caching for Heterogeneous Systems: An Optimization Perspective
Venue: arXiv cs.IT 2019
Year: 2019

In cache-aided networks, the server populates the cache memories at the users during low-traffic periods, in order to reduce the delivery load during peak-traffic hours. In turn, there exists a fundamental trade-off between the delivery load on the server and the cache sizes at the users. In this paper, we study this trade-off in a multicast network where the server is connected to users with unequal cache sizes and the number of users is less than or equal to the number of library files. We propose centralized uncoded placement and linear delivery schemes which are optimized by solving a linear program. Additionally, we derive a lower bound on the delivery memory trade-off with uncoded placement that accounts for the heterogeneity in cache sizes. We explicitly characterize this trade-off for the case of three end-users, as well as an arbitrary number of end-users when the total memory size at the users is small, and when it is large. Next, we consider a system where the server is connected to the users via rate limited links of different capacities and the server assigns the users' cache sizes subject to a total cache budget. We characterize the optimal cache sizes that minimize the delivery completion time with uncoded placement and linear delivery. In particular, the optimal memory allocation balances between assigning larger cache sizes to users with low capacity links and uniform memory allocation.
A minimalistic approach for fast computation of geodesic distances on triangular meshes
Venue: arXiv cs.CG 2019
Year: 2019

The computation of geodesic distances is an important research topic in Geometry Processing and 3D Shape Analysis as it is a basic component of many methods used in these areas. In this work, we present a minimalistic parallel algorithm based on front propagation to compute approximate geodesic distances on meshes. Our method is practical and simple to implement and does not require any heavy pre-processing. The convergence of our algorithm depends on the number of discrete level sets around the source points from which distance information propagates. To appropriately implement our method on GPUs taking into account memory coalescence problems, we take advantage of a graph representation based on a breadth-first search traversal that works harmoniously with our parallel front propagation approach. We report experiments that show how our method scales with the size of the problem. We compare the mean error and processing time obtained by our method with such measures computed using other methods. Our method produces results in competitive times with almost the same accuracy, especially for large meshes. We also demonstrate its use for solving two classical geometry processing problems: the regular sampling problem and the Voronoi tessellation on meshes.
Large-scale Hierarchical Alignment for Data-driven Text Rewriting
Venue: arXiv cs.CL 2019
Year: 2019

We propose a simple unsupervised method for extracting pseudo-parallel monolingual sentence pairs from comparable corpora representative of two different text styles, such as news articles and scientific papers. Our approach does not require a seed parallel corpus, but instead relies solely on hierarchical search over pre-trained embeddings of documents and sentences. We demonstrate the effectiveness of our method through automatic and extrinsic evaluation on text simplification from the normal to the Simple Wikipedia. We show that pseudo-parallel sentences extracted with our method not only supplement existing parallel data, but can even lead to competitive performance on their own.
FPT algorithms to recognize well covered graphs
Venue: arXiv cs.DS 2019
Year: 2019

Given a graph $G$, let $vc(G)$ and $vc^+(G)$ be the sizes of a minimum and a maximum minimal vertex covers of $G$, respectively. We say that $G$ is well covered if $vc(G)=vc^+(G)$ (that is, all minimal vertex covers have the same size). Determining if a graph is well covered is a coNP-complete problem. In this paper, we obtain $O^*(2^{vc})$-time and $O^*(1.4656^{vc^+})$-time algorithms to decide well coveredness, improving results of Boria et. al. (2015). Moreover, using crown decomposition, we show that such problems admit kernels having linear number of vertices. In 2018, Alves et. al. (2018) proved that recognizing well covered graphs is coW[2]-hard when the independence number $α(G)=n-vc(G)$ is the parameter. Contrasting with such coW[2]-hardness, we present an FPT algorithm to decide well coveredness when $α(G)$ and the degeneracy of the input graph $G$ are aggregate parameters. Finally, we use the primeval decomposition technique to obtain a linear time algorithm for extended $P_4$-laden graphs and $(q,q-4)$-graphs, which is FPT parameterized by $q$, improving results of Klein et al (2013).
Formalizing computability theory via partial recursive functions
Venue: arXiv cs.LO 2019
Year: 2019

We present an extension to the $\mathtt{mathlib}$ library of the Lean theorem prover formalizing the foundations of computability theory. We use primitive recursive functions and partial recursive functions as the main objects of study, and we use a constructive encoding of partial functions such that they are executable when the programs in question provably halt. Main theorems include the construction of a universal partial recursive function and a proof of the undecidability of the halting problem. Type class inference provides a transparent way to supply Gödel numberings where needed and encapsulate the encoding details.
Stability conditions for a decentralised medium access algorithm: single- and multi-hop networks
Venue: arXiv cs.IT 2019
Year: 2019

We consider a decentralised multi-access algorithm, motivated primarily by the control of transmissions in a wireless network. For a finite single-hop network with arbitrary interference constraints we prove stochastic stability under the natural conditions. For infinite and finite single-hop networks, we obtain broad rate-stability conditions. We also consider symmetric finite multi-hop networks and show that the natural condition is sufficient for stochastic stability.