OpenRaiser/Intern-Atlas huggingface dataset:
Online Stochastic Gradient Descent Learns Linear Dynamical Systems from A Single Trajectory
Venue: arXiv cs.LG 2021
Year: 2021

This work investigates the problem of estimating the weight matrices of a stable time-invariant linear dynamical system from a single sequence of noisy measurements. We show that if the unknown weight matrices describing the system are in Brunovsky canonical form, we can efficiently estimate the ground truth unknown matrices of the system from a linear system of equations formulated based on the transfer function of the system, using both online and offline stochastic gradient descent (SGD) methods. Specifically, by deriving concrete complexity bounds, we show that SGD converges linearly in expectation to any arbitrary small Frobenius norm distance from the ground truth weights. To the best of our knowledge, ours is the first work to establish linear convergence characteristics for online and offline gradient-based iterative methods for weight matrix estimation in linear dynamical systems from a single trajectory. Extensive numerical tests verify that the performance of the proposed methods is consistent with our theory, and show their superior performance relative to existing state of the art methods.
Uniform Elgot Iteration in Foundations
Venue: arXiv cs.LO 2021
Year: 2021

Category theory is famous for its innovative way of thinking of concepts by their descriptions, in particular by establishing universal properties. Concepts that can be characterized in a universal way receive a certain quality seal, which makes them easily transferable across application domains. The notion of partiality is however notoriously difficult to characterize in this way, although the importance of it is certain, especially for computer science where entire research areas, such as synthetic and axiomatic domain theory revolve around notions of partiality. More recently, this issue resurfaced in the context of (constructive) intensional type theory. Here, we provide a generic categorical iteration-based notion of partiality, which is arguably the most basic one. We show that the emerging free structures, which we dub uniform-iteration algebras enjoy various desirable properties, in particular, yield an equational lifting monad. We then study the impact of classicality assumptions and choice principles on this monad, in particular, we establish a suitable categorial formulation of the axiom of countable choice entailing that the monad is an Elgot monad.
Finding Stable Matchings in PhD Markets with Consistent Preferences and Cooperative Partners
Venue: arXiv cs.GT 2021
Year: 2021

We introduce a new algorithm for finding stable matchings in multi-sided matching markets. Our setting is motivated by a PhD market of students, advisors, and co-advisors, and can be generalized to supply chain networks viewed as $n$-sided markets. In the three-sided PhD market, students primarily care about advisors and then about co-advisors (consistent preferences), while advisors and co-advisors have preferences over students only (hence they are cooperative). A student must be matched to one advisor and one co-advisor, or not at all. In contrast to previous work, advisor-student and student-co-advisor pairs may not be mutually acceptable (e.g., a student may not want to work with an advisor or co-advisor and vice versa). We show that three-sided stable matchings always exist, and present an algorithm that, in time quadratic in the market size (up to log factors), finds a three-sided stable matching using any two-sided stable matching algorithm as matching engine. We illustrate the challenges that arise when not all advisor-co-advisor pairs are compatible. We then generalize our algorithm to $n$-sided markets with quotas and show how they can model supply chain networks. Finally, we show how our algorithm outperforms the baseline given by [Danilov, 2003] in terms of both producing a stable matching and a larger number of matches on a synthetic dataset.
Chasm in Hegemony: Explaining and Reproducing Disparities in Homophilous Networks
Venue: arXiv cs.SI 2021
Year: 2021

In networks with a minority and a majority community, it is well-studied that minorities are under-represented at the top of the social hierarchy. However, researchers are less clear about the representation of minorities from the lower levels of the hierarchy, where other disadvantages or vulnerabilities may exist. We offer a more complete picture of social disparities at each social level with empirical evidence that the minority representation exhibits two opposite phases: at the higher rungs of the social ladder, the representation of the minority community decreases; but, lower in the ladder, which is more populous, as you ascend, the representation of the minority community improves. We refer to this opposing phenomenon between the upper-level and lower-level as the \emph{chasm effect}. Previous models of network growth with homophily fail to detect and explain the presence of this chasm effect. We analyze the interactions among a few well-observed network-growing mechanisms with a simple model to reveal the sufficient and necessary conditions for both phases in the chasm effect to occur. By generalizing the simple model naturally, we present a complete bi-affiliation bipartite network-growth model that could successfully capture disparities at all social levels and reproduce real social networks. Finally, we illustrate that addressing the chasm effect can create fairer systems with two applications in advertisement and fact-checks, thereby demonstrating the potential impact of the chasm effect on the future research of minority-majority disparities and fair algorithms.
Design and Analysis of a Logless Dynamic Reconfiguration Protocol
Venue: arXiv cs.DC 2021
Year: 2021

Distributed replication systems based on the replicated state machine model have become ubiquitous as the foundation of modern database systems. To ensure availability in the presence of faults, these systems must be able to dynamically replace failed nodes with healthy ones via dynamic reconfiguration. MongoDB is a document oriented database with a distributed replication mechanism derived from the Raft protocol. In this paper, we present MongoRaftReconfig, a novel dynamic reconfiguration protocol for the MongoDB replication system. MongoRaftReconfig utilizes a logless approach to managing configuration state and decouples the processing of configuration changes from the main database operation log. The protocol's design was influenced by engineering constraints faced when attempting to redesign an unsafe, legacy reconfiguration mechanism that existed previously in MongoDB. We provide a safety proof of MongoRaftReconfig, along with a formal specification in TLA+. To our knowledge, this is the first published safety proof and formal specification of a reconfiguration protocol for a Raft-based system. We also present results from model checking its safety properties on finite protocol instances. Finally, we discuss the conceptual novelties of MongoRaftReconfig, how it can be understood as an optimized and generalized version of the single server reconfiguration algorithm of Raft, and present an experimental evaluation of how its optimizations can provide performance benefits for reconfigurations.
Lotka's Law and Pattern of Author Productivity in the Field of Brain Concussion Research: A Scientometric Analysis
Venue: arXiv cs.DL 2021
Year: 2021

The present study deals a scientometric analysis of 8486 bibliometric publications retrieved from the Web of Science database during the period 2008 to 2017. Data is collected and analyzed using Bibexcel software. The study focuses on various aspect of the quantitative research such as growth of papers (year wise), Collaborative Index (CI), Degree of Collaboration (DC), Co-authorship Index (CAI), Collaborative Co-efficient (CC), Modified Collaborative Co-Efficient (MCC), Lotka's Exponent value, Kolmogorov-Smirnov test (K-S Test).
Hero: On the Chaos When PATH Meets Modules
Venue: arXiv cs.SE 2021
Year: 2021

Ever since its first release in 2009, the Go programming language (Golang) has been well received by software communities. A major reason for its success is the powerful support of library-based development, where a Golang project can be conveniently built on top of other projects by referencing them as libraries. As Golang evolves, it recommends the use of a new library-referencing mode to overcome the limitations of the original one. While these two library modes are incompatible, both are supported by the Golang ecosystem. The heterogeneous use of library-referencing modes across Golang projects has caused numerous dependency management (DM) issues, incurring reference inconsistencies and even build failures. Motivated by the problem, we conducted an empirical study to characterize the DM issues, understand their root causes, and examine their fixing solutions. Based on our findings, we developed \textsc{Hero}, an automated technique to detect DM issues and suggest proper fixing solutions. We applied \textsc{Hero} to 19,000 popular Golang projects. The results showed that \textsc{Hero} achieved a high detection rate of 98.5\% on a DM issue benchmark and found 2,422 new DM issues in 2,356 popular Golang projects. We reported 280 issues, among which 181 (64.6\%) issues have been confirmed, and 160 of them (88.4\%) have been fixed or are under fixing. Almost all the fixes have adopted our fixing suggestions.
A New Pairwise Deep Learning Feature For Environmental Microorganism Image Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Environmental microorganism (EM) offers a high-efficient, harmless, and low-cost solution to environmental pollution. They are used in sanitation, monitoring, and decomposition of environmental pollutants. However, this depends on the proper identification of suitable microorganisms. In order to fasten, low the cost, increase consistency and accuracy of identification, we propose the novel pairwise deep learning features to analyze microorganisms. The pairwise deep learning features technique combines the capability of handcrafted and deep learning features. In this technique we, leverage the Shi and Tomasi interest points by extracting deep learning features from patches which are centered at interest points locations. Then, to increase the number of potential features that have intermediate spatial characteristics between nearby interest points, we use Delaunay triangulation theorem and straight-line geometric theorem to pair the nearby deep learning features. The potential of pairwise features is justified on the classification of EMs using SVMs, k-NN, and Random Forest classifier. The pairwise features obtain outstanding results of 99.17%, 91.34%, 91.32%, 91.48%, and 99.56%, which are the increase of about 5.95%, 62.40%, 62.37%, 61.84%, and 3.23% in accuracy, F1-score, recall, precision, and specificity respectively, compared to non-paired deep learning features.
A Trident Quaternion Framework for Inertial-based Navigation Part II: Error Models and Application to Initial Alignment
Venue: arXiv cs.RO 2021
Year: 2021

This work deals with error models for trident quaternion framework proposed in the companion paper (Part I) and further uses them to investigate the odometer-aided static/in-motion inertial navigation attitude alignment for land vehicles. By linearizing the trident quaternion kinematic equation, the left and right trident quaternion error models are obtained, which are found to be equivalent to those derived from profound group affine. The two error models are used to design their corresponding extended Kalman filters (EKF), namely, the left-quaternion EKF (LQEKF) and the right-quaternion EKF (RQEKF). Simulations and field tests are conducted to evaluate their actual performances. Owing to the high estimation consistency, the L/RQEKF converge much faster in the static alignment than the traditional error model-based EKF, even under arbitrary large heading initialization. For the in-motion alignment, the L/RQEKF possess much larger convergence region than the traditional EKF does, although they still require the aid of attitude initialization so as to avoid large initial attitude errors.
A CP-Net based Qualitative Composition Approach for an IaaS Provider
Venue: arXiv cs.AI 2021
Year: 2021

We propose a novel CP-Net based composition approach to qualitatively select an optimal set of consumers for an IaaS provider. The IaaS provider's and consumers' qualitative preferences are captured using CP-Nets. We propose a CP-Net composability model using the semantic congruence property of a qualitative composition. A greedy-based and a heuristic-based consumer selection approaches are proposed that effectively reduce the search space of candidate consumers in the composition. Experimental results prove the feasibility of the proposed composition approach.
Malicious and Low Credibility URLs on Twitter during the AstraZeneca COVID-19 Vaccine Development
Venue: arXiv cs.SI 2021
Year: 2021

We investigate the link sharing behavior of Twitter users following the temporary halt of AstraZeneca COVID-19 vaccine development in September 2020. During this period, we show the presence of malicious and low credibility information sources shared on Twitter messages in multiple languages. The malicious URLs, often in shortened forms, are increasingly hosted in content delivery networks and shared cloud hosting infrastructures not only to improve reach but also to avoid being detected and blocked. There are potential signs of coordination to promote both malicious and low credibility URLs on Twitter. Our findings suggest the need to develop a system that monitors the low-quality URLs shared in times of crisis.
Density Sketches for Sampling and Estimation
Venue: arXiv cs.DS 2021
Year: 2021

We introduce Density sketches (DS): a succinct online summary of the data distribution. DS can accurately estimate point wise probability density. Interestingly, DS also provides a capability to sample unseen novel data from the underlying data distribution. Thus, analogous to popular generative models, DS allows us to succinctly replace the real-data in almost all machine learning pipelines with synthetic examples drawn from the same distribution as the original data. However, unlike generative models, which do not have any statistical guarantees, DS leads to theoretically sound asymptotically converging consistent estimators of the underlying density function. Density sketches also have many appealing properties making them ideal for large-scale distributed applications. DS construction is an online algorithm. The sketches are additive, i.e., the sum of two sketches is the sketch of the combined data. These properties allow data to be collected from distributed sources, compressed into a density sketch, efficiently transmitted in the sketch form to a central server, merged, and re-sampled into a synthetic database for modeling applications. Thus, density sketches can potentially revolutionize how we store, communicate, and distribute data.
Actionable Principles for Artificial Intelligence Policy: Three Pathways
Venue: arXiv cs.CY 2021
Year: 2021

In the development of governmental policy for artificial intelligence (AI) that is informed by ethics, one avenue currently pursued is that of drawing on AI Ethics Principles. However, these AI Ethics Principles often fail to be actioned in governmental policy. This paper proposes a novel framework for the development of Actionable Principles for AI. The approach acknowledges the relevance of AI Ethics Principles and homes in on methodological elements to increase their practical implementability in policy processes. As a case study, elements are extracted from the development process of the Ethics Guidelines for Trustworthy AI of the European Commissions High Level Expert Group on AI. Subsequently, these elements are expanded on and evaluated in light of their ability to contribute to a prototype framework for the development of Actionable Principles for AI. The paper proposes the following three propositions for the formation of such a prototype framework: (1) preliminary landscape assessments; (2) multi-stakeholder participation and cross-sectoral feedback; and, (3) mechanisms to support implementation and operationalizability.
Task-Specific Pre-Training and Cross Lingual Transfer for Code-Switched Data
Venue: arXiv cs.CL 2021
Year: 2021

Using task-specific pre-training and leveraging cross-lingual transfer are two of the most popular ways to handle code-switched data. In this paper, we aim to compare the effects of both for the task of sentiment analysis. We work with two Dravidian Code-Switched languages - Tamil-Engish and Malayalam-English and four different BERT based models. We compare the effects of task-specific pre-training and cross-lingual transfer and find that task-specific pre-training results in superior zero-shot and supervised performance when compared to performance achieved by leveraging cross-lingual transfer from multilingual BERT models.
Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT
Venue: arXiv cs.CR 2021
Year: 2021

The recently proposed Fast Fourier Transform (FFT)-based accountant for evaluating $(\varepsilon,δ)$-differential privacy guarantees using the privacy loss distribution formalism has been shown to give tighter bounds than commonly used methods such as Rényi accountants when applied to homogeneous compositions, i.e., to compositions of identical mechanisms. In this paper, we extend this approach to heterogeneous compositions. We carry out a full error analysis that allows choosing the parameters of the algorithm such that a desired accuracy is obtained. The analysis also extends previous results by taking into account all the parameters of the algorithm. Using the error analysis, we also give a bound for the computational complexity in terms of the error which is analogous to and slightly tightens the one given by Murtagh and Vadhan (2018). We also show how to speed up the evaluation of tight privacy guarantees using the Plancherel theorem at the cost of increased pre-computation and memory usage.
Kernel-based framework to estimate deformations of pneumothorax lung using relative position of anatomical landmarks
Venue: arXiv cs.CV 2021
Year: 2021

In video-assisted thoracoscopic surgeries, successful procedures of nodule resection are highly dependent on the precise estimation of lung deformation between the inflated lung in the computed tomography (CT) images during preoperative planning and the deflated lung in the treatment views during surgery. Lungs in the pneumothorax state during surgery have a large volume change from normal lungs, making it difficult to build a mechanical model. The purpose of this study is to develop a deformation estimation method of the 3D surface of a deflated lung from a few partial observations. To estimate deformations for a largely deformed lung, a kernel regression-based solution was introduced. The proposed method used a few landmarks to capture the partial deformation between the 3D surface mesh obtained from preoperative CT and the intraoperative anatomical positions. The deformation for each vertex of the entire mesh model was estimated per-vertex as a relative position from the landmarks. The landmarks were placed in the anatomical position of the lung's outer contour. The method was applied on nine datasets of the left lungs of live Beagle dogs. Contrast-enhanced CT images of the lungs were acquired. The proposed method achieved a local positional error of vertices of 2.74 mm, Hausdorff distance of 6.11 mm, and Dice similarity coefficient of 0.94. Moreover, the proposed method could estimate lung deformations from a small number of training cases and a small observation area. This study contributes to the data-driven modeling of pneumothorax deformation of the lung.
Quantum Annealing for Large MIMO Downlink Vector Perturbation Precoding
Venue: arXiv cs.NI 2021
Year: 2021

In a multi-user system with multiple antennas at the base station, precoding techniques in the downlink broadcast channel allow users to detect their respective data in a non-cooperative manner. Vector Perturbation Precoding (VPP) is a non-linear variant of transmit-side channel inversion that perturbs user data to achieve full diversity order. While promising, finding an optimal perturbation in VPP is known to be an NP-hard problem, demanding heavy computational support at the base station and limiting the feasibility of the approach to small MIMO systems. This work proposes a radically different processing architecture for the downlink VPP problem, one based on Quantum Annealing (QA), to enable the applicability of VPP to large MIMO systems. Our design reduces VPP to a quadratic polynomial form amenable to QA, then refines the problem coefficients to mitigate the adverse effects of QA hardware noise. We evaluate our proposed QA based VPP (QAVP) technique on a real Quantum Annealing device over a variety of design and machine parameter settings. With existing hardware, QAVP can achieve a BER of $10^{-4}$ with 100$μ$s compute time, for a 6$\times$6 MIMO system using 64 QAM modulation at 32 dB SNR.
Triplet loss based embeddings for forensic speaker identification in Spanish
Venue: arXiv cs.SD 2021
Year: 2021

With the advent of digital technology, it is more common that committed crimes or legal disputes involve some form of speech recording where the identity of a speaker is questioned [1]. In face of this situation, the field of forensic speaker identification has been looking to shed light on the problem by quantifying how much a speech recording belongs to a particular person in relation to a population. In this work, we explore the use of speech embeddings obtained by training a CNN using the triplet loss. In particular, we focus on the Spanish language which has not been extensively studies. We propose extracting the embeddings from speech spectrograms samples, then explore several configurations of such spectrograms, and finally, quantify the embeddings quality. We also show some limitations of our data setting which is predominantly composed by male speakers. At the end, we propose two approaches to calculate the Likelihood Radio given out speech embeddings and we show that triplet loss is a good alternative to create speech embeddings for forensic speaker identification.
Deep Compact Polyhedral Conic Classifier for Open and Closed Set Recognition
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose a new deep neural network classifier that simultaneously maximizes the inter-class separation and minimizes the intra-class variation by using the polyhedral conic classification function. The proposed method has one loss term that allows the margin maximization to maximize the inter-class separation and another loss term that controls the compactness of the class acceptance regions. Our proposed method has a nice geometric interpretation using polyhedral conic function geometry. We tested the proposed method on various visual classification problems including closed/open set recognition and anomaly detection. The experimental results show that the proposed method typically outperforms other state-of-the art methods, and becomes a better choice compared to other tested methods especially for open set recognition type problems.
Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with $\sqrt{T}$ Regret
Venue: arXiv cs.LG 2021
Year: 2021

We consider the task of learning to control a linear dynamical system under fixed quadratic costs, known as the Linear Quadratic Regulator (LQR) problem. While model-free approaches are often favorable in practice, thus far only model-based methods, which rely on costly system identification, have been shown to achieve regret that scales with the optimal dependence on the time horizon T. We present the first model-free algorithm that achieves similar regret guarantees. Our method relies on an efficient policy gradient scheme, and a novel and tighter analysis of the cost of exploration in policy space in this setting.