OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Deep Features for Remote Sensing Image Retrieval: A Systematic Investigation
Venue: arXiv cs.CV 2019
Year: 2019

Remote sensing (RS) image retrieval is of great significant for geological information mining. Over the past two decades, a large amount of research on this task has been carried out, which mainly focuses on the following three core issues: feature extraction, similarity metric and relevance feedback. Due to the complexity and multiformity of ground objects in high-resolution remote sensing (HRRS) images, there is still room for improvement in the current retrieval approaches. In this paper, we analyze the three core issues of RS image retrieval and provide a comprehensive review on existing methods. Furthermore, for the goal to advance the state-of-the-art in HRRS image retrieval, we focus on the feature extraction issue and delve how to use powerful deep representations to address this task. We conduct systematic investigation on evaluating correlative factors that may affect the performance of deep features. By optimizing each factor, we acquire remarkable retrieval results on publicly available HRRS datasets. Finally, we explain the experimental phenomenon in detail and draw conclusions according to our analysis. Our work can serve as a guiding role for the research of content-based RS image retrieval.
Engineering fast multilevel support vector machines
Venue: arXiv cs.LG 2019
Year: 2019

The computational complexity of solving nonlinear support vector machine (SVM) is prohibitive on large-scale data. In particular, this issue becomes very sensitive when the data represents additional difficulties such as highly imbalanced class sizes. Typically, nonlinear kernels produce significantly higher classification quality to linear kernels but introduce extra kernel and model parameters which requires computationally expensive fitting. This increases the quality but also reduces the performance dramatically. We introduce a generalized fast multilevel framework for regular and weighted SVM and discuss several versions of its algorithmic components that lead to a good trade-off between quality and time. Our framework is implemented using PETSc which allows an easy integration with scientific computing tasks. The experimental results demonstrate significant speed up compared to the state-of-the-art nonlinear SVM libraries. Reproducibility: our source code, documentation and parameters are available at https:// github.com/esadr/mlsvm.
Comparative Analysis and Framework Evaluating Mimicry-Resistant and Invisible Web Authentication Schemes
Venue: arXiv cs.CR 2019
Year: 2019

Many password alternatives for web authentication proposed over the years, despite having different designs and objectives, all predominantly rely on the knowledge of some secret. This motivates us, herein, to provide the first detailed exploration of the integration of a fundamentally different element of defense into the design of web authentication schemes: a mimicry-resistance dimension. We analyze web authentication mechanisms with respect to new usability and security properties related to mimicry-resistance (augmenting the UDS framework), and in particular evaluate invisible techniques (those requiring neither user actions, nor awareness) that provide some mimicry-resistance (unlike those relying solely on static secrets), including device fingerprinting schemes, PUFs (physically unclonable functions), and a subset of Internet geolocation mechanisms.
Efficient Contextual Bandits in Non-stationary Worlds
Venue: arXiv cs.LG 2019
Year: 2019

Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. problems with sophisticated statistical tests so as to dynamically adapt to a change in distribution. We analyze various standard notions of regret suited to non-stationary environments for these algorithms, including interval regret, switching regret, and dynamic regret. When competing with the best policy at each time, one of our algorithms achieves regret $\mathcal{O}(\sqrt{ST})$ if there are $T$ rounds with $S$ stationary periods, or more generally $\mathcal{O}(Δ^{1/3}T^{2/3})$ where $Δ$ is some non-stationarity measure. These results almost match the optimal guarantees achieved by an inefficient baseline that is a variant of the classic Exp4 algorithm. The dynamic regret result is also the first one for efficient and fully adversarial contextual bandit. Furthermore, while the results above require tuning a parameter based on the unknown quantity $S$ or $Δ$, we also develop a parameter free algorithm achieving regret $\min\{S^{1/4}T^{3/4}, Δ^{1/5}T^{4/5}\}$. This improves and generalizes the best existing result $Δ^{0.18}T^{0.82}$ by Karnin and Anava (2016) which only holds for the two-armed bandit problem.
Simple Analysis of Sparse, Sign-Consistent JL
Venue: arXiv cs.DS 2019
Year: 2019

Allen-Zhu, Gelashvili, Micali, and Shavit construct a sparse, sign-consistent Johnson-Lindenstrauss distribution, and prove that this distribution yields an essentially optimal dimension for the correct choice of sparsity. However, their analysis of the upper bound on the dimension and sparsity requires a complicated combinatorial graph-based argument similar to Kane and Nelson's analysis of sparse JL. We present a simple, combinatorics-free analysis of sparse, sign-consistent JL that yields the same dimension and sparsity upper bounds as the original analysis. Our analysis also yields dimension/sparsity tradeoffs, which were not previously known. As with previous proofs in this area, our analysis is based on applying Markov's inequality to the pth moment of an error term that can be expressed as a quadratic form of Rademacher variables. Interestingly, we show that, unlike in previous work in the area, the traditionally used Hanson-Wright bound is not strong enough to yield our desired result. Indeed, although the Hanson-Wright bound is known to be optimal for gaussian degree-2 chaos, it was already shown to be suboptimal for Rademachers. Surprisingly, we are able to show a simple moment bound for quadratic forms of Rademachers that is sufficiently tight to achieve our desired result, which given the ubiquity of moment and tail bounds in theoretical computer science, is likely to be of broader interest.
Mining Deep And-Or Object Structures via Cost-Sensitive Question-Answer-Based Active Annotations
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a cost-sensitive active Question-Answering (QA) framework for learning a nine-layer And-Or graph (AOG) from web images. The AOG explicitly represents object categories, poses/viewpoints, parts, and detailed structures within the parts in a compositional hierarchy. The QA framework is designed to minimize an overall risk, which trades off the loss and query costs. The loss is defined for nodes in all layers of the AOG, including the generative loss (measuring the likelihood of the images) and the discriminative loss (measuring the fitness to human answers). The cost comprises both the human labor of answering questions and the computational cost of model learning. The cost-sensitive QA framework iteratively selects different storylines of questions to update different nodes in the AOG. Experiments showed that our method required much less human supervision (e.g., labeling parts on 3--10 training objects for each category) and achieved better performance than baseline methods.
Strategy Synthesis in POMDPs via Game-Based Abstractions
Venue: arXiv cs.RO 2019
Year: 2019

We study synthesis problems with constraints in partially observable Markov decision processes (POMDPs), where the objective is to compute a strategy for an agent that is guaranteed to satisfy certain safety and performance specifications. Verification and strategy synthesis for POMDPs are, however, computationally intractable in general. We alleviate this difficulty by focusing on planning applications and exploiting typical structural properties of such scenarios; for instance, we assume that the agent has the ability to observe its own position inside an environment. We propose an abstraction refinement framework which turns such a POMDP model into a (fully observable) probabilistic two-player game (PG). For the obtained PGs, efficient verification and synthesis tools allow to determine strategies with optimal safety and performance measures, which approximate optimal schedulers on the POMDP. If the approximation is too coarse to satisfy the given specifications, an refinement scheme improves the computed strategies. As a running example, we use planning problems where an agent moves inside an environment with randomly moving obstacles and restricted observability. We demonstrate that the proposed method advances the state of the art by solving problems several orders-of-magnitude larger than those that can be handled by existing POMDP solvers. Furthermore, this method gives guarantees on safety constraints, which is not supported by the majority of the existing solvers.
Secrecy Energy Efficiency of MIMOME Wiretap Channels with Full-Duplex Jamming
Venue: arXiv cs.IT 2019
Year: 2019

Full-duplex (FD) jamming transceivers are recently shown to enhance the information security of wireless communication systems by simultaneously transmitting artificial noise (AN) while receiving information. In this work, we investigate if FD jamming can also improve the systems secrecy energy efficiency (SEE) in terms of securely communicated bits-per- Joule, when considering the additional power used for jamming and self-interference (SI) cancellation. Moreover, the degrading effect of the residual SI is also taken into account. In this regard, we formulate a set of SEE maximization problems for a FD multiple-input-multiple-output multiple-antenna eavesdropper (MIMOME) wiretap channel, considering both cases where exact or statistical channel state information (CSI) is available. Due to the intractable problem structure, we propose iterative solutions in each case with a proven convergence to a stationary point. Numerical simulations indicate only a marginal SEE gain, through the utilization of FD jamming, for a wide range of system conditions. However, when SI can efficiently be mitigated, the observed gain is considerable for scenarios with a small distance between the FD node and the eavesdropper, a high Signal-to-noise ratio (SNR), or for a bidirectional FD communication setup.
Boltzmann machines and energy-based models
Venue: arXiv cs.NE 2019
Year: 2019

We review Boltzmann machines and energy-based models. A Boltzmann machine defines a probability distribution over binary-valued patterns. One can learn parameters of a Boltzmann machine via gradient based approaches in a way that log likelihood of data is increased. The gradient and Hessian of a Boltzmann machine admit beautiful mathematical representations, although computing them is in general intractable. This intractability motivates approximate methods, including Gibbs sampler and contrastive divergence, and tractable alternatives, namely energy-based models.
Eccentricity Effects on Blur and Depth Perception
Venue: arXiv cs.GR 2019
Year: 2019

Foveation and focus cue are the two most discussed topics on vision in designing near-eye displays. Foveation reduces rendering load by omitting spatial details in the content that the peripheral vision cannot appreciate; Providing richer focal cue can resolve vergence-accommodation conflict thereby lessening visual discomfort in using near-eye displays. We performed two psychophysical experiments to investigate the relationship between foveation and focus cue. The first study measured blur discrimination sensitivity as a function of visual eccentricity, where we found discrimination thresholds significantly lower than previously reported. The second study measured depth discrimination threshold where we found a clear dependency on visual eccentricity. We discuss the results from the two studies and suggest further investigation.
This Far, No Further: Introducing Virtual Borders to Mobile Robots Using a Laser Pointer
Venue: arXiv cs.RO 2019
Year: 2019

We address the problem of controlling the workspace of a 3-DoF mobile robot. In a human-robot shared space, robots should navigate in a human-acceptable way according to the users' demands. For this purpose, we employ virtual borders, that are non-physical borders, to allow a user the restriction of the robot's workspace. To this end, we propose an interaction method based on a laser pointer to intuitively define virtual borders. This interaction method uses a previously developed framework based on robot guidance to change the robot's navigational behavior. Furthermore, we extend this framework to increase the flexibility by considering different types of virtual borders, i.e. polygons and curves separating an area. We evaluated our method with 15 non-expert users concerning correctness, accuracy and teaching time. The experimental results revealed a high accuracy and linear teaching time with respect to the border length while correctly incorporating the borders into the robot's navigational map. Finally, our user study showed that non-expert users can employ our interaction method.
Divergence, Entropy, Information: An Opinionated Introduction to Information Theory
Venue: arXiv cs.IT 2019
Year: 2019

Information theory is a mathematical theory of learning with deep connections with topics as diverse as artificial intelligence, statistical physics, and biological evolution. Many primers on information theory paint a broad picture with relatively little mathematical sophistication, while many others develop specific application areas in detail. In contrast, these informal notes aim to outline some elements of the information-theoretic "way of thinking," by cutting a rapid and interesting path through some of the theory's foundational concepts and results. They are aimed at practicing systems scientists who are interested in exploring potential connections between information theory and their own fields. The main mathematical prerequisite for the notes is comfort with elementary probability, including sample spaces, conditioning, and expectations. We take the Kullback-Leibler divergence as our most basic concept, and then proceed to develop the entropy and mutual information. We discuss some of the main results, including the Chernoff bounds as a characterization of the divergence; Gibbs' Theorem; and the Data Processing Inequality. A recurring theme is that the definitions of information theory support natural theorems that sound ``obvious'' when translated into English. More pithily, ``information theory makes common sense precise.'' Since the focus of the notes is not primarily on technical details, proofs are provided only where the relevant techniques are illustrative of broader themes. Otherwise, proofs and intriguing tangents are referenced in liberally-sprinkled footnotes. The notes close with a highly nonexhaustive list of references to resources and other perspectives on the field.
Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective
Venue: arXiv cs.DS 2019
Year: 2019

The main purpose of this paper is pedagogical. Despite its importance, all proofs of the correctness of Strassen's famous 1969 algorithm to multiply two 2x2 matrices with only seven multiplications involve some basis-dependent calculations such as explicitly multiplying specific 2x2 matrices, expanding expressions to cancel terms with opposing signs, or expanding tensors over the standard basis. This makes the proof nontrivial to memorize and many presentations of the proof avoid showing all the details and leave a significant amount of verifications to the reader. In this note we give a short, self-contained, basis-independent proof of the existence of Strassen's algorithm that avoids these types of calculations. We achieve this by focusing on symmetries and algebraic properties. Our proof can be seen as a coordinate-free version of the construction of Clausen from 1988, combined with recent work on the geometry of Strassen's algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.
Fine-grained Visual-textual Representation Learning
Venue: arXiv cs.CV 2019
Year: 2019

Fine-grained visual categorization is to recognize hundreds of subcategories belonging to the same basic-level category, which is a highly challenging task due to the quite subtle and local visual distinctions among similar subcategories. Most existing methods generally learn part detectors to discover discriminative regions for better categorization performance. However, not all parts are beneficial and indispensable for visual categorization, and the setting of part detector number heavily relies on prior knowledge as well as experimental validation. As is known to all, when we describe the object of an image via textual descriptions, we mainly focus on the pivotal characteristics, and rarely pay attention to common characteristics as well as the background areas. This is an involuntary transfer from human visual attention to textual attention, which leads to the fact that textual attention tells us how many and which parts are discriminative and significant to categorization. So textual attention could help us to discover visual attention in image. Inspired by this, we propose a fine-grained visual-textual representation learning (VTRL) approach, and its main contributions are: (1) Fine-grained visual-textual pattern mining devotes to discovering discriminative visual-textual pairwise information for boosting categorization performance through jointly modeling vision and text with generative adversarial networks (GANs), which automatically and adaptively discovers discriminative parts. (2) Visual-textual representation learning jointly combines visual and textual information, which preserves the intra-modality and inter-modality information to generate complementary fine-grained representation, as well as further improves categorization performance.
String Matching: Communication, Circuits, and Learning
Venue: arXiv cs.CC 2019
Year: 2019

String matching is the problem of deciding whether a given $n$-bit string contains a given $k$-bit pattern. We study the complexity of this problem in three settings. Communication complexity. For small $k$, we provide near-optimal upper and lower bounds on the communication complexity of string matching. For large $k$, our bounds leave open an exponential gap; we exhibit some evidence for the existence of a better protocol. Circuit complexity. We present several upper and lower bounds on the size of circuits with threshold and DeMorgan gates solving the string matching problem. Similarly to the above, our bounds are near-optimal for small $k$. Learning. We consider the problem of learning a hidden pattern of length at most $k$ relative to the classifier that assigns 1 to every string that contains the pattern. We prove optimal bounds on the VC dimension and sample complexity of this problem.
Nearest Embedded and Embedding Self-Nested Trees
Venue: arXiv cs.DS 2019
Year: 2019

Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by DAG compression. A method for quantifying the degree of self-similarity of plants through self-nested trees has been introduced by Godin and Ferraro in 2010. The procedure consists in computing a self-nested approximation, called the nearest embedding self-nested tree, that both embeds the plant and is the closest to it. In this paper, we propose a new algorithm that computes the nearest embedding self-nested tree with a smaller overall complexity, but also the nearest embedded self-nested tree. We show from simulations that the latter is mostly the closest to the initial data, which suggests that this better approximation should be used as a privileged measure of the degree of self-similarity of plants.
Balanced Line Separators of Unit Disk Graphs
Venue: arXiv cs.CG 2019
Year: 2019

We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $\ell$ such that $\ell$ intersects at most $O(\sqrt{(m+n)\log{n}})$ disks and each of the halfplanes determined by $\ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(\sqrt{m+n})$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(\sqrt{m})$).
Robust Object Manipulation for Tactile-based Blind Grasping
Venue: arXiv cs.RO 2019
Year: 2019

Tactile-based blind grasping addresses realistic robotic grasping in which the hand only has access to proprioceptive and tactile sensors. The robotic hand has no prior knowledge of the object/grasp properties, such as object weight, inertia, and shape. There exists no manipulation controller that rigorously guarantees object manipulation in such a setting. Here, a robust control law is proposed for object manipulation in tactile-based blind grasping. The analysis ensures semi-global asymptotic and exponential stability in the presence of model uncertainties and external disturbances that are neglected in related work. Simulation and experimental results validate the effectiveness of the proposed approach.
Activity Archetypes in Question-and-Answer (Q&A) Websites - A Study of 50 Stack Exchange Instances
Venue: arXiv cs.SI 2019
Year: 2019

Millions of users on the Internet discuss a variety of topics on Question-and-Answer (Q&A) instances. However, not all instances and topics receive the same amount of attention, as some thrive and achieve self-sustaining levels of activity, while others fail to attract users and either never grow beyond being a small niche community or become inactive. Hence, it is imperative to not only better understand but also to distill deciding factors and rules that define and govern sustainable Q&A instances. We aim to empower community managers with quantitative methods for them to better understand, control and foster their communities, and thus contribute to making the Web a more efficient place to exchange information. To that end, we extract, model and cluster user activity-based time series from $50$ randomly selected Q&A instances from the Stack Exchange network to characterize user behavior. We find four distinct types of user activity temporal patterns, which vary primarily according to the users' activity frequency. Finally, by breaking down total activity in our 50 Q&A instances by the previously identified user activity profiles, we classify those 50 Q&A instances into three different activity profiles. Our parsimonious categorization of Q&A instances aligns with the stage of development and maturity of the underlying communities, and can potentially help operators of such instances: We not only quantitatively assess progress of Q&A instances, but we also derive practical implications for optimizing Q&A community building efforts, as we e.g. recommend which user types to focus on at different developmental stages of a Q&A community.