OpenRaiser/Intern-Atlas huggingface dataset:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
Venue: arXiv cs.DS 2023
Year: 2023

We abstract and study \emph{reachability preservers}, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph $G = (V, E)$ and a set of \emph{demand pairs} $P \subseteq V \times V$, a reachability preserver is a sparse subgraph $H$ that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an $n$-node graph and demand pairs of the form $P \subseteq S \times V$ for a small node subset $S$, there is always a reachability preserver on $O(n+\sqrt{n |P| |S|})$ edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which $O(n)$ size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the $O(n^{0.6+\varepsilon})$ of Chlamatac, Dinitz, Kortsarz, and Laekhanukit (SODA'17) to $O(n^{4/7+\varepsilon})$.
Stability of optimal spherical codes
Venue: arXiv cs.IT 2023
Year: 2023

For many extremal configurations of points on a sphere, the linear programming approach can be used to show their optimality. In this paper we establish the general framework for showing stability of such configurations and use this framework to prove the stability of the two spherical codes formed by minimal vectors of the lattice $E_8$ and of the Leech lattice.
Post-Quantum Cryptography: Riemann Primitives and Chrysalis
Venue: arXiv cs.CR 2023
Year: 2023

The Chrysalis project is a proposed method for post-quantum cryptography using the Riemann sphere. To this end, Riemann primitives are introduced in addition to a novel implementation of this new method. Chrysalis itself is the first cryptographic scheme to rely on Holomorphic Learning with Errors, which is a complex form of Learning with Errors. The proposed NP-Hard problem for security reduction is the non-commutative Grothendieck problem. The reduction of this problem is achieved by applying bilinear matrices in terms of the holomorphic vector bundle such that coordinate systems are intersected via surjective functions between each holomorphic expression. The result is an arbitrarily selected set of points within constraints of bilinear matrix inequalities approximate to the non-commutative problem. This is achieved by applying the quadratic form of bilinear matrices to a linear matrix inequality.
Concise Fuzzy Planar Embedding of Graphs: a Dimensionality Reduction Approach
Venue: arXiv cs.AI 2023
Year: 2023

The enormous amount of data to be represented using large graphs exceeds in some cases the resources of a conventional computer. Edges in particular can take up a considerable amount of memory as compared to the number of nodes. However, rigorous edge storage might not always be essential to be able to draw the needed conclusions. A similar problem takes records with many variables and attempts to extract the most discernible features. It is said that the ``dimension'' of this data is reduced. Following an approach with the same objective in mind, we can map a graph representation to a $k$-dimensional space and answer queries of neighboring nodes mainly by measuring Euclidean distances. The accuracy of our answers would decrease but would be compensated for by fuzzy logic which gives an idea about the likelihood of error. This method allows for reasonable representation in memory while maintaining a fair amount of useful information, and allows for concise embedding in $k$-dimensional Euclidean space as well as solving some problems without having to decompress the graph. Of particular interest is the case where $k=2$. Promising highly accurate experimental results are obtained and reported.
A Multilayer Framework for Online Metric Learning
Venue: arXiv cs.CV 2023
Year: 2023

Online metric learning has been widely applied in classification and retrieval. It can automatically learn a suitable metric from data by restricting similar instances to be separated from dissimilar instances with a given margin. However, the existing online metric learning algorithms have limited performance in real-world classifications, especially when data distributions are complex. To this end, this paper proposes a multilayer framework for online metric learning to capture the nonlinear similarities among instances. Different from the traditional online metric learning, which can only learn one metric space, the proposed Multi-Layer Online Metric Learning (MLOML) takes an online metric learning algorithm as a metric layer and learns multiple hierarchical metric spaces, where each metric layer follows a nonlinear layers for the complicated data distribution. Moreover, the forward propagation (FP) strategy and backward propagation (BP) strategy are employed to train the hierarchical metric layers. To build a metric layer of the proposed MLOML, a new Mahalanobis-based Online Metric Learning (MOML) algorithm is presented based on the passive-aggressive strategy and one-pass triplet construction strategy. Furthermore, in a progressively and nonlinearly learning way, MLOML has a stronger learning ability than traditional online metric learning in the case of limited available training data. To make the learning process more explainable and theoretically guaranteed, theoretical analysis is provided. The proposed MLOML enjoys several nice properties, indeed learns a metric progressively, and performs better on the benchmark datasets. Extensive experiments with different settings have been conducted to verify these properties of the proposed MLOML.
Deformable Generator Networks: Unsupervised Disentanglement of Appearance and Geometry
Venue: arXiv cs.LG 2023
Year: 2023

We present a deformable generator model to disentangle the appearance and geometric information for both image and video data in a purely unsupervised manner. The appearance generator network models the information related to appearance, including color, illumination, identity or category, while the geometric generator performs geometric warping, such as rotation and stretching, through generating deformation field which is used to warp the generated appearance to obtain the final image or video sequences. Two generators take independent latent vectors as input to disentangle the appearance and geometric information from image or video sequences. For video data, a nonlinear transition model is introduced to both the appearance and geometric generators to capture the dynamics over time. The proposed scheme is general and can be easily integrated into different generative models. An extensive set of qualitative and quantitative experiments shows that the appearance and geometric information can be well disentangled, and the learned geometric generator can be conveniently transferred to other image datasets to facilitate knowledge transfer tasks.
A Survey of Knowledge Representation in Service Robotics
Venue: arXiv cs.RO 2023
Year: 2023

Within the realm of service robotics, researchers have placed a great amount of effort into learning, understanding, and representing motions as manipulations for task execution by robots. The task of robot learning and problem-solving is very broad, as it integrates a variety of tasks such as object detection, activity recognition, task/motion planning, localization, knowledge representation and retrieval, and the intertwining of perception/vision and machine learning techniques. In this paper, we solely focus on knowledge representations and notably how knowledge is typically gathered, represented, and reproduced to solve problems as done by researchers in the past decades. In accordance with the definition of knowledge representations, we discuss the key distinction between such representations and useful learning models that have extensively been introduced and studied in recent years, such as machine learning, deep learning, probabilistic modelling, and semantic graphical structures. Along with an overview of such tools, we discuss the problems which have existed in robot learning and how they have been built and used as solutions, technologies or developments (if any) which have contributed to solving them. Finally, we discuss key principles that should be considered when designing an effective knowledge representation.
AudioMNIST: Exploring Explainable Artificial Intelligence for Audio Analysis on a Simple Benchmark
Venue: arXiv cs.SD 2023
Year: 2023

Explainable Artificial Intelligence (XAI) is targeted at understanding how models perform feature selection and derive their classification decisions. This paper explores post-hoc explanations for deep neural networks in the audio domain. Notably, we present a novel Open Source audio dataset consisting of 30,000 audio samples of English spoken digits which we use for classification tasks on spoken digits and speakers' biological sex. We use the popular XAI technique Layer-wise Relevance Propagation (LRP) to identify relevant features for two neural network architectures that process either waveform or spectrogram representations of the data. Based on the relevance scores obtained from LRP, hypotheses about the neural networks' feature selection are derived and subsequently tested through systematic manipulations of the input data. Further, we take a step beyond visual explanations and introduce audible heatmaps. We demonstrate the superior interpretability of audible explanations over visual ones in a human user study.
Compressible Spectral Mixture Kernels with Sparse Dependency Structures for Gaussian Processes
Venue: arXiv cs.LG 2023
Year: 2023

Spectral mixture (SM) kernels comprise a powerful class of generalized kernels for Gaussian processes (GPs) to describe complex patterns. This paper introduces model compression and time- and phase (TP) modulated dependency structures to the original (SM) kernel for improved generalization of GPs. Specifically, by adopting Bienaymés identity, we generalize the dependency structure through cross-covariance between the SM components. Then, we propose a novel SM kernel with a dependency structure (SMD) by using cross-convolution between the SM components. Furthermore, we ameliorate the expressiveness of the dependency structure by parameterizing it with time and phase delays. The dependency structure has clear interpretations in terms of spectral density, covariance behavior, and sampling path. To enrich the SMD with effective hyperparameter initialization, compressible SM kernel components, and sparse dependency structures, we introduce a novel structure adaptation (SA) algorithm in the end. A thorough comparative analysis of the SMD on both synthetic and real-life applications corroborates its efficacy.
A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Acceleration
Venue: arXiv cs.LG 2023
Year: 2023

Integrating adaptive learning rate and momentum techniques into SGD leads to a large class of efficiently accelerated adaptive stochastic algorithms, such as AdaGrad, RMSProp, Adam, AccAdaGrad, \textit{etc}. In spite of their effectiveness in practice, there is still a large gap in their theories of convergences, especially in the difficult non-convex stochastic setting. To fill this gap, we propose \emph{weighted AdaGrad with unified momentum}, dubbed AdaUSM, which has the main characteristics that (1) it incorporates a unified momentum scheme which covers both the heavy ball momentum and the Nesterov accelerated gradient momentum; (2) it adopts a novel weighted adaptive learning rate that can unify the learning rates of AdaGrad, AccAdaGrad, Adam, and RMSProp. Moreover, when we take polynomially growing weights in AdaUSM, we obtain its $\mathcal{O}(\log(T)/\sqrt{T})$ convergence rate in the non-convex stochastic setting. We also show that the adaptive learning rates of Adam and RMSProp correspond to taking exponentially growing weights in AdaUSM, thereby providing a new perspective for understanding Adam and RMSProp. Lastly, comparative experiments of AdaUSM against SGD with momentum, AdaGrad, AdaEMA, Adam, and AMSGrad on various deep learning models and datasets are also carried out.
EdgeLaaS: Edge Learning as a Service for Knowledge-Centric Connected Healthcare
Venue: arXiv cs.NI 2023
Year: 2023

By introducing networking technologies and services into healthcare infrastructures (e.g., multimodal sensors and smart devices) that are deployed to supervise a person's health condition, the traditional healthcare system is being revolutionized toward knowledge-centric connected healthcare (KCCH), where persons will take their own responsibility for their healthcare in a knowledge-centric way. Due to the volume, velocity, and variety of healthcare supervision data generated by these healthcare infrastructures, an urgent and strategic issue is how to efficiently process a person's healthcare supervision data with the right knowledge of the right guardians (e.g., relatives, nurses, and doctors) at the right time. To solve this issue, the naming and routing criterion of medical knowledge is studied. With this offloaded medical knowledge, we propose an edge learning as a service (EdgeLaaS) framework for KCCH to locally process health supervision data. In this framework, edge learning nodes can help the patient choose better advice from the right guardians in real time when some emergencies occur. Two application cases: 1) fast self-help and 2) mobile help pre-calling are studied. Performance evaluations demonstrate the superiority of KCCH and EdgeLaaS, respectively.
Distributed Conditional Cooperation Model Predictive Control of Interconnected Microgrids
Venue: arXiv cs.SY 2023
Year: 2023

In this paper, we propose a model predictive control based operation strategy that allows for power exchange between interconnected microgrids. Particularly, the approach ensures that each microgrid benefits from power exchange with others. This is realised by including a condition which is based on the islanded operation cost. The overall model predictive control problem is posed as a mixed-integer quadratically-constrained program and solved using a distributed algorithm that iteratively updates continuous and integer variables. For this algorithm, termination, feasibility and computational properties are discussed. The performance and the computational benefits of the proposed strategy are highlighted in an illustrative case study.
TimbreTron: A WaveNet(CycleGAN(CQT(Audio))) Pipeline for Musical Timbre Transfer
Venue: arXiv cs.SD 2023
Year: 2023

In this work, we address the problem of musical timbre transfer, where the goal is to manipulate the timbre of a sound sample from one instrument to match another instrument while preserving other musical content, such as pitch, rhythm, and loudness. In principle, one could apply image-based style transfer techniques to a time-frequency representation of an audio signal, but this depends on having a representation that allows independent manipulation of timbre as well as high-quality waveform generation. We introduce TimbreTron, a method for musical timbre transfer which applies "image" domain style transfer to a time-frequency representation of the audio signal, and then produces a high-quality waveform using a conditional WaveNet synthesizer. We show that the Constant Q Transform (CQT) representation is particularly well-suited to convolutional architectures due to its approximate pitch equivariance. Based on human perceptual evaluations, we confirmed that TimbreTron recognizably transferred the timbre while otherwise preserving the musical content, for both monophonic and polyphonic samples.
Adversarial Bandits with Knapsacks
Venue: arXiv cs.DS 2023
Year: 2023

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to the algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version and use it as a subroutine to solve the latter.
The Jiminy Advisor: Moral Agreements Among Stakeholders Based on Norms and Argumentation
Venue: arXiv cs.AI 2023
Year: 2023

An autonomous system is constructed by a manufacturer, operates in a society subject to norms and laws, and interacts with end users. All of these actors are stakeholders affected by the behavior of the autonomous system. We address the challenge of how the ethical views of such stakeholders can be integrated in the behavior of an autonomous system. We propose an ethical recommendation component called Jiminy which uses techniques from normative systems and formal argumentation to reach moral agreements among stakeholders. A Jiminy represents the ethical views of each stakeholder by using normative systems, and has three ways of resolving moral dilemmas that involve the opinions of the stakeholders. First, the Jiminy considers how the arguments of the stakeholders relate to one another, which may already resolve the dilemma. Secondly, the Jiminy combines the normative systems of the stakeholders such that the combined expertise of the stakeholders may resolve the dilemma. Thirdly, and only if these two other methods have failed, the Jiminy uses context-sensitive rules to decide which of the stakeholders take preference over the others. At the abstract level, these three methods are characterized by adding arguments, adding attacks between arguments, and revising attacks between arguments. We show how a Jiminy can be used not only for ethical reasoning and collaborative decision-making, but also to provide explanations about ethical behavior.
The Value of Interaction in Data Intelligence
Venue: arXiv cs.HC 2023
Year: 2023

In human computer interaction (HCI), it is common to evaluate the value of HCI designs, techniques, devices, and systems in terms of their benefit to users. It is less common to discuss the benefit of HCI to computers. Every HCI task allows a computer to receive some data from the user. In many situations, the data received by the computer embodies human knowledge and intelligence in handling complex problems, and/or some critical information without which the computer cannot proceed. In this paper, we present an information-theoretic framework for quantifying the knowledge received by the computer from its users via HCI. We apply information-theoretic measures to some common HCI tasks as well as HCI tasks in complex data intelligence processes. We formalize the methods for estimating such quantities analytically and measuring them empirically. Using theoretical reasoning, we can confirm the significant but often undervalued role of HCI in data intelligence workflows.
The Fair Division of Hereditary Set Systems
Venue: arXiv cs.DM 2023
Year: 2023

We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. In this spirit, we study the case where the items form an hereditary set system. We present a simple algorithm that allocates each agent a bundle of items whose value is at least $0.3636$ times the maximin share of the agent. This improves upon the current best known guarantee of $0.2$ due to Ghodsi et al. The analysis of the algorithm is almost tight; we present an instance where the algorithm provides a guarantee of at most $0.3738$. We also show that the algorithm can be implemented in polynomial time given a valuation oracle for each agent.
Learn to Interpret Atari Agents
Venue: arXiv cs.LG 2023
Year: 2023

Deep reinforcement learning (DeepRL) agents surpass human-level performance in many tasks. However, the direct mapping from states to actions makes it hard to interpret the rationale behind the decision-making of the agents. In contrast to previous a-posteriori methods for visualizing DeepRL policies, in this work, we propose to equip the DeepRL model with an innate visualization ability. Our proposed agent, named region-sensitive Rainbow (RS-Rainbow), is an end-to-end trainable network based on the original Rainbow, a powerful deep Q-network agent. It learns important regions in the input domain via an attention module. At inference time, after each forward pass, we can visualize regions that are most important to decision-making by backpropagating gradients from the attention module to the input frames. The incorporation of our proposed module not only improves model interpretability, but leads to performance improvement. Extensive experiments on games from the Atari 2600 suite demonstrate the effectiveness of RS-Rainbow.
Investigating Antigram Behaviour using Distributional Semantics
Venue: arXiv cs.CL 2023
Year: 2023

The field of computational linguistics constantly presents new challenges and topics for research. Whether it be analyzing word usage changes over time or identifying relationships between pairs of seemingly unrelated words. To this point, we identify Anagrams and Antigrams as words possessing such unique properties. The presented work is an exploration into generating anagrams from a given word and determining whether there exists antigram (semantically opposite anagrams) relationships between the pairs of generated anagrams using GloVe embeddings. We propose a rudimentary, yet interpretable, rule-based algorithm for detecting antigrams. On a small dataset of just 12 antigrams, our approach yielded an accuracy of 39\% which shows that there is much work left to be done in this space.
No reference image quality assessment metric based on regional mutual information among images
Venue: arXiv cs.CV 2023
Year: 2023

With the inclusion of camera in daily life, an automatic no reference image quality evaluation index is required for automatic classification of images. The present manuscripts proposes a new No Reference Regional Mutual Information based technique for evaluating the quality of an image. We use regional mutual information on subsets of the complete image. Proposed technique is tested on four benchmark natural image databases, and one benchmark synthetic database. A comparative analysis with classical and state-of-art methods indicate superiority of the present technique for high quality images and comparable for other images of the respective databases.