OpenRaiser/Intern-Atlas huggingface dataset:
Channel Inclusion Beyond Discrete Memoryless Channels
Venue: arXiv cs.IT 2021
Year: 2021

Partial ordering of communication channels has applications in performance analysis, and goes beyond comparisons of channels just on the basis of their Shannon capacity or error probability. Shannon defined a partial order of channel inclusion based on convex mixture of input/output degradations of a discrete memoryless channel (DMC). In this paper, extensions to channels other than DMCs are considered. In particular, additive noise channels and phase degraded channels, and multiple input multiple output (MIMO) linear Gaussian channels (LGC) are considered. For each of these models, the conditions under which the partial order becomes a lattice are also discussed.
Iterative Human and Automated Identification of Wildlife Images
Venue: arXiv cs.CV 2021
Year: 2021

Camera trapping is increasingly used to monitor wildlife, but this technology typically requires extensive data annotation. Recently, deep learning has significantly advanced automatic wildlife recognition. However, current methods are hampered by a dependence on large static data sets when wildlife data is intrinsically dynamic and involves long-tailed distributions. These two drawbacks can be overcome through a hybrid combination of machine learning and humans in the loop. Our proposed iterative human and automated identification approach is capable of learning from wildlife imagery data with a long-tailed distribution. Additionally, it includes self-updating learning that facilitates capturing the community dynamics of rapidly changing natural systems. Extensive experiments show that our approach can achieve a ~90% accuracy employing only ~20% of the human annotations of existing approaches. Our synergistic collaboration of humans and machines transforms deep learning from a relatively inefficient post-annotation tool to a collaborative on-going annotation tool that vastly relieves the burden of human annotation and enables efficient and constant model updates.
Universal Algorithms for Clustering Problems
Venue: arXiv cs.DS 2021
Year: 2021

This paper presents universal algorithms for clustering problems, including the widely studied $k$-median, $k$-means, and $k$-center objectives. The input is a metric space containing all potential client locations. The algorithm must select $k$ cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm's solution and that of an optimal solution. A universal algorithm's solution $SOL$ for a clustering problem is said to be an $(α, β)$-approximation if for all subsets of clients $C'$, it satisfies $SOL(C') \leq α\cdot OPT(C') + β\cdot MR$, where $OPT(C')$ is the cost of the optimal solution for clients $C'$ and $MR$ is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of $k$-median, $k$-means, and $k$-center that achieve $(O(1), O(1))$-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other $\ell_p$-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that $(α, β)$-approximation is NP-hard if $α$ or $β$ is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, $(O(1), O(1))$-approximation is the strongest type of guarantee obtainable for universal clustering.
Reconfiguring Diversity and Inclusion for AI Ethics
Venue: arXiv cs.CY 2021
Year: 2021

Activists, journalists, and scholars have long raised critical questions about the relationship between diversity, representation, and structural exclusions in data-intensive tools and services. We build on work mapping the emergent landscape of corporate AI ethics to center one outcome of these conversations: the incorporation of diversity and inclusion in corporate AI ethics activities. Using interpretive document analysis and analytic tools from the values in design field, we examine how diversity and inclusion work is articulated in public-facing AI ethics documentation produced by three companies that create application and services layer AI infrastructure: Google, Microsoft, and Salesforce. We find that as these documents make diversity and inclusion more tractable to engineers and technical clients, they reveal a drift away from civil rights justifications that resonates with the managerialization of diversity by corporations in the mid-1980s. The focus on technical artifacts, such as diverse and inclusive datasets, and the replacement of equity with fairness make ethical work more actionable for everyday practitioners. Yet, they appear divorced from broader DEI initiatives and other subject matter experts that could provide needed context to nuanced decisions around how to operationalize these values. Finally, diversity and inclusion, as configured by engineering logic, positions firms not as ethics owners but as ethics allocators; while these companies claim expertise on AI ethics, the responsibility of defining who diversity and inclusion are meant to protect and where it is relevant is pushed downstream to their customers.
Person Retrieval in Surveillance Using Textual Query: A Review
Venue: arXiv cs.CV 2021
Year: 2021

Recent advancement of research in biometrics, computer vision, and natural language processing has discovered opportunities for person retrieval from surveillance videos using textual query. The prime objective of a surveillance system is to locate a person using a description, e.g., a short woman with a pink t-shirt and white skirt carrying a black purse. She has brown hair. Such a description contains attributes like gender, height, type of clothing, colour of clothing, hair colour, and accessories. Such attributes are formally known as soft biometrics. They help bridge the semantic gap between a human description and a machine as a textual query contains the person's soft biometric attributes. It is also not feasible to manually search through huge volumes of surveillance footage to retrieve a specific person. Hence, automatic person retrieval using vision and language-based algorithms is becoming popular. In comparison to other state-of-the-art reviews, the contribution of the paper is as follows: 1. Recommends most discriminative soft biometrics for specifiic challenging conditions. 2. Integrates benchmark datasets and retrieval methods for objective performance evaluation. 3. A complete snapshot of techniques based on features, classifiers, number of soft biometric attributes, type of the deep neural networks, and performance measures. 4. The comprehensive coverage of person retrieval from handcrafted features based methods to end-to-end approaches based on natural language description.
Faster Algorithms for Bounded Tree Edit Distance
Venue: arXiv cs.DS 2021
Year: 2021

Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in $O(n^3)$ time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007], and fine-grained hardness results suggest that the weighted version of this problem cannot be solved in truly subcubic time unless the APSP conjecture is false [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. We consider the unweighted version of tree edit distance, where every insertion, deletion, or relabeling operation has unit cost. Given a parameter $k$ as an upper bound on the distance, the previous fastest algorithm for this problem runs in $O(nk^3)$ time [Touzet, CPM 2005], which improves upon the cubic-time algorithm for $k\ll n^{2/3}$. In this paper, we give a faster algorithm taking $O(nk^2 \log n)$ time, improving both of the previous results for almost the full range of $\log n \ll k\ll n/\sqrt{\log n}$.
Attestation Waves: Platform Trust via Remote Power Analysis
Venue: arXiv cs.CR 2021
Year: 2021

Attestation is a strong tool to verify the integrity of an untrusted system. However, in recent years, different attacks have appeared that are able to mislead the attestation process with treacherous practices as memory copy, proxy, and rootkit attacks, just to name a few. A successful attack leads to systems that are considered trusted by a verifier system, while the prover has bypassed the challenge. To mitigate these attacks against attestation methods and protocols, some proposals have considered the use of side-channel information that can be measured externally, as it is the case of electromagnetic (EM) emanation. Nonetheless, these methods require the physical proximity of an external setup to capture the EM radiation. In this paper, we present the possibility of performing attestation by using the side-channel information captured by a sensor or peripheral that lives in the same System-on-Chip (SoC) than the processor system (PS) which executes the operation that we aim to attest, by only sharing the Power Distribution Network (PDN). In our case, an analog-to-digital converter (ADC) that captures the voltage fluctuations at its input terminal while a certain operation is taking place is suitable to characterize itself and to distinguish it from other binaries. The resultant power traces are enough to clearly identify a given operation without the requirement of physical proximity.
XeroAlign: Zero-Shot Cross-lingual Transformer Alignment
Venue: arXiv cs.CL 2021
Year: 2021

The introduction of pretrained cross-lingual language models brought decisive improvements to multilingual NLP tasks. However, the lack of labelled task data necessitates a variety of methods aiming to close the gap to high-resource languages. Zero-shot methods in particular, often use translated task data as a training signal to bridge the performance gap between the source and target language(s). We introduce XeroAlign, a simple method for task-specific alignment of cross-lingual pretrained transformers such as XLM-R. XeroAlign uses translated task data to encourage the model to generate similar sentence embeddings for different languages. The XeroAligned XLM-R, called XLM-RA, shows strong improvements over the baseline models to achieve state-of-the-art zero-shot results on three multilingual natural language understanding tasks. XLM-RA's text classification accuracy exceeds that of XLM-R trained with labelled data and performs on par with state-of-the-art models on a cross-lingual adversarial paraphrasing task.
PH-CPF: Planar Hexagonal Meshing using Coordinate Power Fields
Venue: arXiv cs.GR 2021
Year: 2021

We present a new approach for computing planar hexagonal meshes that approximate a given surface, represented as a triangle mesh. Our method is based on two novel technical contributions. First, we introduce Coordinate Power Fields, which are a pair of tangent vector fields on the surface that fulfill a certain continuity constraint. We prove that the fulfillment of this constraint guarantees the existence of a seamless parameterization with quantized rotational jumps, which we then use to regularly remesh the surface. We additionally propose an optimization framework for finding Coordinate Power Fields, which also fulfill additional constraints, such as alignment, sizing and bijectivity. Second, we build upon this framework to address a challenging meshing problem: planar hexagonal meshing. To this end, we suggest a combination of conjugacy, scaling and alignment constraints, which together lead to planarizable hexagons. We demonstrate our approach on a variety of surfaces, automatically generating planar hexagonal meshes on complicated meshes, which were not achievable with existing methods.
A model for cooperative scientific research inspired by the ant colony algorithm
Venue: arXiv cs.DL 2021
Year: 2021

Modern scientific research has become largely a cooperative activity in the Internet age. We build a simulation model to understand the population-level creativity based on the heuristic ant colony algorithm. Each researcher has two heuristic parameters characterizing the goodness of his own judgments and his trust on literature. In a population with all kinds of researchers, we find that as the problem scale increases, the contributor distribution significantly shifts from the independent regime of relying on one's own judgments to the cooperative regime of more closely following the literature. The distribution also changes with the stage of the research problem and the computing power available. Our work provides some preliminary understanding and guidance for the dynamical process of cooperative scientific research in various disciplines.
Time-Aware Q-Networks: Resolving Temporal Irregularity for Deep Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Deep Reinforcement Learning (DRL) has shown outstanding performance on inducing effective action policies that maximize expected long-term return on many complex tasks. Much of DRL work has been focused on sequences of events with discrete time steps and ignores the irregular time intervals between consecutive events. Given that in many real-world domains, data often consists of temporal sequences with irregular time intervals, and it is important to consider the time intervals between temporal events to capture latent progressive patterns of states. In this work, we present a general Time-Aware RL framework: Time-aware Q-Networks (TQN), which takes into account physical time intervals within a deep RL framework. TQN deals with time irregularity from two aspects: 1) elapsed time in the past and an expected next observation time for time-aware state approximation, and 2) action time window for the future for time-aware discounting of rewards. Experimental results show that by capturing the underlying structures in the sequences with time irregularities from both aspects, TQNs significantly outperform DQN in four types of contexts with irregular time intervals. More specifically, our results show that in classic RL tasks such as CartPole and MountainCar and Atari benchmark with randomly segmented time intervals, time-aware discounting alone is more important while in the real-world tasks such as nuclear reactor operation and septic patient treatment with intrinsic time intervals, both time-aware state and time-aware discounting are crucial. Moreover, to improve the agent's learning capacity, we explored three boosting methods: Double networks, Dueling networks, and Prioritized Experience Replay, and our results show that for the two real-world tasks, combining all three boosting methods with TQN is especially effective.
Optimal Subgraph on Disturbed Network
Venue: arXiv cs.DM 2021
Year: 2021

During the pandemic of COVID-19, the demand of the transportation systems are drastically changed both qualitatively and quantitatively and the network has become obsolete. In this article, we study the problem of finding an optimal subnetwork that guarantee that (i) the minimal access time from any node of the urban network to the new network is not {\em too large} compared to the original transportation network; (ii) for any itinerary, the delay caused by the deletion of nodes of the transportation network is not {\em too big}; and (iii) the number of nodes of the transportation network has been reduced at least by a known factor. A solution is optimal if it induces a minimal global delay. We model this problem as a Mixed Integer Linear Program before applying the model on a real-case application on the Lyon's buses transportation network.
How UAVs' Highly Dynamic 3D Movement Improves Network Security?
Venue: arXiv cs.CR 2021
Year: 2021

Cooperative ad hoc unmanned aerial vehicle (UAV) networks need essential security services to ensure their communication security. Cryptography, as the inseparable tool for providing security services, requires a robust key management system. Alas, the absence of infrastructure in cooperative networks leads to the infeasibility of providing conventional key management systems. Key pre-distribution schemes have shown promising performance in different cooperative networks due to their lightweight nature. However, intermediate decryption-encryption (DE) steps and the lack of key updates are the most concerning issues they suffer from. In this paper, we propose a simple and effective key management algorithm inspired by the idea of key pre-distribution, where it utilizes the highly dynamic UAV node movement in 3D space to provide the key update feature and optimizes the number of intermediate DE steps. Although it is a general model for any mobile ad hoc network, we have selected UAV network as an example domain to show the efficiency of the model given the high mobility. We define the communication density parameter to analytically show that using any highly dynamic random movement pattern leads our algorithm to work effectively. To show the proposed algorithm's effectiveness, we exhaustively analyze its security and performance in the UAV network using the ns-3 network simulator. Results validate our analytical findings and show how the highly dynamic UAV network movement helps our algorithm to provide the key update feature and to optimize the number of DE steps.
Searching by Heterogeneous Agents
Venue: arXiv cs.DM 2021
Year: 2021

In this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs: once a search strategy initially assigns labels to the searchers, each searcher can be only present on an edge of its own label. We prove that this problem is not monotone even for trees and we give instances in which the number of recontamination events is asymptotically quadratic in the tree size. Other negative results regard the NP-completeness of the monotone, and NP-hardness of an arbitrary (i.e., non-monotone) heterogeneous search in trees. These properties show that this problem behaves very differently from the classical edge search. On the other hand, if all edges of a particular label form a (connected) subtree of the input tree, then we show that optimal heterogeneous search strategy can be computed efficiently.
Quantum Logarithmic Space and Post-selection
Venue: arXiv cs.CC 2021
Year: 2021

Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005). In the present paper, we initiate the study of post-selection for space-bounded quantum complexity classes. Our main result shows the identity $\sf PostBQL=PL$, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection ($\sf PostBQL$) is equal to the class of problems that can be solved by unbounded-error logarithmic-space classical algorithms ($\sf PL$). This result gives a space-bounded version of the well-known result $\sf PostBQP=PP$ proved by Aaronson for polynomial-time quantum computation. As a by-product, we also show that $\sf PL$ coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
Uncertainty-aware INVASE: Enhanced Breast Cancer Diagnosis Feature Selection
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we present an uncertainty-aware INVASE to quantify predictive confidence of healthcare problem. By introducing learnable Gaussian distributions, we lever-age their variances to measure the degree of uncertainty. Based on the vanilla INVASE, two additional modules are proposed, i.e., an uncertainty quantification module in the predictor, and a reward shaping module in the selector. We conduct extensive experiments on UCI-WDBC dataset. Notably, our method eliminates almost all predictive bias with only about 20% queries, while the uncertainty-agnostic counterpart requires nearly 100% queries. The open-source implementation with a detailed tutorial is available at https://github.com/jx-zhong-for-academic-purpose/Uncertainty-aware-INVASE/blob/main/tutorialinvase%2B.ipynb.
MIMII DUE: Sound Dataset for Malfunctioning Industrial Machine Investigation and Inspection with Domain Shifts due to Changes in Operational and Environmental Conditions
Venue: arXiv cs.SD 2021
Year: 2021

In this paper, we introduce MIMII DUE, a new dataset for malfunctioning industrial machine investigation and inspection with domain shifts due to changes in operational and environmental conditions. Conventional methods for anomalous sound detection face practical challenges because the distribution of features changes between the training and operational phases (called domain shift) due to various real-world factors. To check the robustness against domain shifts, we need a dataset that actually includes domain shifts, but such a dataset does not exist so far. The new dataset we created consists of the normal and abnormal operating sounds of five different types of industrial machines under two different operational/environmental conditions (source domain and target domain) independent of normal/abnormal, with domain shifts occurring between the two domains. Experimental results showed significant performance differences between the source and target domains, indicating that the dataset contains the domain shifts. These findings demonstrate that the dataset will be helpful for checking the robustness against domain shifts. The dataset is a subset of the dataset for DCASE 2021 Challenge Task 2 and freely available for download at https://zenodo.org/record/4740355
Heterogeneous Facility Location with Limited Resources
Venue: arXiv cs.GT 2021
Year: 2021

We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0,1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.
Digital Voodoo Dolls
Venue: arXiv cs.CY 2021
Year: 2021

An institution, be it a body of government, commercial enterprise, or a service, cannot interact directly with a person. Instead, a model is created to represent us. We argue the existence of a new high-fidelity type of person model which we call a digital voodoo doll. We conceptualize it and compare its features with existing models of persons. Digital voodoo dolls are distinguished by existing completely beyond the influence and control of the person they represent. We discuss the ethical issues that such a lack of accountability creates and argue how these concerns can be mitigated.
Pose-Guided Sign Language Video GAN with Dynamic Lambda
Venue: arXiv cs.CV 2021
Year: 2021

We propose a novel approach for the synthesis of sign language videos using GANs. We extend the previous work of Stoll et al. by using the human semantic parser of the Soft-Gated Warping-GAN from to produce photorealistic videos guided by region-level spatial layouts. Synthesizing target poses improves performance on independent and contrasting signers. Therefore, we have evaluated our system with the highly heterogeneous MS-ASL dataset with over 200 signers resulting in a SSIM of 0.893. Furthermore, we introduce a periodic weighting approach to the generator that reactivates the training and leads to quantitatively better results.