OpenRaiser/Intern-Atlas huggingface dataset:
Achieving Single-Sensor Complex Activity Recognition from Multi-Sensor Training Data
Venue: arXiv cs.HC 2020
Year: 2020

In this study, we propose a method for single sensor-based activity recognition, trained with data from multiple sensors. There is no doubt that the performance of complex activity recognition systems increases when we use enough sensors with sufficient quality, however using such rich sensors may not be feasible in real-life situations for various reasons such as user comfort, privacy, battery-preservation, and/or costs. In many cases, only one device such as a smartphone is available, and it is challenging to achieve high accuracy with a single sensor, more so for complex activities. Our method combines representation learning with feature mapping to leverage multiple sensor information made available during training while using a single sensor during testing or in real usage. Our results show that the proposed approach can improve the F1-score of the complex activity recognition by up to 17\% compared to that in training while utilizing the same sensor data in a new user scenario.
MGA: Momentum Gradient Attack on Network
Venue: arXiv cs.SI 2020
Year: 2020

The adversarial attack methods based on gradient information can adequately find the perturbations, that is, the combinations of rewired links, thereby reducing the effectiveness of the deep learning model based graph embedding algorithms, but it is also easy to fall into a local optimum. Therefore, this paper proposes a Momentum Gradient Attack (MGA) against the GCN model, which can achieve more aggressive attacks with fewer rewiring links. Compared with directly updating the original network using gradient information, integrating the momentum term into the iterative process can stabilize the updating direction, which makes the model jump out of poor local optimum and enhance the method with stronger transferability. Experiments on node classification and community detection methods based on three well-known network embedding algorithms show that MGA has a better attack effect and transferability.
Lipschitz standardization for multivariate learning
Venue: arXiv cs.LG 2020
Year: 2020

Probabilistic learning is increasingly being tackled as an optimization problem, with gradient-based approaches as predominant methods. When modelling multivariate likelihoods, a usual but undesirable outcome is that the learned model fits only a subset of the observed variables, overlooking the rest. In this work, we study this problem through the lens of multitask learning (MTL), where similar effects have been broadly studied. While MTL solutions do not directly apply in the probabilistic setting (as they cannot handle the likelihood constraints) we show that similar ideas may be leveraged during data preprocessing. First, we show that data standardization often helps under common continuous likelihoods, but it is not enough in the general case, specially under mixed continuous and discrete likelihood models. In order for balance multivariate learning, we then propose a novel data preprocessing, Lipschitz standardization, which balances the local Lipschitz smoothness across variables. Our experiments on real-world datasets show that Lipschitz standardization leads to more accurate multivariate models than the ones learned using existing data preprocessing techniques. The models and datasets employed in the experiments can be found in https://github.com/adrianjav/lipschitz-standardization.
Upper and Lower Bounds on the Space Complexity of Detectable Object
Venue: arXiv cs.DC 2020
Year: 2020

The emergence of systems with non-volatile main memory (NVM) increases the interest in the design of \emph{recoverable concurrent objects} that are robust to crash-failures, since their operations are able to recover from such failures by using state retained in NVM. Of particular interest are recoverable algorithms that, in addition to ensuring object consistency, also provide \emph{detectability}, a correctness condition requiring that the recovery code can infer if the failed operation was linearized or not and, in the former case, obtain its response. In this work, we investigate the space complexity of detectable algorithms and the external support they require. We make the following three contributions. First, we present the first wait-free bounded-space detectable read/write and CAS object implementations. Second, we prove that the bit complexity of every $N$-process obstruction-free detectable CAS implementation, assuming values from a domain of size at least $N$, is $Ω(N)$. Finally, we prove that the following holds for obstruction-free detectable implementations of a large class of objects: their recoverable operations must be provided with \emph{auxiliary state} -- state that is not required by the non-recoverable counterpart implementation -- whose value must be provided from outside the operation, either by the system or by the caller of the operation. In contrast, this external support is, in general, not required if the recoverable algorithm is not detectable.
Symmetric uncoded caching schemes with low subpacketization levels
Venue: arXiv cs.IT 2020
Year: 2020

Caching is a commonly used technique in content-delivery networks which aims to deliver information from hosting servers to users in the most efficient way. In 2014, Maddah-Ali and Niessen formulated caching into a formal information theoretic problem and it has gained a lot of attention since then. It is known that the caching schemes proposed by Ali-Niesen and Yu et. al. are optimal, that is, they require the least number of transmissions from the server to satisfy all users' demands. However for these schemes to work, each file needs to be partitioned into $F^*$ subfiles ($F^*$ is called the subpacketization level of files) with $F^*$ growing exponentially in the number $K$ of users. As a result, it is problematic to apply these schemes in practical situations, where $K$ tends to be very large. There rise the following questions: (1) are there optimal schemes in which each file is partitioned into $F$ subfiles, where $F$ is not exponential, say polynomial for example, in $K$? (2) if the answer to this question is no, is there a near-optimal scheme, a scheme which is as asymptotically good as the one in \cite{ali1,yu}, with $F$ polynomial in $K$? Both these questions are open. Our main contribution in this paper is to provide answers to above questions. Firstly, we prove that under some mild restriction on user's cache rate, there are no optimal schemes with $F$ smaller than $F^*$. Moreover, we give necessary and sufficient conditions for the existence of optimal schemes in this case. Secondly, we provide an affirmative answer to the second question raised above by an explicit construction and a detailed performance analysis.
Polar-Slotted ALOHA over Slot Erasure Channels
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we design a new polar slotted ALOHA (PSA) protocol over the slot erasure channels, which uses polar coding to construct the identical slot pattern (SP) assembles within each active user and base station. A theoretical analysis framework for the PSA is provided. First, by using the packet-oriented operation for the overlap packets when they conflict in a slot interval, we introduce the packet-based polarization transform and prove that this transform is independent of the packet's length. Second, guided by the packet-based polarization, an SP assignment (SPA) method with the variable slot erasure probability (SEP) and a SPA method with a fixed SEP value are designed for the PSA scheme. Then, a packet-oriented successive cancellation (pSC) and a pSC list (pSCL) decoding algorithm are developed. Simultaneously, the finite-slots throughput bounds and the asymptotic throughput for the pSC algorithm are analyzed. The simulation results show that the proposed PSA scheme can achieve an improved throughput with the pSC/SCL decoding algorithm over the traditional repetition slotted ALOHA scheme.
Space Efficient Representations of Finite Groups
Venue: arXiv cs.DS 2020
Year: 2020

The Cayley table representation of a group uses $\mathcal{O}(n^2)$ words for a group of order $n$ and answers multiplication queries in time $\mathcal{O}(1)$. It is interesting to ask if there is a $o(n^2)$ space representation of groups that still has $\mathcal{O}(1)$ query-time. We show that for any $δ$, $\frac{1}{\log n} \le δ\le 1$, there is an $\mathcal{O}(\frac{n^{1 +δ}}δ)$ space representation for groups of order $n$ with $\mathcal{O}(\frac{1}δ)$ query-time. We also show that for Z-groups, simple groups and several group classes defined in terms of semidirect product, there are linear space representations with at most logarithmic query-time. Farzan and Munro (ISSAC'06) defined a model for group representation and gave a succinct data structure for abelian groups with constant query-time. They asked if their result can be extended to categorically larger group classes. We construct data structures in their model for Hamiltonian groups and some other classes of groups with constant query-time.
Towards Interpretable Semantic Segmentation via Gradient-weighted Class Activation Mapping
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks have become state-of-the-art in a wide range of image recognition tasks. The interpretation of their predictions, however, is an active area of research. Whereas various interpretation methods have been suggested for image classification, the interpretation of image segmentation still remains largely unexplored. To that end, we propose SEG-GRAD-CAM, a gradient-based method for interpreting semantic segmentation. Our method is an extension of the widely-used Grad-CAM method, applied locally to produce heatmaps showing the relevance of individual pixels for semantic segmentation.
CookGAN: Meal Image Synthesis from Ingredients
Venue: arXiv cs.CV 2020
Year: 2020

In this work we propose a new computational framework, based on generative deep models, for synthesis of photo-realistic food meal images from textual list of its ingredients. Previous works on synthesis of images from text typically rely on pre-trained text models to extract text features, followed by generative neural networks (GAN) aimed to generate realistic images conditioned on the text features. These works mainly focus on generating spatially compact and well-defined categories of objects, such as birds or flowers, but meal images are significantly more complex, consisting of multiple ingredients whose appearance and spatial qualities are further modified by cooking methods. To generate real-like meal images from ingredients, we propose Cook Generative Adversarial Networks (CookGAN), CookGAN first builds an attention-based ingredients-image association model, which is then used to condition a generative neural network tasked with synthesizing meal images. Furthermore, a cycle-consistent constraint is added to further improve image quality and control appearance. Experiments show our model is able to generate meal images corresponding to the ingredients.
Decidability of Sample Complexity of PAC Learning in finite setting
Venue: arXiv cs.LG 2020
Year: 2020

In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities (with no a priori bound). Unfortunately, the decision procedure is at present, at least doubly exponential in the number of points times the uniform bound on the support size.
Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
Venue: arXiv cs.SI 2020
Year: 2020

Network embedding methods map a network's nodes to vectors in an embedding space, in such a way that these representations are useful for estimating some notion of similarity or proximity between pairs of nodes in the network. The quality of these node representations is then showcased through results of downstream prediction tasks. Commonly used benchmark tasks such as link prediction, however, present complex evaluation pipelines and an abundance of design choices. This, together with a lack of standardized evaluation setups can obscure the real progress in the field. In this paper, we aim to shed light on the state-of-the-art of network embedding methods for link prediction and show, using a consistent evaluation pipeline, that only thin progress has been made over the last years. The newly conducted benchmark that we present here, including 17 embedding methods, also shows that many approaches are outperformed even by simple heuristics. Finally, we argue that standardized evaluation tools can repair this situation and boost future progress in this field.
Safe and Efficient Remote Application Code Execution on Disaggregated NVM Storage with eBPF
Venue: arXiv cs.DC 2020
Year: 2020

With rapid improvements in NVM storage devices, the performance bottleneck is gradually shifting to the network, thus giving rise to the notion of "data movement wall". To reduce the amount of data movement over the network, researchers have proposed near-data computing by shipping operations and compute-extensions closer to storage devices. However, running arbitrary, user-provided extensions in a shared, disaggregated storage environment presents multiple challenges regarding safety, isolation, and performance. Instead of approaching this problem from scratch, in this work we make a case for leveraging the Linux kernel eBPF framework to program disaggregated NVM storage devices. eBPF offers a safe, verifiable, and high-performance way of executing untrusted, user-defined code in a shared runtime. In this paper, we describe our experiences building a first prototype that supports remote operations on storage using eBPF, discuss the limitations of our approach, and directions for addressing them.
Synchronous Counter Design Using Novel Level Sensitive T-FF in QCA Technology
Venue: arXiv cs.ET 2020
Year: 2020

The quantum-dot cellular automata (QCA) nano-technique has attracted computer scientists due to its noticeable features such as low power consumption and small size. Many papers have been published in the literature about the utilization of this technology for de-signing many QCA circuits and for presenting logic gates in an optimal structure. The T flip-flop, which is an essential part of digital designs, can be used to design synchronous and asynchronous counters. This paper presents a novel T flip-flop structure in an optimal form. The presented novel gate was used to design an N-bit binary synchronous counter. The QCADesigner software was used to verify the designed circuits and to present the simulation results, while the QCAPro tool was used for the power analysis. The proposed design required minimal power and showed good improvements over previous designs.
An Optimal Control Model of Mouse Pointing Using the LQR
Venue: arXiv cs.HC 2020
Year: 2020

In this paper we explore the Linear-Quadratic Regulator (LQR) to model movement of the mouse pointer. We propose a model in which users are assumed to behave optimally with respect to a certain cost function. Users try to minimize the distance of the mouse pointer to the target smoothly and with minimal effort, by simultaneously minimizing the jerk of the movement. We identify parameters of our model from a dataset of reciprocal pointing with the mouse. We compare our model to the classical minimum-jerk and second-order lag models on data from 12 users with a total of 7702 movements. Our results show that our approach explains the data significantly better than either of these previous models.
Better coverage, better outcomes? Mapping mobile network data to official statistics using satellite imagery and radio propagation modelling
Venue: arXiv cs.CY 2020
Year: 2020

Mobile sensing data has become a popular data source for geo-spatial analysis, however, mapping it accurately to other sources of information such as statistical data remains a challenge. Popular mapping approaches such as point allocation or voronoi tessellation provide only crude approximations of the mobile network coverage as they do not consider holes, overlaps and within-cell heterogeneity. More elaborate mapping schemes often require additional proprietary data operators are highly reluctant to share. In this paper, I use human settlement information extracted from publicly available satellite imagery in combination with stochastic radio propagation modelling techniques to account for that. I investigate in a simulation study and a real-world application on unemployment estimates in Senegal whether better coverage approximations lead to better outcome predictions. The good news is: it does not have to be complicated.
Revisiting compact RDF stores based on k2-trees
Venue: arXiv cs.DB 2020
Year: 2020

We present a new compact representation to efficiently store and query large RDF datasets in main memory. Our proposal, called BMatrix, is based on the k2-tree, a data structure devised to represent binary matrices in a compressed way, and aims at improving the results of previous state-of-the-art alternatives, especially in datasets with a relatively large number of predicates. We introduce our technique, together with some improvements on the basic k2-tree that can be applied to our solution in order to boost compression. Experimental results in the flagship RDF dataset DBPedia show that our proposal achieves better compression than existing alternatives, while yielding competitive query times, particularly in the most frequent triple patterns and in queries with unbound predicate, in which we outperform existing solutions.
Facebook Ads as a Demographic Tool to Measure the Urban-Rural Divide
Venue: arXiv cs.CY 2020
Year: 2020

In the global move toward urbanization, making sure the people remaining in rural areas are not left behind in terms of development and policy considerations is a priority for governments worldwide. However, it is increasingly challenging to track important statistics concerning this sparse, geographically dispersed population, resulting in a lack of reliable, up-to-date data. In this study, we examine the usefulness of the Facebook Advertising platform, which offers a digital "census" of over two billions of its users, in measuring potential rural-urban inequalities. We focus on Italy, a country where about 30% of the population lives in rural areas. First, we show that the population statistics that Facebook produces suffer from instability across time and incomplete coverage of sparsely populated municipalities. To overcome such limitation, we propose an alternative methodology for estimating Facebook Ads audiences that nearly triples the coverage of the rural municipalities from 19% to 55% and makes feasible fine-grained sub-population analysis. Using official national census data, we evaluate our approach and confirm known significant urban-rural divides in terms of educational attainment and income. Extending the analysis to Facebook-specific user "interests" and behaviors, we provide further insights on the divide, for instance, finding that rural areas show a higher interest in gambling. Notably, we find that the most predictive features of income in rural areas differ from those for urban centres, suggesting researchers need to consider a broader range of attributes when examining rural wellbeing. The findings of this study illustrate the necessity of improving existing tools and methodologies to include under-represented populations in digital demographic studies -- the failure to do so could result in misleading observations, conclusions, and most importantly, policies.
Inceptive Event Time-Surfaces for Object Classification Using Neuromorphic Cameras
Venue: arXiv cs.NE 2020
Year: 2020

This paper presents a novel fusion of low-level approaches for dimensionality reduction into an effective approach for high-level objects in neuromorphic camera data called Inceptive Event Time-Surfaces (IETS). IETSs overcome several limitations of conventional time-surfaces by increasing robustness to noise, promoting spatial consistency, and improving the temporal localization of (moving) edges. Combining IETS with transfer learning improves state-of-the-art performance on the challenging problem of object classification utilizing event camera data.
Bitvectors with runs and the successor/predecessor problem
Venue: arXiv cs.DS 2020
Year: 2020

The successor and predecessor problem consists of obtaining the closest value in a set of integers, greater/smaller than a given value. This problem has interesting applications, like the intersection of inverted lists. It can be easily modeled by using a bitvector of size $n$ and its operations rank and select. However, there is a practical approach, which keeps the best theoretical bounds, and allows to solve successor and predecessor more efficiently. Based on that technique, we designed a novel compact data structure for bitvectors with $k$ runs that achieves access, rank, and successor/predecessor in $O(1)$ time by consuming space $O(\sqrt{kn})$ bits. In practice, it obtains a compression ratio of $0.04\%-26.33\%$ when the runs are larger than $100$, and becomes the fastest technique, which considers compressibility, in successor/predecessor queries. Besides, we present a recursive variant of our structure, which tends to $O(k)$ bits and takes $O(\log \frac{n}{k})$ time.
FedCoin: A Peer-to-Peer Payment System for Federated Learning
Venue: arXiv cs.CR 2020
Year: 2020

Federated learning (FL) is an emerging collaborative machine learning method to train models on distributed datasets with privacy concerns. To properly incentivize data owners to contribute their efforts, Shapley Value (SV) is often adopted to fairly assess their contribution. However, the calculation of SV is time-consuming and computationally costly. In this paper, we propose FedCoin, a blockchain-based peer-to-peer payment system for FL to enable a feasible SV based profit distribution. In FedCoin, blockchain consensus entities calculate SVs and a new block is created based on the proof of Shapley (PoSap) protocol. It is in contrast to the popular BitCoin network where consensus entities "mine" new blocks by solving meaningless puzzles. Based on the computed SVs, a scheme for dividing the incentive payoffs among FL clients with nonrepudiation and tamper-resistance properties is proposed. Experimental results based on real-world data show that FedCoin can promote high-quality data from FL clients through accurately computing SVs with an upper bound on the computational resources required for reaching consensus. It opens opportunities for non-data owners to play a role in FL.
Distributed Cross-Blockchain Transactions
Venue: arXiv cs.DB 2020
Year: 2020

The interoperability across multiple or many blockchains would play a critical role in the forthcoming blockchain-based data management paradigm. In particular, how to ensure the ACID properties of those transactions across an arbitrary number of blockchains remains an open problem in both academic and industry: Existing solutions either work for only two blockchains or requires a centralized component, neither of which would meet the scalability requirement in practice. This short paper shares our vision and some early results toward scalable cross-blockchain transactions. Specifically, we design two distributed commit protocols and, both analytically and experimentally, demonstrate their effectiveness.