OpenRaiser/Intern-Atlas huggingface dataset:
Post-Earthquake Assessment of Buildings Using Deep Learning
Venue: arXiv cs.CV 2019
Year: 2019

Classification of the extent of damage suffered by a building in a seismic event is crucial from the safety perspective and repairing work. In this study, authors have proposed a CNN based autonomous damage detection model. Over 1200 images of different types of buildings-1000 for training and 200 for testing classified into 4 categories according to the extent of damage suffered. Categories are namely, no damage, minor damage, major damage, and collapse. Trained network tested by the application of various algorithms with different learning rates. The most optimum results were obtained on the application of VGG16 transfer learning model with a learning rate of 1e-5 as it gave a training accuracy of 97.85% and validation accuracy of up to 89.38%. The model developed has real-time application in the event of an earthquake.
On the relation between Loss Functions and T-Norms
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning has been shown to achieve impressive results in several domains like computer vision and natural language processing. A key element of this success has been the development of new loss functions, like the popular cross-entropy loss, which has been shown to provide faster convergence and to reduce the vanishing gradient problem in very deep structures. While the cross-entropy loss is usually justified from a probabilistic perspective, this paper shows an alternative and more direct interpretation of this loss in terms of t-norms and their associated generator functions, and derives a general relation between loss functions and t-norms. In particular, the presented work shows intriguing results leading to the development of a novel class of loss functions. These losses can be exploited in any supervised learning task and which could lead to faster convergence rates that the commonly employed cross-entropy loss.
Locality-constrained Spatial Transformer Network for Video Crowd Counting
Venue: arXiv cs.CV 2019
Year: 2019

Compared with single image based crowd counting, video provides the spatial-temporal information of the crowd that would help improve the robustness of crowd counting. But translation, rotation and scaling of people lead to the change of density map of heads between neighbouring frames. Meanwhile, people walking in/out or being occluded in dynamic scenes leads to the change of head counts. To alleviate these issues in video crowd counting, a Locality-constrained Spatial Transformer Network (LSTN) is proposed. Specifically, we first leverage a Convolutional Neural Networks to estimate the density map for each frame. Then to relate the density maps between neighbouring frames, a Locality-constrained Spatial Transformer (LST) module is introduced to estimate the density map of next frame with that of current frame. To facilitate the performance evaluation, a large-scale video crowd counting dataset is collected, which contains 15K frames with about 394K annotated heads captured from 13 different scenes. As far as we know, it is the largest video crowd counting dataset. Extensive experiments on our dataset and other crowd counting datasets validate the effectiveness of our LSTN for crowd counting.
Transfer Learning Across Simulated Robots With Different Sensors
Venue: arXiv cs.AI 2019
Year: 2019

For a robot to learn a good policy, it often requires expensive equipment (such as sophisticated sensors) and a prepared training environment conducive to learning. However, it is seldom possible to perfectly equip robots for economic reasons, nor to guarantee ideal learning conditions, when deployed in real-life environments. A solution would be to prepare the robot in the lab environment, when all necessary material is available to learn a good policy. After training in the lab, the robot should be able to get by without the expensive equipment that used to be available to it, and yet still be guaranteed to perform well on the field. The transition between the lab (source) and the real-world environment (target) is related to transfer learning, where the state-space between the source and target tasks differ. We tackle a simulated task with continuous states and discrete actions presenting this challenge, using Bootstrapped Dual Policy Iteration, a model-free actor-critic reinforcement learning algorithm, and Policy Shaping. Specifically, we train a BDPI agent, embodied by a virtual robot performing a task in the V-Rep simulator, sensing its environment through several proximity sensors. The resulting policy is then used by a second agent learning the same task in the same environment, but with camera images as input. The goal is to obtain a policy able to perform the task relying on merely camera images.
Sensitive Distance and Reachability Oracles for Large Batch Updates
Venue: arXiv cs.DS 2019
Year: 2019

In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph $G$ with $n$ nodes and integer weights from $[-W,W]$. Second, given a single batch of $f$ edge insertions and deletions, we update the data structure. Third, given a query pair of nodes $(u,v)$, return the distance from $u$ to $v$. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from $u$ to $v$. Our first result is a sensitive distance oracle with $\tilde{O}(Wn^{ω+(3-ω)μ})$ preprocessing time, $\tilde{O}(Wn^{2-μ}f^{2}+Wnf^ω)$ update time, and $\tilde{O}(Wn^{2-μ}f+Wnf^{2})$ query time where the parameter $μ\in[0,1]$ can be chosen. The data-structure requires $O(Wn^{2+μ} \log n)$ bits of memory. This is the first algorithm that can handle $f\ge\log n$ updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'12]) can handle at most 2 updates. When $3\le f\le\log n$, the only non-trivial algorithm was by [Weimann and Yuster FOCS'10]. When $W=\tilde{O}(1)$, our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when $f=ω(1)$, their update and query time is $Ω(n^{2-o(1)})$, while our update and query time are truly subquadratic in $n$, i.e., ours is faster by a polynomial factor of $n$. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp'05; Zhou, Labahn and Storjohann J.Comp'15] developed in the symbolic computation community. [...]
Convolutional Reservoir Computing for World Models
Venue: arXiv cs.LG 2019
Year: 2019

Recently, reinforcement learning models have achieved great success, completing complex tasks such as mastering Go and other games with higher scores than human players. Many of these models collect considerable data on the tasks and improve accuracy by extracting visual and time-series features using convolutional neural networks (CNNs) and recurrent neural networks, respectively. However, these networks have very high computational costs because they need to be trained by repeatedly using a large volume of past playing data. In this study, we propose a novel practical approach called reinforcement learning with convolutional reservoir computing (RCRC) model. The RCRC model has several desirable features: 1. it can extract visual and time-series features very fast because it uses random fixed-weight CNN and the reservoir computing model; 2. it does not require the training data to be stored because it extracts features without training and decides action with evolution strategy. Furthermore, the model achieves state of the art score in the popular reinforcement learning task. Incredibly, we find the random weight-fixed simple networks like only one dense layer network can also reach high score in the RL task.
Graph-Based Encoders and their Performance for Finite-State Channels with Feedback
Venue: arXiv cs.IT 2019
Year: 2019

The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoders. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric Trapdoor channel and binary fading channels (BFCs), new capacity results are eastablished by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.
On Arrangements of Orthogonal Circles
Venue: arXiv cs.CG 2019
Year: 2019

In this paper, we study arrangements of orthogonal circles, that is, arrangements of circles where every pair of circles must either be disjoint or intersect at a right angle. Using geometric arguments, we show that such arrangements have only a linear number of faces. This implies that orthogonal circle intersection graphs have only a linear number of edges. When we restrict ourselves to orthogonal unit circles, the resulting class of intersection graphs is a subclass of penny graphs (that is, contact graphs of unit circles). We show that, similarly to penny graphs, it is NP-hard to recognize orthogonal unit circle intersection graphs.
ReconViguRation: Reconfiguring Physical Keyboards in Virtual Reality
Venue: arXiv cs.HC 2019
Year: 2019

Physical keyboards are common peripherals for personal computers and are efficient standard text entry devices. Recent research has investigated how physical keyboards can be used in immersive head-mounted display-based Virtual Reality (VR). So far, the physical layout of keyboards has typically been transplanted into VR for replicating typing experiences in a standard desktop environment. In this paper, we explore how to fully leverage the immersiveness of VR to change the input and output characteristics of physical keyboard interaction within a VR environment. This allows individual physical keys to be reconfigured to the same or different actions and visual output to be distributed in various ways across the VR representation of the keyboard. We explore a set of input and output mappings for reconfiguring the virtual presentation of physical keyboards and probe the resulting design space by specifically designing, implementing and evaluating nine VR-relevant applications: emojis, languages and special characters, application shortcuts, virtual text processing macros, a window manager, a photo browser, a whack-a-mole game, secure password entry and a virtual touch bar. We investigate the feasibility of the applications in a user study with 20 participants and find that, among other things, they are usable in VR. We discuss the limitations and possibilities of remapping the input and output characteristics of physical keyboards in VR based on empirical findings and analysis and suggest future research directions in this area.
Fragility of Layout-Based and Visual GUI Test Scripts: An Assessment Study on a Hybrid Mobile Application
Venue: arXiv cs.SE 2019
Year: 2019

Context: Albeit different approaches exist for automated GUI testing of hybrid mobile applications, the practice appears to be not so commonly adopted by developers. A possible reason for such a low diffusion can be the fragility of the techniques, i.e. the frequent need for maintaining test cases when the GUI of the app is changed. Goal: In this paper, we perform an assessment of the maintenance needed by test cases for a hybrid mobile app, and the related fragility causes. Methods: We evaluated a small test suite with a Layout-based testing tool (Appium) and a Visual one (EyeAutomate) and observed the changes needed by tests during the co-evolution with the GUI of the app. Results: We found that 20% Layout-based test methods and 30% Visual test methods had to be modified at least once, and that each release induced fragilities in 3-4% of the test methods. Conclusion: Fragility of GUI tests can induce relevant maintenance efforts in test suites of large applications. Several principal causes for fragilities have been identified for the tested hybrid application, and guidelines for developers are deduced from them.
Investigating Italian disinformation spreading on Twitter in the context of 2019 European elections
Venue: arXiv cs.SI 2019
Year: 2019

We investigate the presence (and the influence) of disinformation spreading on online social networks in Italy, in the5-month period preceding the 2019 European Parliament elections. To this aim we collected a large-scale dataset oftweets associated to thousands of news articles published on Italian disinformation websites. In the observation period,a few outlets accounted for most of the deceptive information circulating on Twitter, which focused on controversialand polarizing topics of debate such as immigration, national safety and (Italian) nationalism. We found evidence ofconnections between different disinformation outlets across Europe, U.S. and Russia, which often linked to each otherand featured similar, even translated, articles in the period before the elections. Overall, the spread of disinformation onTwitter was confined in a limited community, strongly (and explicitly) related to the Italian conservative and far-rightpolitical environment, who had a limited impact on online discussions on the up-coming elections.
Imperfect Gaps in Gap-ETH and PCPs
Venue: arXiv cs.CC 2019
Year: 2019

We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness when the initial gap is a constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq \text{PCP}_{1,1-Ω(1)}[r+O(1),q+O(r)]$, for $c-s=Ω(1)$. This implies that one can convert imperfect completeness to perfect in linear-sized PCPs for $NTIME[O(n)]$ with a $O(\log n)$ additive loss in the query complexity $q$. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs (when completeness is imperfect), analogous to questions studied in parallel repetition and pseudorandomness. We also investigate the time complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. we show that Gap-3SAT, where the gap is not around 1, has a subexponential algorithm, if and only if, Gap-3SAT with perfect completeness has subexponential algorithms. We also relate the time complexities of these two problems in a more fine-grained way, to show that $T_2(n) \leq T_1(n(\log\log n)^{O(1)})$, where $T_1(n),T_2(n)$ denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness, respectively.
Finding First and Most-Beautiful Queens by Integer Programming
Venue: arXiv cs.DS 2019
Year: 2019

The n-queens puzzle is a well-known combinatorial problem that requires to place n queens on an n x n chessboard so that no two queens can attack each other. Since the 19th century, this problem was studied by many mathematicians and computer scientists. While finding any solution to the n-queens puzzle is rather straightforward, it is very challenging to find the lexicographically first (or smallest) feasible solution. Solutions for this type are known in the literature for n <= 55, while for some larger chessboards only partial solutions are known. The present paper was motivated by the question of whether Integer Linear Programming (ILP) can be used to compute solutions for some open instances. We describe alternative ILP-based solution approaches, and show that they are indeed able to compute (sometimes in unexpectedly-short computing times) many new lexicographically optimal solutions for n ranging from 56 to 115. One of the proposed algorithms is a pure cutting plane method based on a combinatorial variant of classical Gomory cuts. We also address an intriguing "lexicographic bottleneck" (or min-max) variant of the problem that requires finding a most beautiful (in a well defined sense) placement, and report its solution for n up to 176.
Message passing on networks with loops
Venue: arXiv cs.SI 2019
Year: 2019

In this paper we offer a solution to a long-standing problem in the study of networks. Message passing is a fundamental technique for calculations on networks and graphs. The first versions of the method appeared in the 1930s and over the decades it has been applied to a wide range of foundational problems in mathematics, physics, computer science, statistics, and machine learning, including Bayesian inference, spin models, coloring, satisfiability, graph partitioning, network epidemiology, and the calculation of matrix eigenvalues. Despite its wide use, however, it has long been recognized that the method has a fundamental flaw: it only works on networks that are free of short loops. Loops introduce correlations that cause the method to give inaccurate answers at best, and to fail completely in the worst cases. Unfortunately, almost all real-world networks contain many short loops, which limits the usefulness of the message passing approach. In this paper we demonstrate how to rectify this shortcoming and create message passing methods that work on any network. We give two example applications, one to the percolation properties of networks and the other to the calculation of the spectra of sparse matrices.
Toxicity Prediction by Multimodal Deep Learning
Venue: arXiv cs.LG 2019
Year: 2019

Prediction of toxicity levels of chemical compounds is an important issue in Quantitative Structure-Activity Relationship (QSAR) modeling. Although toxicity prediction has achieved significant progress in recent times through deep learning, prediction accuracy levels obtained by even very recent methods are not yet very high. We propose a multimodal deep learning method using multiple heterogeneous neural network types and data representations. We represent chemical compounds by strings, images, and numerical features. We train fully connected, convolutional, and recurrent neural networks and their ensembles. Each data representation or neural network type has its own strengths and weaknesses. Our motivation is to obtain a collective performance that could go beyond individual performance of each data representation or each neural network type. On a standard toxicity benchmark, our proposed method obtains significantly better accuracy levels than that by the state-of-the-art toxicity prediction methods.
Only Time Can Tell: Discovering Temporal Data for Temporal Modeling
Venue: arXiv cs.CV 2019
Year: 2019

Understanding temporal information and how the visual world changes over time is a fundamental ability of intelligent systems. In video understanding, temporal information is at the core of many current challenges, including compression, efficient inference, motion estimation or summarization. However, in current video datasets it has been observed that action classes can often be recognized without any temporal information from a single frame of video. As a result, both benchmarking and training in these datasets may give an unintentional advantage to models with strong image understanding capabilities, as opposed to those with strong temporal understanding. In this paper we address this problem head on by identifying action classes where temporal information is actually necessary to recognize them and call these "temporal classes". Selecting temporal classes using a computational method would bias the process. Instead, we propose a methodology based on a simple and effective human annotation experiment. We remove just the temporal information by shuffling frames in time and measure if the action can still be recognized. Classes that cannot be recognized when frames are not in order are included in the temporal Dataset. We observe that this set is statistically different from other static classes, and that performance in it correlates with a network's ability to capture temporal information. Thus we use it as a benchmark on current popular networks, which reveals a series of interesting facts. We also explore the effect of training on the temporal dataset, and observe that this leads to better generalization in unseen classes, demonstrating the need for more temporal data. We hope that the proposed dataset of temporal categories will help guide future research in temporal modeling for better video understanding.
Sparse Recovery for Orthogonal Polynomial Transforms
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we consider the following sparse recovery problem. We have query access to a vector $\vx \in \R^N$ such that $\vhx = \vF \vx$ is $k$-sparse (or nearly $k$-sparse) for some orthogonal transform $\vF$. The goal is to output an approximation (in an $\ell_2$ sense) to $\vhx$ in sublinear time. This problem has been well-studied in the special case that $\vF$ is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time $O(k \cdot \mathrm{polylog} N)$. However, for transforms $\vF$ other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms---running in time $\poly(k \log(N))$---for solving the sparse recovery problem for orthogonal transforms $\vF$ that arise from orthogonal polynomials. More precisely, our algorithm works for any $\vF$ that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the $k$-sparse sparse recovery problem to the $1$-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials.
Automated Machine Learning in Practice: State of the Art and Recent Results
Venue: arXiv cs.LG 2019
Year: 2019

A main driver behind the digitization of industry and society is the belief that data-driven model building and decision making can contribute to higher degrees of automation and more informed decisions. Building such models from data often involves the application of some form of machine learning. Thus, there is an ever growing demand in work force with the necessary skill set to do so. This demand has given rise to a new research topic concerned with fitting machine learning models fully automatically - AutoML. This paper gives an overview of the state of the art in AutoML with a focus on practical applicability in a business context, and provides recent benchmark results on the most important AutoML algorithms.