OpenRaiser/Intern-Atlas huggingface dataset:
On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
Venue: arXiv cs.LG 2021
Year: 2021

We consider local planning in fixed-horizon MDPs with a generative model under the assumption that the optimal value function lies close to the span of a feature map. The generative model provides a local access to the MDP: The planner can ask for random transitions from previously returned states and arbitrary actions, and features are only accessible for states that are encountered in this process. As opposed to previous work (e.g. Lattimore et al. (2020)) where linear realizability of all policies was assumed, we consider the significantly relaxed assumption of a single linearly realizable (deterministic) policy. A recent lower bound by Weisz et al. (2020) established that the related problem when the action-value function of the optimal policy is linearly realizable requires an exponential number of queries, either in $H$ (the horizon of the MDP) or $d$ (the dimension of the feature mapping). Their construction crucially relies on having an exponentially large action set. In contrast, in this work, we establish that poly$(H,d)$ planning is possible with state value function realizability whenever the action set has a constant size. In particular, we present the TensorPlan algorithm which uses poly$((dH/δ)^A)$ simulator queries to find a $δ$-optimal policy relative to any deterministic policy for which the value function is linearly realizable with some bounded parameter. This is the first algorithm to give a polynomial query complexity guarantee using only linear-realizability of a single competing value function. Whether the computation cost is similarly bounded remains an open question. We extend the upper bound to the near-realizable case and to the infinite-horizon discounted setup. We also present a lower bound in the infinite-horizon episodic setting: Planners that achieve constant suboptimality need exponentially many queries, either in $d$ or the number of actions.
A General Coded Caching Scheme for Scalar Linear Function Retrieval
Venue: arXiv cs.IT 2021
Year: 2021

Coded caching aims to minimize the network's peak-time communication load by leveraging the information pre-stored in the local caches at the users. The original single file retrieval setting by Maddah-Ali and Niesen has been recently extended to general Scalar Linear Function Retrieval (SLFR) by Wan et al., who proposed a linear scheme that surprisingly achieves the same optimal load (under the constraint of uncoded cache placement) as in single file retrieval. This paper's goal is to characterize the conditions under which a general SLFR linear scheme is optimal and gain practical insights into why the specific choices made by Wan et al. work. This paper shows that the optimal decoding coefficients are necessarily the product of two terms, one only involving the encoding coefficients and the other only the demands. In addition, the relationships among the encoding coefficients are shown to be captured by the cycles of certain graphs. Thus, a general linear scheme for SLFR can be found by solving a spanning tree problem.
The Pitfall of More Powerful Autoencoders in Lidar-Based Navigation
Venue: arXiv cs.RO 2021
Year: 2021

The benefit of pretrained autoencoders for reinforcement learning in comparison to training on raw observations is already known [1]. In this paper, we address the generation of a compact and information-rich state representation. In particular, we train a variational autoencoder for 2D-lidar scans to use its latent state for reinforcement learning of navigation tasks. To achieve high reconstruction power of our autoencoding pipeline, we propose an - in the context of autoencoding 2D-lidar scans - novel preprocessing into a local binary occupancy image. This has no additional requirements, neither self-localization nor robust mapping, and therefore can be applied in any setting and easily transferred from simulation in real-world. In a second stage, we show the usage of the compact state representation generated by our autoencoding pipeline in a simplistic navigation task and expose the pitfall that increased reconstruction power will always lead to an improved performance. We implemented our approach in python using tensorflow. Our datasets are simulated with pybullet as well as recorded using a slamtec rplidar A3. The experiments show the significantly improved reconstruction capabilities of our approach for 2D-lidar scans w.r.t. the state of the art. However, as we demonstrate in the experiments the impact on reinforcement learning in lidar-based navigation tasks is non-predictable when improving the latent state representation generated by an autoencoding pipeline. This is surprising and needs to be taken into account during the process of optimizing a pretrained autoencoder for reinforcement learning tasks.
The Archerfish Hunting Optimizer: a novel metaheuristic algorithm for global optimization
Venue: arXiv cs.AI 2021
Year: 2021

Global optimization solves real-world problems numerically or analytically by minimizing their objective functions. Most of the analytical algorithms are greedy and computationally intractable. Metaheuristics are nature-inspired optimization algorithms. They numerically find a near-optimal solution for optimization problems in a reasonable amount of time. We propose a novel metaheuristic algorithm for global optimization. It is based on the shooting and jumping behaviors of the archerfish for hunting aerial insects. We name it the Archerfish Hunting Optimizer (AHO). We Perform two sorts of comparisons to validate the proposed algorithm's performance. First, AHO is compared to the 12 recent metaheuristic algorithms (the accepted algorithms for the 2020's competition on single objective bound-constrained numerical optimization) on ten test functions of the benchmark CEC 2020 for unconstrained optimization. Second, the performance of AHO and 3 recent metaheuristic algorithms, is evaluated using five engineering design problems taken from the benchmark CEC 2020 for non-convex constrained optimization. The experimental results are evaluated using the Wilcoxon signed-rank and the Friedman tests. The statistical indicators illustrate that the Archerfish Hunting Optimizer has an excellent ability to accomplish higher performance in competition with the well-established optimizers.
DiSCoL: Toward Engaging Dialogue Systems through Conversational Line Guided Response Generation
Venue: arXiv cs.CL 2021
Year: 2021

Having engaging and informative conversations with users is the utmost goal for open-domain conversational systems. Recent advances in transformer-based language models and their applications to dialogue systems have succeeded to generate fluent and human-like responses. However, they still lack control over the generation process towards producing contentful responses and achieving engaging conversations. To achieve this goal, we present \textbf{DiSCoL} (\textbf{Di}alogue \textbf{S}ystems through \textbf{Co}versational \textbf{L}ine guided response generation). DiSCoL is an open-domain dialogue system that leverages conversational lines (briefly \textbf{convlines}) as controllable and informative content-planning elements to guide the generation model produce engaging and informative responses. Two primary modules in DiSCoL's pipeline are conditional generators trained for 1) predicting relevant and informative convlines for dialogue contexts and 2) generating high-quality responses conditioned on the predicted convlines. Users can also change the returned convlines to \textit{control} the direction of the conversations towards topics that are more interesting for them. Through automatic and human evaluations, we demonstrate the efficiency of the convlines in producing engaging conversations.
Embodied Intelligence via Learning and Evolution
Venue: arXiv cs.LG 2021
Year: 2021

The intertwined processes of learning and evolution in complex environmental niches have resulted in a remarkable diversity of morphological forms. Moreover, many aspects of animal intelligence are deeply embodied in these evolved morphologies. However, the principles governing relations between environmental complexity, evolved morphology, and the learnability of intelligent control, remain elusive, partially due to the substantial challenge of performing large-scale in silico experiments on evolution and learning. We introduce Deep Evolutionary Reinforcement Learning (DERL): a novel computational framework which can evolve diverse agent morphologies to learn challenging locomotion and manipulation tasks in complex environments using only low level egocentric sensory information. Leveraging DERL we demonstrate several relations between environmental complexity, morphological intelligence and the learnability of control. First, environmental complexity fosters the evolution of morphological intelligence as quantified by the ability of a morphology to facilitate the learning of novel tasks. Second, evolution rapidly selects morphologies that learn faster, thereby enabling behaviors learned late in the lifetime of early ancestors to be expressed early in the lifetime of their descendants. In agents that learn and evolve in complex environments, this result constitutes the first demonstration of a long-conjectured morphological Baldwin effect. Third, our experiments suggest a mechanistic basis for both the Baldwin effect and the emergence of morphological intelligence through the evolution of morphologies that are more physically stable and energy efficient, and can therefore facilitate learning and control.
The Forgotten Document-Oriented Database Management Systems: An Overview and Benchmark of Native XML DODBMSes in Comparison with JSON DODBMSes
Venue: arXiv cs.DB 2021
Year: 2021

In the current context of Big Data, a multitude of new NoSQL solutions for storing, managing, and extracting information and patterns from semi-structured data have been proposed and implemented. These solutions were developed to relieve the issue of rigid data structures present in relational databases, by introducing semi-structured and flexible schema design. As current data generated by different sources and devices, especially from IoT sensors and actuators, use either XML or JSON format, depending on the application, database technologies that store and query semi-structured data in XML format are needed. Thus, Native XML Databases, which were initially designed to manipulate XML data using standardized querying languages, i.e., XQuery and XPath, were rebranded as NoSQL Document-Oriented Databases Systems. Currently, the majority of these solutions have been replaced with the more modern JSON based Database Management Systems. However, we believe that XML-based solutions can still deliver performance in executing complex queries on heterogeneous collections. Unfortunately nowadays, research lacks a clear comparison of the scalability and performance for database technologies that store and query documents in XML versus the more modern JSON format. Moreover, to the best of our knowledge, there are no Big Data-compliant benchmarks for such database technologies. In this paper, we present a comparison for selected Document-Oriented Database Systems that either use the XML format to encode documents, i.e., BaseX, eXist-db, and Sedna, or the JSON format, i.e., MongoDB, CouchDB, and Couchbase. To underline the performance differences we also propose a benchmark that uses a heterogeneous complex schema on a large DBLP corpus.
Insiders and Outsiders in Research on Machine Learning and Society
Venue: arXiv cs.CY 2021
Year: 2021

A subset of machine learning research intersects with societal issues, including fairness, accountability and transparency, as well as the use of machine learning for social good. In this work, we analyze the scholars contributing to this research at the intersection of machine learning and society through the lens of the sociology of science. By analyzing the authorship of all machine learning papers posted to arXiv, we show that compared to researchers from overrepresented backgrounds (defined by gender and race/ethnicity), researchers from underrepresented backgrounds are more likely to conduct research at this intersection than other kinds of machine learning research. This state of affairs leads to contention between two perspectives on insiders and outsiders in the scientific enterprise: outsiders being those outside the group being studied, and outsiders being those who have not participated as researchers in an area historically. This contention manifests as an epistemic question on the validity of knowledge derived from lived experience in machine learning research, and predicts boundary work that we see in a real-world example.
System Intelligence for UAV-Based Mission Critical with Challenging 5G/B5G Connectivity
Venue: arXiv cs.NI 2021
Year: 2021

Unmanned aerial vehicles (UAVs) and communication systems are fundamental elements in Mission Critical services, such as search and rescue. In this article, we introduce an architecture for managing and orchestrating 5G and beyond networks that operate over a heterogeneous infrastructure with UAVs' aid. UAVs are used for collecting and processing data, as well as improving communications. The proposed System Intelligence (SI) architecture was designed to comply with recent standardization works, especially the ETSI Experiential Networked Intelligence specifications. Another contribution of this article is an evaluation using a testbed based on a virtualized non-standalone 5G core and a 4G Radio Access Network (RAN) implemented with open-source software. The experimental results indicate, for instance, that SI can substantially improve the latency of UAV-based services by splitting deep neural networks between UAV and edge or cloud equipment. Other experiments explore the slicing of RAN resources and efficient placement of virtual network functions to assess the benefits of incorporating intelligence in UAV-based mission-critical services.
Horizontally Fused Training Array: An Effective Hardware Utilization Squeezer for Training Novel Deep Learning Models
Venue: arXiv cs.LG 2021
Year: 2021

Driven by the tremendous effort in researching novel deep learning (DL) algorithms, the training cost of developing new models increases staggeringly in recent years. We analyze GPU cluster usage statistics from a top research institute for more insights into the hardware efficiency achieved by typical DL training jobs. Our study reveals that single-accelerator training jobs can dominate the cluster-wide resource consumption when launched repetitively (e.g., for hyper-parameter tuning) while severely under-utilizing the hardware. Fortunately, we observe that such workloads have the following unique characteristics: (i) the models among jobs often have the same types of operators with the same shapes, and (ii) the inter-model horizontal fusion of such operators is mathematically equivalent to other already well-optimized operators. Thus, to help DL researchers and practitioners effectively improve the hardware utilization of their novel DL training workloads, we propose Horizontally Fused Training Array (HFTA). HFTA is a new DL framework extension library that horizontally fuses the models from different repetitive jobs deeply down to operators and then trains them simultaneously on a shared accelerator. To show the generality of our solution, we apply HFTA to six DL models training on state-of-the-art accelerators (GPUs and TPUs). Our results indicate that HFTA is highly effective in improving hardware utilization and achieves up to $15.1 \times$ higher training throughput vs. the standard practice of running each job on a separate accelerator.
First- and Second-Moment Constrained Gaussian Channels
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies the channel capacity of intensity-modulation direct-detection (IM/DD) visible light communication (VLC) systems under both optical and electrical power constraints. Specifically, it derives the asymptotic capacities in the high and low signal-to-noise ratio (SNR) regimes under peak, first-moment, and second-moment constraints. The results show that first- and second-moment constraints are never simultaneously active in the asymptotic low-SNR regime, and only in few cases in the asymptotic high-SNR regime. Moreover, the second-moment constraint is more stringent in the asymptotic low-SNR regime than in the high-SNR regime.
Audio Adversarial Examples: Attacks Using Vocal Masks
Venue: arXiv cs.SD 2021
Year: 2021

We construct audio adversarial examples on automatic Speech-To-Text systems . Given any audio waveform, we produce an another by overlaying an audio vocal mask generated from the original audio. We apply our audio adversarial attack to five SOTA STT systems: DeepSpeech, Julius, Kaldi, wav2letter@anywhere and CMUSphinx. In addition, we engaged human annotators to transcribe the adversarial audio. Our experiments show that these adversarial examples fool State-Of-The-Art Speech-To-Text systems, yet humans are able to consistently pick out the speech. The feasibility of this attack introduces a new domain to study machine and human perception of speech.
Reconfigurable-intelligent-surface-assisted Downlink Transmission Design via Bayesian Optimization
Venue: arXiv cs.IT 2021
Year: 2021

This paper investigates the transmission design in the reconfigurable-intelligent-surface (RIS)-assisted downlink system. The channel state information (CSI) is usually difficult to be estimated at the base station (BS) when the RIS is not equipped with radio frequency chains. In this paper, we propose a downlink transmission framework with unknown CSI via Bayesian optimization. Since the CSI is not available at the BS, we treat the unknown objective function as the black-box function and take the beamformer, the phase shift, and the receiving filter as the input. Then the objective function is decomposed as the sum of low-dimension subfunctions to reduce the complexity. By re-expressing the power constraint of the BS in spherical coordinates, the original constraint problem is converted into an equivalent unconstrained problem. The users estimate the sum MSE of the training symbols as the objective value and feed it back to the BS. We assume a Gaussian prior of the feedback samples and the next query point is updated by minimizing the constructed acquisition function. Furthermore, this framework can also be applied to the power transfer system and fairness problems. Simulation results validate the effectiveness of the proposed transmission scheme in the downlink data transmission and power transfer.
Assessing Individual and Community Vulnerability to Fake News in Social Networks
Venue: arXiv cs.SI 2021
Year: 2021

The plague of false information, popularly called fake news has affected lives of news consumers ever since the prevalence of social media. Thus understanding the spread of false information in social networks has gained a lot of attention in the literature. While most proposed models do content analysis of the information, no much work has been done by exploring the community structures that also play an important role in determining how people get exposed to it. In this paper we base our idea on Computational Trust in social networks to propose a novel Community Health Assessment model against fake news. Based on the concepts of neighbor, boundary and core nodes of a community, we propose novel evaluation metrics to quantify the vulnerability of nodes (individual-level) and communities (group-level) to spreading false information. Our model hypothesizes that if the boundary nodes trust the neighbor nodes of a community who are spreaders, the densely-connected core nodes of the community are highly likely to become spreaders. We test our model with communities generated using three popular community detection algorithms based on two new datasets of information spreading networks collected from Twitter. Our experimental results show that the proposed metrics perform clearly better on the networks spreading false information than on those spreading true ones, indicating our community health assessment model is effective.
Cumulant Expansion of Mutual Information for Quantifying Leakage of a Protected Secret
Venue: arXiv cs.IT 2021
Year: 2021

The information leakage of a cryptographic implementation with a given degree of protection is evaluated in a typical situation when the signal-to-noise ratio is small. This is solved by expanding Kullback-Leibler divergence, entropy, and mutual information in terms of moments/cumulants.
Transfer Learning in Bandits with Latent Continuity
Venue: arXiv cs.LG 2021
Year: 2021

Structured stochastic multi-armed bandits provide accelerated regret rates over the standard unstructured bandit problems. Most structured bandits, however, assume the knowledge of the structural parameter such as Lipschitz continuity, which is often not available. To cope with the latent structural parameter, we consider a transfer learning setting in which an agent must learn to transfer the structural information from the prior tasks to the next task, which is inspired by practical problems such as rate adaptation in wireless link. We propose a novel framework to provably and accurately estimate the Lipschitz constant based on previous tasks and fully exploit it for the new task at hand. We analyze the efficiency of the proposed framework in two folds: (i) the sample complexity of our estimator matches with the information-theoretic fundamental limit; and (ii) our regret bound on the new task is close to that of the oracle algorithm with the full knowledge of the Lipschitz constant under mild assumptions. Our analysis reveals a set of useful insights on transfer learning for latent Lipschitzconstants such as the fundamental challenge a learner faces. Our numerical evaluations confirm our theoretical findings and show the superiority of the proposed framework compared to baselines.
User Interface Factors of Mobile UX: A Study with an Incident Reporting Application
Venue: arXiv cs.HC 2021
Year: 2021

Smartphones are now ubiquitous, yet our understanding of user interface factors that maximize mobile user experience (UX), is still limited. This work presents a controlled experiment, which investigated factors that affect the usability and UX of a mobile incident reporting app. The results indicate that sequence of user interface elements matters while striving to increase UX, and that there is no difference between tab and scrolling as navigation modalities in short forms. These findings can serve as building blocks for empirically-derived guidelines for mobile incident reporting.
Non-Symmetric Coded Caching for Location-Dependent Content Delivery
Venue: arXiv cs.IT 2021
Year: 2021

Immersive viewing is emerging as the next interface evolution for human-computer interaction. A truly wireless immersive application necessitates immense data delivery with ultra-low latency, raising stringent requirements for next-generation wireless networks. A potential solution for addressing these requirements is through the efficient usage of in-device storage and computation capabilities. This paper proposes a novel location-based coded cache placement and delivery scheme, which leverages the nested code modulation (NCM) to enable multi-rate multicasting transmission. To provide a uniform quality of experience in different network locations, we formulate a linear programming cache allocation problem. Next, based on the users' spatial realizations, we adopt an NCM based coded delivery algorithm to efficiently serve a distinct group of users during each transmission. Numerical results demonstrate that the proposed location-based delivery method significantly increases transmission efficiency compared to state of the art.