OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Matrix Factorization on Heterogeneous CPU-GPU Systems
Venue: arXiv cs.DC 2020
Year: 2020

Matrix Factorization (MF) has been widely applied in machine learning and data mining. A large number of algorithms have been studied to factorize matrices. Among them, stochastic gradient descent (SGD) is a commonly used method. Heterogeneous systems with multi-core CPUs and GPUs have become more and more promising recently due to the prevalence of GPUs in general-purpose data-parallel applications. Due to the large computational cost of MF, we aim to improve the efficiency of SGD-based MF computation by utilizing the massive parallel processing power of heterogeneous multiprocessors. The main challenge in parallel SGD algorithms on heterogeneous CPU-GPU systems lies in the granularity of the matrix division and the strategy to assign tasks. We design a novel strategy to divide the matrix into a set of blocks by considering two aspects. First, we observe that the matrix should be divided nonuniformly, and relatively large blocks should be assigned to GPUs to saturate the computing power of GPUs. In addition to exploiting the characteristics of hardware, the workloads assigned to two types of hardware should be balanced. Aiming at the final division strategy, we design a cost model tailored for our problem to accurately estimate the performance of hardware on different data sizes. A dynamic scheduling policy is also used to further balance workloads in practice. Extensive experiments show that our proposed algorithm achieves high efficiency with a high quality of training quality.
Concept and the implementation of a tool to convert industry 4.0 environments modeled as FSM to an OpenAI Gym wrapper
Venue: arXiv cs.LG 2020
Year: 2020

Industry 4.0 systems have a high demand for optimization in their tasks, whether to minimize cost, maximize production, or even synchronize their actuators to finish or speed up the manufacture of a product. Those challenges make industrial environments a suitable scenario to apply all modern reinforcement learning (RL) concepts. The main difficulty, however, is the lack of that industrial environments. In this way, this work presents the concept and the implementation of a tool that allows us to convert any dynamic system modeled as an FSM to the open-source Gym wrapper. After that, it is possible to employ any RL methods to optimize any desired task. In the first tests of the proposed tool, we show traditional Q-learning and Deep Q-learning methods running over two simple environments.
Passive Wi-Fi Monitoring in Public Transport: A case study in the Madeira Island
Venue: arXiv cs.CY 2020
Year: 2020

Transportation has become of evermore importance in the last years, affecting people's satisfaction and significantly impacting their quality of life. In this paper we present a low-cost infrastructure to collect passive Wi-Fi probes with the aim of monitoring, optimizing and personalizing public transport, towards a more sustainable mobility. We developed an embedded system deployed in 19 public transportation vehicles using passive Wi-Fi data. This data is analyzed on a per-vehicle and per-stop basis and compared against ground truth data (ticketing), while also using a method of estimating passenger exits, detecting peak loads on vehicles, and origin destination habits. As such, we argue that this data enables route optimization and provides local authorities and tourism boards with a tool to monitor and optimize the management of routes and transportation, identify and prevent accessibility issues, with the aim of improving the services offered to citizens and tourists, towards a more sustainable mobility.
Iris Recognition: Inherent Binomial Degrees of Freedom
Venue: arXiv cs.CV 2020
Year: 2020

The distinctiveness of the human iris has been measured by first extracting a set of features from the iris, an encoding, and then comparing these encoded feature sets to determine how distinct they are from one another. For example, John Daugman measures the distinctiveness of the human iris at 244 degrees of freedom, that is, Daugman's encoding maps irises into the equivalent of 2 ^ 244 distinct possibilities [2]. This paper shows by direct pixel-by-pixel comparison of high-quality iris images that the inherent number of degrees of freedom embodied in the human iris, independent of any encoding, is at least 536. When the resolution of these images is gradually reduced, the number of degrees of freedom decreases smoothly to 123 for the lowest resolution images tested.
Predicting Length of Stay in the Intensive Care Unit with Temporal Pointwise Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

The pressure of ever-increasing patient demand and budget restrictions make hospital bed management a daily challenge for clinical staff. Most critical is the efficient allocation of resource-heavy Intensive Care Unit (ICU) beds to the patients who need life support. Central to solving this problem is knowing for how long the current set of ICU patients are likely to stay in the unit. In this work, we propose a new deep learning model based on the combination of temporal convolution and pointwise (1x1) convolution, to solve the length of stay prediction task on the eICU critical care dataset. The model - which we refer to as Temporal Pointwise Convolution (TPC) - is specifically designed to mitigate for common challenges with Electronic Health Records, such as skewness, irregular sampling and missing data. In doing so, we have achieved significant performance benefits of 18-51% (metric dependent) over the commonly used Long-Short Term Memory (LSTM) network, and the multi-head self-attention network known as the Transformer.
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Venue: arXiv cs.DS 2020
Year: 2020

Let $G = (V, E)$ be an undirected graph and let $B \subseteq V \times V$ be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of $G$ whose removal destroys all the paths between every terminal pair in $B$. The problem of computing a {\em minimum} node/edge multicut is NP-hard and extensively studied from several viewpoints. In this paper, we study the problem of enumerating all {\em minimal} node multicuts. We give an incremental polynomial delay enumeration algorithm for minimal node multicuts, which extends an enumeration algorithm due to Khachiyan et al. (Algorithmica, 2008) for minimal edge multicuts. Important special cases of node/edge multicuts are node/edge {\em multiway cuts}, where the set of terminal pairs contains every pair of vertices in some subset $T \subseteq V$, that is, $B = T \times T$. We improve the running time bound for this special case: We devise a polynomial delay and exponential space enumeration algorithm for minimal node multiway cuts and a polynomial delay and space enumeration algorithm for minimal edge multiway cuts.
Optimization Landscape of Tucker Decomposition
Venue: arXiv cs.LG 2020
Year: 2020

Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconvex objective of Tucker decomposition, all local minima are also globally optimal. We also give a local search algorithm that can find an approximate local (and global) optimal solution in polynomial time.
Asymmetric metric learning for knowledge transfer
Venue: arXiv cs.CV 2020
Year: 2020

Knowledge transfer from large teacher models to smaller student models has recently been studied for metric learning, focusing on fine-grained classification. In this work, focusing on instance-level image retrieval, we study an asymmetric testing task, where the database is represented by the teacher and queries by the student. Inspired by this task, we introduce asymmetric metric learning, a novel paradigm of using asymmetric representations at training. This acts as a simple combination of knowledge transfer with the original metric learning task. We systematically evaluate different teacher and student models, metric learning and knowledge transfer loss functions on the new asymmetric testing as well as the standard symmetric testing task, where database and queries are represented by the same model. We find that plain regression is surprisingly effective compared to more complex knowledge transfer mechanisms, working best in asymmetric testing. Interestingly, our asymmetric metric learning approach works best in symmetric testing, allowing the student to even outperform the teacher.
Probabilistic Bounds on the End-to-End Delay of Service Function Chains using Deep MDN
Venue: arXiv cs.PF 2020
Year: 2020

Ensuring the conformance of a service system's end-to-end delay to service level agreement (SLA) constraints is a challenging task that requires statistical measures beyond the average delay. In this paper, we study the real-time prediction of the end-to-end delay distribution in systems with composite services such as service function chains. In order to have a general framework, we use queueing theory to model service systems, while also adopting a statistical learning approach to avoid the limitations of queueing-theoretic methods such as stationarity assumptions or other approximations that are often used to make the analysis mathematically tractable. Specifically, we use deep mixture density networks (MDN) to predict the end-to-end distribution of the delay given the network's state. As a result, our method is sufficiently general to be applied in different contexts and applications. Our evaluations show a good match between the learned distributions and the simulations, which suggest that the proposed method is a good candidate for providing probabilistic bounds on the end-to-end delay of more complex systems where simulations or theoretical methods are not applicable.
Quantifying Susceptibility to Spear Phishing in a High School Environment Using Signal Detection Theory
Venue: arXiv cs.CR 2020
Year: 2020

Spear phishing is a deceptive attack that uses social engineering to obtain confidential information through targeted victimization. It is distinguished by its use of social cues and personalized information to target specific victims. Previous work on resilience to spear phishing has focused on convenience samples, with a disproportionate focus on students. In contrast, here, we report on an evaluation of a high school community. We engaged 57 high school students and faculty members (12 high school students, 45 staff members) as participants in research utilizing signal detection theory (SDT). Through scenario-based analysis, participants tasked with distinguishing phishing emails from authentic emails. The results revealed an overconfidence bias in self-detection from the participants, regardless of their technical background. These findings are critical for evaluating the decision-making of underrepresented populations and protecting people from potential spear phishing attacks by examining human susceptibility.
Vehicle Attribute Recognition by Appearance: Computer Vision Methods for Vehicle Type, Make and Model Classification
Venue: arXiv cs.CV 2020
Year: 2020

This paper studies vehicle attribute recognition by appearance. In the literature, image-based target recognition has been extensively investigated in many use cases, such as facial recognition, but less so in the field of vehicle attribute recognition. We survey a number of algorithms that identify vehicle properties ranging from coarse-grained level (vehicle type) to fine-grained level (vehicle make and model). Moreover, we discuss two alternative approaches for these tasks, including straightforward classification and a more flexible metric learning method. Furthermore, we design a simulated real-world scenario for vehicle attribute recognition and present an experimental comparison of the two approaches.
Multi-sensory Integration in a Quantum-Like Robot Perception Model
Venue: arXiv cs.RO 2020
Year: 2020

Formalisms inspired by Quantum theory have been used in Cognitive Science for decades. Indeed, Quantum-Like (QL) approaches provide descriptive features that are inherently suitable for perception, cognition, and decision processing. A preliminary study on the feasibility of a QL robot perception model has been carried out for a robot with limited sensing capabilities. In this paper, we generalize such a model for multi-sensory inputs, creating a multidimensional world representation directly based on sensor readings. Given a 3-dimensional case study, we highlight how this model provides a compact and elegant representation, embodying features that are extremely useful for modeling uncertainty and decision. Moreover, the model enables to naturally define query operators to inspect any world state, which answers quantifies the robot's degree of belief on that state.
Making Streett Determinization Tight
Venue: arXiv cs.FL 2020
Year: 2020

Optimal determinization construction of Streett automata is an important research problem because it is indispensable in numerous applications such as decision problems for tree temporal logics, logic games and system synthesis. This paper presents a transformation from nondeterministic Streett automata (NSA) with $n$ states and $k$ Streett pairs to equivalent deterministic Rabin transition automata (DRTA) with $n^{5n}(n!)^{n}$ states, $O(n^{n^2})$ Rabin pairs for $k=ω(n)$ and $n^{5n}k^{nk}$ states, $O(k^{nk})$ Rabin pairs for $k=O(n)$. This improves the state of the art Streett determinization construction with $n^{5n}(n!)^{n+1}$ states, $O(n^2)$ Rabin pairs and $n^{5n}k^{nk}n!$ states, $O(nk)$ Rabin pairs, respectively. Moreover, deterministic parity transition automata (DPTA) are obtained with $3(n(n+1)-1)!(n!)^{n+1}$ states, $2n(n+1)$ priorities for $k=ω(n)$ and $3(n(k+1)-1)!n!k^{nk}$ states, $2n(k+1)$ priorities for $k=O(n)$, which improves the best construction with $n^{n}(k+1)^{n(k+1)}(n(k+1)-1)!$ states, $2n(k+1)$ priorities. Further, we prove a lower bound state complexity for determinization construction from NSA to deterministic Rabin (transition) automata i.e. $n^{5n}(n!)^{n}$ for $k=ω(n)$ and $n^{5n}k^{nk}$ for $k=O(n)$, which matches the state complexity of the proposed determinization construction. Besides, we put forward a lower bound state complexity for determinization construction from NSA to deterministic parity (transition) automata i.e. $2^{Ω(n^2 \log n)}$ for $k=ω(n)$ and $2^{Ω(nk \log nk)}$ for $k=O(n)$, which is the same as the state complexity of the proposed determinization construction in the exponent.
MSNet: A Multilevel Instance Segmentation Network for Natural Disaster Damage Assessment in Aerial Videos
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we study the problem of efficiently assessing building damage after natural disasters like hurricanes, floods or fires, through aerial video analysis. We make two main contributions. The first contribution is a new dataset, consisting of user-generated aerial videos from social media with annotations of instance-level building damage masks. This provides the first benchmark for quantitative evaluation of models to assess building damage using aerial videos. The second contribution is a new model, namely MSNet, which contains novel region proposal network designs and an unsupervised score refinement network for confidence score calibration in both bounding box and mask branches. We show that our model achieves state-of-the-art results compared to previous methods in our dataset. We will release our data, models and code.
Policy Gradient Optimization of Thompson Sampling Policies
Venue: arXiv cs.LG 2020
Year: 2020

We study the use of policy gradient algorithms to optimize over a class of generalized Thompson sampling policies. Our central insight is to view the posterior parameter sampled by Thompson sampling as a kind of pseudo-action. Policy gradient methods can then be tractably applied to search over a class of sampling policies, which determine a probability distribution over pseudo-actions (i.e., sampled parameters) as a function of observed data. We also propose and compare policy gradient estimators that are specialized to Bayesian bandit problems. Numerical experiments demonstrate that direct policy search on top of Thompson sampling automatically corrects for some of the algorithm's known shortcomings and offers meaningful improvements even in long horizon problems where standard Thompson sampling is extremely effective.
Algorithms and complexity for geodetic sets on planar and chordal graphs
Venue: arXiv cs.DM 2020
Year: 2020

We study the complexity of finding the \emph{geodetic number} on subclasses of planar graphs and chordal graphs. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study \textsc{MGS} on restricted classes of planar graphs: we design a linear-time algorithm for \textsc{MGS} on solid grids, improving on a $3$-approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that it remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that \textsc{MGS} is fixed parameter tractable for inputs of this class when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \textsc{MGS} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.
Forced-exploration free Strategies for Unimodal Bandits
Venue: arXiv cs.LG 2020
Year: 2020

We consider a multi-armed bandit problem specified by a set of Gaussian or Bernoulli distributions endowed with a unimodal structure. Although this problem has been addressed in the literature (Combes and Proutiere, 2014), the state-of-the-art algorithms for such structure make appear a forced-exploration mechanism. We introduce IMED-UB, the first forced-exploration free strategy that exploits the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) strategy introduced by Honda and Takemura (2015). This strategy is proven optimal. We then derive KLUCB-UB, a KLUCB version of IMED-UB, which is also proven optimal. Owing to our proof technique, we are further able to provide a concise finite-time analysis of both strategies in an unified way. Numerical experiments show that both IMED-UB and KLUCB-UB perform similarly in practice and outperform the state-of-the-art algorithms.
A Simple Domain Shifting Networkfor Generating Low Quality Images
Venue: arXiv cs.CV 2020
Year: 2020

Deep Learning systems have proven to be extremely successful for image recognition tasks for which significant amounts of training data is available, e.g., on the famous ImageNet dataset. We demonstrate that for robotics applications with cheap camera equipment, the low image quality, however,influences the classification accuracy, and freely available databases cannot be exploited in a straight forward way to train classifiers to be used on a robot. As a solution we propose to train a network on degrading the quality images in order to mimic specific low quality imaging systems. Numerical experiments demonstrate that classification networks trained by using images produced by our quality degrading network along with the high quality images outperform classification networks trained only on high quality data when used on a real robot system, while being significantly easier to use than competing zero-shot domain adaptation techniques.
Bitcoin Covenants: Three Ways to Control the Future
Venue: arXiv cs.CR 2020
Year: 2020

A bitcoin covenant is a mechanism to enforce conditions on how the control of coins will be transferred in the future. This work introduces deleted-key covenants; using pre-signed transactions with secure key deletion. With this, a general class of covenants are possible without introducing new security risks to bitcoin. There is a range of security models for the key deletion process, but this is subject to a security-convenience trade-off and requires interactivity in a multi-party context. On the other hand, this work makes a compelling case for what can be gained through a soft-fork upgrade to the signature hash system [Dec17] which enables recovered-key covenants through elliptic curve key recovery. This has similar properties to script-based covenant mechanisms proposed previously [Rub20]. Key factors are discussed and compared for the three covenant mechanisms, including; the enforcement process, methods for proving accessibility of funds and whether or not they are bound by a covenant, methods for dynamic fee allocation, the underlying cryptographic assumptions, and their feasibility in single-party, hierarchical and adversarial multi-party contexts. Despite the relative downsides of deleted-key covenants, they are a practical tool for custody protocol design. The comparison shows precisely how soft-fork proposals improve the practicality of bitcoin covenants, through non-interactive enforcement and tighter cryptographic assumptions, to enhance custody protocols and enable some adversarial applications such as payment protocols.
Online Multi-Facility Location
Venue: arXiv cs.DS 2020
Year: 2020

Facility Location problems ask to place facilities in a way that optimizes a given objective function so as to provide a service to all clients. These are one of the most well-studied optimization problems spanning many research areas such as operations research, computer science, and management science. Traditionally, these problems are solved with the assumption that clients need to be served by one facility each. In many real-world scenarios, it is very likely that clients need a robust service that requires more than one facility for each client. In this paper, we capture this robustness by exploring a generalization of Facility Location problems, called Multi-Facility Location problems, in the online setting. An additional parameter k, which represents the number of facilities required to serve a client, is given. We propose the first online algorithms for the metric and non-metric variants of Multi-Facility Location and measure their performance with competitive analysis, the standard to measure online algorithms, in the worst case, in which the cost of the online algorithm is compared to that of the optimal offline algorithm that knows the entire input sequence in advance.