OpenRaiser/Intern-Atlas huggingface dataset:
Opportunistic Routing for Opto-Acoustic Internet of Underwater Things
Venue: arXiv cs.NI 2020
Year: 2020

Internet of underwater things (IoUT) is a technological revolution that could mark a new era for scientific, industrial, and military underwater applications. To mitigate the hostile underwater channel characteristics, this paper hybridizes underwater acoustic and optical wireless communications to achieve a ubiquitous control and high-speed low-latency networking performance, respectively. Since underwater optical wireless communications (UOWC) suffers from limited range, it requires effective multi-hop routing solutions. In this regard, we propose a Sector-based Opportunistic Routing (SectOR) protocol. Unlike the traditional routing (TR) techniques which unicast packets to a unique relay, opportunistic routing (OR) targets a set of candidate relays by leveraging the broadcast nature of the UOWC channel. OR improves the packet delivery ratio as the likelihood of having at least one successful packet reception is much higher than that in conventional unicast routing. Contingent upon the performance characterization of a single-hop link, we obtain a variety of local and global metrics to evaluate the fitness of a candidate set (CS) and prioritize the members of a CS. Since rate-error and range-beamwidth tradeoffs yield different candidate set diversities, we develop a candidate filtering and searching algorithm to find the optimal sector-shaped coverage region by scanning the feasible search space. Moreover, a hybrid acoustic/optic coordination mechanism is considered to avoid duplicate transmission of the relays. Numerical results show that SectOR protocol can perform even better than an optimal unicast routing protocol in well-connected UOWNs.
An improved FastEuler-DLKF small-UAV AHRS algorithm
Venue: arXiv cs.RO 2020
Year: 2020

The accurate Attitude Heading Reference System(AHRS) is an important apart of the UAV reliable flight system. Aiming at the application scenarios of near ground navigation of small-UAV, this paper establishes a loose couple error model of the gyroscope/accelerometer/magnetometer, and presents an improved FastEuler Double-Layer Kalman Filter algorithm. Using low-cost devices which include MEMS Inertial Measurement Units(IMU) and magnetometers, this paper constructs the AHRS hardware and software systems of UAV, and designs the offline and real-time verification platforms. Moreover, the attitude changes of UAV is analyzed by the simulation and flight test, respectively. In addition, an adaptive factor is used to adjust the measurement noise covariance in order to eliminate the harmful effects of linear acceleration in the accelerometer, which is solved the roll and ptich angle. The experimental comparison with the Complementary Filter shows that the proposed algorithm can provide accurate attitude information when UAV is flying, which improves the accuracy and reliability of attitude solution, and removes the influence the gyro bias for the attitude estimation.
EyeTAP: A Novel Technique using Voice Inputs to Address the Midas Touch Problem for Gaze-based Interactions
Venue: arXiv cs.HC 2020
Year: 2020

One of the main challenges of gaze-based interactions is the ability to distinguish normal eye function from a deliberate interaction with the computer system, commonly referred to as 'Midas touch'. In this paper we propose, EyeTAP (Eye tracking point-and-select by Targeted Acoustic Pulse) a hands-free interaction method for point-and-select tasks. We evaluated the prototype in two separate user studies, each containing two experiments with 33 participants and found that EyeTAP is robust even in presence of ambient noise in the audio input signal with tolerance of up to 70 dB, results in a faster movement time, and faster task completion time, and has a lower cognitive workload than voice recognition. In addition, EyeTAP has a lower error rate than the dwell-time method in a ribbon-shaped experiment. These characteristics make it applicable for users for whom physical movements are restricted or not possible due to a disability. Furthermore, EyeTAP has no specific requirements in terms of user interface design and therefore it can be easily integrated into existing systems with minimal modifications. EyeTAP can be regarded as an acceptable alternative to address the Midas touch.
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
Venue: arXiv cs.GT 2020
Year: 2020

In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincaré recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting the reward (by adding a regularization term) of the game can give strong convergence guarantees in monotone games. We continue by showing how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium. Finally, we show how these insights can be directly used to build state-of-the-art model-free algorithms for zero-sum two-player Imperfect Information Games (IIG).
Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs
Venue: arXiv cs.DS 2020
Year: 2020

The zeta and Moebius transforms over the subset lattice of $n$ elements and the so-called subset convolution are examples of unary and binary operations on set functions. While their direct computation requires $O(3^n)$ arithmetic operations, less naive algorithms only use $2^n \mathrm{poly}(n)$ operations, nearly linear in the input size. Here, we investigate a related $n$-ary operation that takes $n$ set functions as input and maps them to a new set function. This operation, we call multi-subset transform, is the core ingredient in the known inclusion--exclusion recurrence for weighted sums over acyclic digraphs, which extends Robinson's recurrence for the number of labelled acyclic digraphs. Prior to this work the best known complexity bound was the direct $O(3^n)$. By reducing the task to multiple instances of rectangular matrix multiplication, we improve the complexity to $O(2.985^n)$.
Massive MIMO with Multi-Antenna Users under Jointly Correlated Ricean Fading
Venue: arXiv cs.IT 2020
Year: 2020

We study the uplink performance of massive multiple-input multiple-output (MIMO) when users are equipped with multiple antennas. To this end, we consider a generalized channel model that accounts for line-of-sight propagation and spatially correlated multipath fading. Most importantly, we employ the Weichselberger correlation model, which has been shown to alleviate the deficiencies of the popular Kronecker model. The main contribution of this paper is a rigorous closed-form expression for the uplink spectral efficiency using maximum-ratio combining and minimum mean square error channel estimation. Our result is a non-trivial generalization of previous results on massive MIMO with spatially correlated channels, thereby enabling us to have suitable designs for future massive MIMO systems. Numerical simulations corroborate our analysis and provide useful insights on how different propagation conditions affect system performance.
Modelling response to trypophobia trigger using intermediate layers of ImageNet networks
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we approach the problem of detecting trypophobia triggers using Convolutional neural networks. We show that standard architectures such as VGG or ResNet are capable of recognizing trypophobia patterns. We also conduct experiments to analyze the nature of this phenomenon. To do that, we dissect the network decreasing the number of its layers and parameters. We prove, that even significantly reduced networks have accuracy above 91% and focus their attention on the trypophobia patterns as presented on the visual explanations.
Space Efficient Deterministic Approximation of String Measures
Venue: arXiv cs.DS 2020
Year: 2020

We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increasing sequence (LIS). All three problems can be solved exactly by standard algorithms that run in polynomial time with roughly $Θ(n)$ space, where $n$ is the input length, and our goal is to design deterministic approximation algorithms that run in polynomial time with significantly smaller space. Towards this, we design several algorithms that achieve $1+ε$ or $1-ε$ approximation for all three problems, where $ε>0$ can be any constant and even slightly sub constant. Our algorithms are flexible and can be adjusted to achieve the following two regimes of parameters: 1) space $n^δ$ for any constant $δ>0$ with running time essentially the same as or slightly more than the standard algorithms; and 2) space $\mathsf{polylog}(n)$ with (a larger) polynomial running time, which puts the approximation versions of the three problems in Steve's class (\textbf{SC}). Our algorithms significantly improve previous results in terms of space complexity, where all known results need to use space at least $Ω(\sqrt{n})$. Some of our algorithms can also be adapted to work in the asymmetric streaming model [SS13], and output the corresponding sequence. Furthermore, our results can be used to improve a recent result by Farhadi et. al. [FHRS20] about approximating ED in the asymmetric streaming model, reducing the running time from being exponential in [FHRS20] to a polynomial. Our algorithms are based on the idea of using recursion as in Savitch's theorem [Sav70], and a careful adaption of previous techniques to make the recursion work. Along the way we also give a new logspace reduction from longest common subsequence to longest increasing sequence, which may be of independent interest.
The Problem with Metrics is a Fundamental Problem for AI
Venue: arXiv cs.CY 2020
Year: 2020

Optimizing a given metric is a central aspect of most current AI approaches, yet overemphasizing metrics leads to manipulation, gaming, a myopic focus on short-term goals, and other unexpected negative consequences. This poses a fundamental contradiction for AI development. Through a series of real-world case studies, we look at various aspects of where metrics go wrong in practice and aspects of how our online environment and current business practices are exacerbating these failures. Finally, we propose a framework towards mitigating the harms caused by overemphasis of metrics within AI by: (1) using a slate of metrics to get a fuller and more nuanced picture, (2) combining metrics with qualitative accounts, and (3) involving a range of stakeholders, including those who will be most impacted.
Towards a Soft Faceted Browsing Scheme for Information Access
Venue: arXiv cs.IR 2020
Year: 2020

Faceted browsing is a commonly supported feature of user interfaces for access to information. Existing interfaces generally treat facet values selected by a user as hard filters and respond to the user by only displaying information items strictly satisfying the filters and in their original ranking order. We propose a novel alternative strategy for faceted browsing, called soft faceted browsing, where the system also includes some possibly relevant items outside the selected filter in a non-intrusive way and re-ranks the items to better satisfy the user's information need. Such a soft faceted browsing strategy can be beneficial when the user does not have a very confident and strict preference for the selected facet values, and is especially appropriate for applications such as e-commerce search where the user would like to explore a larger space before finalizing a purchasing decision. We propose a probabilistic framework for modeling and solving the soft faceted browsing problem, and apply the framework to study the case of facet filter selection in e-commerce search engines. Preliminary experiment results demonstrate the soft faceted browsing scheme is better than the traditional faceted browsing scheme in terms of its efficiency in helping users navigate in the information space.
Convergence-guaranteed Independent Positive Semidefinite Tensor Analysis Based on Student's t Distribution
Venue: arXiv cs.SD 2020
Year: 2020

In this paper, we address a blind source separation (BSS) problem and propose a new extended framework of independent positive semidefinite tensor analysis (IPSDTA). IPSDTA is a state-of-the-art BSS method that enables us to take interfrequency correlations into account, but the generative model is limited within the multivariate Gaussian distribution and its parameter optimization algorithm does not guarantee stable convergence. To resolve these problems, first, we propose to extend the generative model to a parametric multivariate Student's t distribution that can deal with various types of signal. Secondly, we derive a new parameter optimization algorithm that guarantees the monotonic nonincrease in the cost function, providing stable convergence. Experimental results reveal that the cost function in the conventional IPSDTA does not display monotonically nonincreasing properties. On the other hand, the proposed method guarantees the monotonic nonincrease in the cost function and outperforms the conventional ILRMA and IPSDTA in the source-separation performance.
Programmable Metasurface Based Multicast Systems: Design and Analysis
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a multi-antenna multicast system with programmable metasurface (PMS) based transmitter. Taking into account of the finite-resolution phase shifts of PMSs, a novel beam training approach is proposed, which achieves comparable performance as the exhaustive beam searching method but with much lower time overhead. Then, a closed-form expression for the achievable multicast rate is presented, which is valid for arbitrary system configurations. In addition, for certain asymptotic scenario, simple approximated expressions for the multicase rate are derived. Closed-form solutions are obtained for the optimal power allocation scheme, and it is shown that equal power allocation is optimal when the pilot power or the number of reflecting elements is sufficiently large. However, it is desirable to allocate more power to weaker users when there are a large number of RF chains. The analytical findings indicate that, with large pilot power, the multicast rate is determined by the weakest user. Also, increasing the number of radio frequency (RF) chains or reflecting elements can significantly improve the multicast rate, and as the phase shift number becomes larger, the multicast rate improves first and gradually converges to a limit. Moreover, increasing the number of users would significantly degrade the multicast rate, but this rate loss can be compensated by implementing a large number of reflecting elements.
Uncovering Coresets for Classification With Multi-Objective Evolutionary Algorithms
Venue: arXiv cs.LG 2020
Year: 2020

A coreset is a subset of the training set, using which a machine learning algorithm obtains performances similar to what it would deliver if trained over the whole original data. Coreset discovery is an active and open line of research as it allows improving training speed for the algorithms and may help human understanding the results. Building on previous works, a novel approach is presented: candidate corsets are iteratively optimized, adding and removing samples. As there is an obvious trade-off between limiting training size and quality of the results, a multi-objective evolutionary algorithm is used to minimize simultaneously the number of points in the set and the classification error. Experimental results on non-trivial benchmarks show that the proposed approach is able to deliver results that allow a classifier to obtain lower error and better ability of generalizing on unseen data than state-of-the-art coreset discovery techniques.
Computational Design with Crowds
Venue: arXiv cs.GR 2020
Year: 2020

Computational design is aimed at supporting or automating design processes using computational techniques. However, some classes of design tasks involve criteria that are difficult to handle only with computers. For example, visual design tasks seeking to fulfill aesthetic goals are difficult to handle purely with computers. One promising approach is to leverage human computation; that is, to incorporate human input into the computation process. Crowdsourcing platforms provide a convenient way to integrate such human computation into a working system. In this chapter, we discuss such computational design with crowds in the domain of parameter tweaking tasks in visual design. Parameter tweaking is often performed to maximize the aesthetic quality of designed objects. Computational design powered by crowds can solve this maximization problem by leveraging human computation. We discuss the opportunities and challenges of computational design with crowds with two illustrative examples: (1) estimating the objective function (specifically, preference learning from crowds' pairwise comparisons) to facilitate interactive design exploration by a designer and (2) directly searching for the optimal parameter setting that maximizes the objective function (specifically, crowds-in-the-loop Bayesian optimization).
How to make Firmware Updates over LoRaWAN Possible
Venue: arXiv cs.NI 2020
Year: 2020

Embedded software management requirements due to concerns about security vulnerabilities or for feature updates in the Internet of Things (IoT) deployments have raised the need for Firmware Update Over The Air (FUOTA). With FUOTA's support, security updates, new functionalities, and optimization patches can be deployed with little human intervention to embedded devices over their lifetime. However, supporting FUTOA over one of the most promising IoT networking technologies, LoRaWAN, is not a straightforward task due to LoRaWAN's limitations that do not provide for data bulk transfer such as a firmware image. Therefore, the LoRa Alliance has proposed new specifications to support multicast, fragmentation, and clock synchronization, which are essential features to enable efficient FUOTA in LoRaWAN. In this paper, we review these new specifications and evaluate the FUOTA process in order to quantify the impact of the different FUOTA parameters in terms of the firmware update time, the device's energy consumption, and the firmware update efficiency, showing different trade-offs among the parameters. For this, we developed FUOTASim, a simulation tool that allows us to determine the best FUOTA parameters.
Soundness conditions for big-step semantics
Venue: arXiv cs.PL 2020
Year: 2020

We propose a general proof technique to show that a predicate is sound, that is, prevents stuck computation, with respect to a big-step semantics. This result may look surprising, since in big-step semantics there is no difference between non-terminating and stuck computations, hence soundness cannot even be expressed. The key idea is to define constructions yielding an extended version of a given arbitrary big-step semantics, where the difference is made explicit. The extended semantics are exploited in the meta-theory, notably they are necessary to show that the proof technique works. However, they remain transparent when using the proof technique, since it consists in checking three conditions on the original rules only, as we illustrate by several examples.
On the Uniqueness of Simultaneous Rational Function Reconstruction
Venue: arXiv cs.SC 2020
Year: 2020

This paper focuses on the problem of reconstructing a vector of rational functions given some evaluations, or more generally given their remainders modulo different polynomials. The special case of rational functions sharing the same denominator, a.k.a.Simultaneous Rational Function Reconstruction (SRFR), has many applications from linear system solving to coding theory, provided that SRFR has a unique solution. The number of unknowns in SRFR is smaller than for a general vector of rational function. This allows to reduce the number of evaluation points needed to guarantee the existence of a solution, but we may lose its uniqueness. In this work, we prove that uniqueness is guaranteed for a generic instance.
How To Avoid Being Eaten By a Grue: Exploration Strategies for Text-Adventure Agents
Venue: arXiv cs.LG 2020
Year: 2020

Text-based games -- in which an agent interacts with the world through textual natural language -- present us with the problem of combinatorially-sized action-spaces. Most current reinforcement learning algorithms are not capable of effectively handling such a large number of possible actions per turn. Poor sample efficiency, consequently, results in agents that are unable to pass bottleneck states, where they are unable to proceed because they do not see the right action sequence to pass the bottleneck enough times to be sufficiently reinforced. Building on prior work using knowledge graphs in reinforcement learning, we introduce two new game state exploration strategies. We compare our exploration strategies against strong baselines on the classic text-adventure game, Zork1, where prior agent have been unable to get past a bottleneck where the agent is eaten by a Grue.
Dissipative SymODEN: Encoding Hamiltonian Dynamics with Dissipation and Control into Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we introduce Dissipative SymODEN, a deep learning architecture which can infer the dynamics of a physical system with dissipation from observed state trajectories. To improve prediction accuracy while reducing network size, Dissipative SymODEN encodes the port-Hamiltonian dynamics with energy dissipation and external input into the design of its computation graph and learns the dynamics in a structured way. The learned model, by revealing key aspects of the system, such as the inertia, dissipation, and potential energy, paves the way for energy-based controllers.
Contextual Lensing of Universal Sentence Representations
Venue: arXiv cs.CL 2020
Year: 2020

What makes a universal sentence encoder universal? The notion of a generic encoder of text appears to be at odds with the inherent contextualization and non-permanence of language use in a dynamic world. However, mapping sentences into generic fixed-length vectors for downstream similarity and retrieval tasks has been fruitful, particularly for multilingual applications. How do we manage this dilemma? In this work we propose Contextual Lensing, a methodology for inducing context-oriented universal sentence vectors. We break the construction of universal sentence vectors into a core, variable length, sentence matrix representation equipped with an adaptable `lens' from which fixed-length vectors can be induced as a function of the lens context. We show that it is possible to focus notions of language similarity into a small number of lens parameters given a core universal matrix representation. For example, we demonstrate the ability to encode translation similarity of sentences across several languages into a single weight matrix, even when the core encoder has not seen parallel data.
Multi-Agent Reinforcement Learning as a Computational Tool for Language Evolution Research: Historical Context and Future Challenges
Venue: arXiv cs.MA 2020
Year: 2020

Computational models of emergent communication in agent populations are currently gaining interest in the machine learning community due to recent advances in Multi-Agent Reinforcement Learning (MARL). Current contributions are however still relatively disconnected from the earlier theoretical and computational literature aiming at understanding how language might have emerged from a prelinguistic substance. The goal of this paper is to position recent MARL contributions within the historical context of language evolution research, as well as to extract from this theoretical and computational background a few challenges for future research.