OpenRaiser/Intern-Atlas huggingface dataset:
Measuring Data Collection Diligence for Community Healthcare
Venue: arXiv cs.LG 2021
Year: 2021

Data analytics has tremendous potential to provide targeted benefit in low-resource communities, however the availability of high-quality public health data is a significant challenge in developing countries primarily due to non-diligent data collection by community health workers (CHWs). In this work, we define and test a data collection diligence score. This challenging unlabeled data problem is handled by building upon domain expert's guidance to design a useful data representation of the raw data, using which we design a simple and natural score. An important aspect of the score is relative scoring of the CHWs, which implicitly takes into account the context of the local area. The data is also clustered and interpreting these clusters provides a natural explanation of the past behavior of each data collector. We further predict the diligence score for future time steps. Our framework has been validated on the ground using observations by the field monitors of our partner NGO in India. Beyond the successful field test, our work is in the final stages of deployment in the state of Rajasthan, India.
Minimax Group Fairness: Algorithms and Experiments
Venue: arXiv cs.LG 2021
Year: 2021

We consider a recently introduced framework in which fairness is measured by worst-case outcomes across groups, rather than by the more standard differences between group outcomes. In this framework we provide provably convergent oracle-efficient learning algorithms (or equivalently, reductions to non-fair learning) for minimax group fairness. Here the goal is that of minimizing the maximum loss across all groups, rather than equalizing group losses. Our algorithms apply to both regression and classification settings and support both overall error and false positive or false negative rates as the fairness measure of interest. They also support relaxations of the fairness constraints, thus permitting study of the tradeoff between overall accuracy and minimax fairness. We compare the experimental behavior and performance of our algorithms across a variety of fairness-sensitive data sets and show empirical cases in which minimax fairness is strictly and strongly preferable to equal outcome notions.
Group isomorphism is nearly-linear time for most orders
Venue: arXiv cs.CC 2021
Year: 2021

We show that there is a dense set $\ourset\subseteq \mathbb{N}$ of group orders and a constant $c$ such that for every $n\in \ourset$ we can decide in time $O(n^2(\log n)^c)$ whether two $n\times n$ multiplication tables describe isomorphic groups of order $n$. This improves significantly over the general $n^{O(\log n)}$-time complexity and shows that group isomorphism can be tested efficiently for almost all group orders $n$. We also show that in time $O(n^2 (\log n)^c)$ it can be decided whether an $n\times n$ multiplication table describes a group; this improves over the known $O(n^3)$ complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model. We give the implications to a RAM model in the promise hierarchy as well.
5G Embraces Satellites for 6G Ubiquitous IoT: Basic Models for Integrated Satellite Terrestrial Networks
Venue: arXiv cs.IT 2021
Year: 2021

Terrestrial communication networks mainly focus on users in urban areas but have poor coverage performance in harsh environments, such as mountains, deserts, and oceans. Satellites can be exploited to extend the coverage of terrestrial fifth-generation (5G) networks. However, satellites are restricted by their high latency and relatively low data rate. Consequently, the integration of terrestrial and satellite components has been widely studied, to take advantage of both sides and enable seamless broadband coverage. Due to the significant differences between satellite communications (SatComs) and terrestrial communications (TerComs) in terms of channel fading, transmission delay, mobility, and coverage performance, the establishment of an efficient hybrid satellite-terrestrial network (HSTN) still faces many challenges. In general, it is difficult to decompose a HSTN into a sum of separate satellite and terrestrial links due to the complicated coupling relationships therein. To uncover the complete picture of HSTNs, we regard the HSTN as a combination of basic cooperative models that contain the main traits of satellite-terrestrial integration but are much simpler and thus more tractable than the large-scale heterogeneous HSTNs. In particular, we present three basic cooperative models, i.e., model X, model L, and model V, and provide a survey of the state-of-the-art technologies for each of them. We discuss future research directions towards establishing a cell-free, hierarchical, decoupled HSTN. We also outline open issues to envision an agile, smart, and secure HSTN for the sixth-generation (6G) ubiquitous Internet of Things (IoT).
Deep Cross-modal Hashing via Margin-dynamic-softmax Loss
Venue: arXiv cs.CV 2021
Year: 2021

Due to their high retrieval efficiency and low storage cost for cross-modal search task, cross-modal hashing methods have attracted considerable attention. For the supervised cross-modal hashing methods, how to make the learned hash codes preserve semantic information sufficiently contained in the label of datapoints is the key to further enhance the retrieval performance. Hence, almost all supervised cross-modal hashing methods usually depends on defining a similarity between datapoints with the label information to guide the hashing model learning fully or partly. However, the defined similarity between datapoints can only capture the label information of datapoints partially and misses abundant semantic information, then hinders the further improvement of retrieval performance. Thus, in this paper, different from previous works, we propose a novel cross-modal hashing method without defining the similarity between datapoints, called Deep Cross-modal Hashing via \textit{Margin-dynamic-softmax Loss} (DCHML). Specifically, DCHML first trains a proxy hashing network to transform each category information of a dataset into a semantic discriminative hash code, called proxy hash code. Each proxy hash code can preserve the semantic information of its corresponding category well. Next, without defining the similarity between datapoints to supervise the training process of the modality-specific hashing networks , we propose a novel \textit{margin-dynamic-softmax loss} to directly utilize the proxy hashing codes as supervised information. Finally, by minimizing the novel \textit{margin-dynamic-softmax loss}, the modality-specific hashing networks can be trained to generate hash codes which can simultaneously preserve the cross-modal similarity and abundant semantic information well.
Text-to-Image Generation Grounded by Fine-Grained User Attention
Venue: arXiv cs.CV 2021
Year: 2021

Localized Narratives is a dataset with detailed natural language descriptions of images paired with mouse traces that provide a sparse, fine-grained visual grounding for phrases. We propose TReCS, a sequential model that exploits this grounding to generate images. TReCS uses descriptions to retrieve segmentation masks and predict object labels aligned with mouse traces. These alignments are used to select and position masks to generate a fully covered segmentation canvas; the final image is produced by a segmentation-to-image generator using this canvas. This multi-step, retrieval-based approach outperforms existing direct text-to-image generation models on both automatic metrics and human evaluations: overall, its generated images are more photo-realistic and better match descriptions.
On the spatial attention in Spatio-Temporal Graph Convolutional Networks for skeleton-based human action recognition
Venue: arXiv cs.CV 2021
Year: 2021

Graph convolutional networks (GCNs) achieved promising performance in skeleton-based human action recognition by modeling a sequence of skeletons as a spatio-temporal graph. Most of the recently proposed GCN-based methods improve the performance by learning the graph structure at each layer of the network using a spatial attention applied on a predefined graph Adjacency matrix that is optimized jointly with model's parameters in an end-to-end manner. In this paper, we analyze the spatial attention used in spatio-temporal GCN layers and propose a symmetric spatial attention for better reflecting the symmetric property of the relative positions of the human body joints when executing actions. We also highlight the connection of spatio-temporal GCN layers employing additive spatial attention to bilinear layers, and we propose the spatio-temporal bilinear network (ST-BLN) which does not require the use of predefined Adjacency matrices and allows for more flexible design of the model. Experimental results show that the three models lead to effectively the same performance. Moreover, by exploiting the flexibility provided by the proposed ST-BLN, one can increase the efficiency of the model.
Point Transformer for Shape Classification and Retrieval of 3D and ALS Roof PointClouds
Venue: arXiv cs.CV 2021
Year: 2021

The success of deep learning methods led to significant breakthroughs in 3-D point cloud processing tasks with applications in remote sensing. Existing methods utilize convolutions that have some limitations, as they assume a uniform input distribution and cannot learn long-range dependencies. Recent works have shown that adding attention in conjunction with these methods improves performance. This raises a question: can attention layers completely replace convolutions? This paper proposes a fully attentional model - {\em Point Transformer}, for deriving a rich point cloud representation. The model's shape classification and retrieval performance are evaluated on a large-scale urban dataset - RoofN3D and a standard benchmark dataset ModelNet40. Extensive experiments are conducted to test the model's robustness to unseen point corruptions for analyzing its effectiveness on real datasets. The proposed method outperforms other state-of-the-art models in the RoofN3D dataset, gives competitive results in the ModelNet40 benchmark, and showcases high robustness to various unseen point corruptions. Furthermore, the model is highly memory and space efficient when compared to other methods.
Multi-Temporal Convolutions for Human Action Recognition in Videos
Venue: arXiv cs.CV 2021
Year: 2021

Effective extraction of temporal patterns is crucial for the recognition of temporally varying actions in video. We argue that the fixed-sized spatio-temporal convolution kernels used in convolutional neural networks (CNNs) can be improved to extract informative motions that are executed at different time scales. To address this challenge, we present a novel spatio-temporal convolution block that is capable of extracting spatio-temporal patterns at multiple temporal resolutions. Our proposed multi-temporal convolution (MTConv) blocks utilize two branches that focus on brief and prolonged spatio-temporal patterns, respectively. The extracted time-varying features are aligned in a third branch, with respect to global motion patterns through recurrent cells. The proposed blocks are lightweight and can be integrated into any 3D-CNN architecture. This introduces a substantial reduction in computational costs. Extensive experiments on Kinetics, Moments in Time and HACS action recognition benchmark datasets demonstrate competitive performance of MTConvs compared to the state-of-the-art with a significantly lower computational footprint.
Online Sparse Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear Markov decision process (MDP), with a special focus on the high-dimensional regime where the ambient dimension is larger than the number of episodes. Our contribution is two-fold. First, we provide a lower bound showing that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. The lower bound construction uses an MDP with a fixed number of states while the number of actions scales with the ambient dimension. Note that when the horizon is fixed to one, the case of linear stochastic bandits, the linear regret can be avoided. Second, we show that if the learner has oracle access to a policy that collects well-conditioned data then a variant of Lasso fitted Q-iteration enjoys a nearly dimension-free regret of $\tilde{O}( s^{2/3} N^{2/3})$ where $N$ is the number of episodes and $s$ is the sparsity level. This shows that in the large-action setting, the difficulty of learning can be attributed to the difficulty of finding a good exploratory policy.
Fourier-based and Rational Graph Filters for Spectral Processing
Venue: arXiv cs.LG 2021
Year: 2021

Data are represented as graphs in a wide range of applications, such as Computer Vision (e.g., images) and Graphics (e.g., 3D meshes), network analysis (e.g., social networks), and bio-informatics (e.g., molecules). In this context, our overall goal is the definition of novel Fourier-based and graph filters induced by rational polynomials for graph processing, which generalise polynomial filters and the Fourier transform to non-Euclidean domains. For the efficient evaluation of discrete spectral Fourier-based and wavelet operators, we introduce a spectrum-free approach, which requires the solution of a small set of sparse, symmetric, well-conditioned linear systems and is oblivious of the evaluation of the Laplacian or kernel spectrum. Approximating arbitrary graph filters with rational polynomials provides a more accurate and numerically stable alternative with respect to polynomials. To achieve these goals, we also study the link between spectral operators, wavelets, and filtered convolution with integral operators induced by spectral kernels. According to our tests, main advantages of the proposed approach are (i) its generality with respect to the input data (e.g., graphs, 3D shapes), applications (e.g., signal reconstruction and smoothing, shape correspondence), and filters (e.g., polynomial, rational polynomial), and (ii) a spectrum-free computation with a generally low computational cost and storage overhead.
On the classification of quaternary optimal Hermitian LCD codes
Venue: arXiv cs.IT 2021
Year: 2021

We propose a method for a classification of quaternary Hermitian LCD codes having large minimum weights. As an example, we give a classification of quaternary optimal Hermitian LCD codes of dimension 3.
Optimal Predefined-time Trajectory Planning for a Free-floating Space Robot
Venue: arXiv cs.RO 2021
Year: 2021

With the development of human space exploration, the space environment is gradually filled with abandoned satellite debris and unknown micrometeorites, which will seriously affect capture motion of space robot. Hence, a novel fast collision-avoidance trajectory planning strategy for a dual-arm free-floating space robot (FFSR) with predefined-time pose feedback will be mainly studied to achieve micron-level tracking accuracy of end-effector in this paper. However, similar to control, the exponential feedback results in larger initial joint angular velocity relative to proportional feedback. Firstly, a pose-error-based kinematic model of the FFSR will be derived from a control perspective. Then, a cumulative dangerous field (CDF) collision-avoidance algorithm is applied in predefined-time trajectory planning to achieve micron-level collision-avoidance trajectory tracking precision. In the end, a GA-based optimization algorithm is used to optimize the predefined-time parameter to obtain a motion trajectory of low joint angular velocity of robotic arms. The simulation results verify our conjecture and conclusion.
Mitigating Bias in Set Selection with Noisy Protected Attributes
Venue: arXiv cs.CY 2021
Year: 2021

Subset selection algorithms are ubiquitous in AI-driven applications, including, online recruiting portals and image search engines, so it is imperative that these tools are not discriminatory on the basis of protected attributes such as gender or race. Currently, fair subset selection algorithms assume that the protected attributes are known as part of the dataset. However, protected attributes may be noisy due to errors during data collection or if they are imputed (as is often the case in real-world settings). While a wide body of work addresses the effect of noise on the performance of machine learning algorithms, its effect on fairness remains largely unexamined. We find that in the presence of noisy protected attributes, in attempting to increase fairness without considering noise, one can, in fact, decrease the fairness of the result! Towards addressing this, we consider an existing noise model in which there is probabilistic information about the protected attributes (e.g., [58, 34, 20, 46]), and ask is fair selection possible under noisy conditions? We formulate a ``denoised'' selection problem which functions for a large class of fairness metrics; given the desired fairness goal, the solution to the denoised problem violates the goal by at most a small multiplicative amount with high probability. Although this denoised problem turns out to be NP-hard, we give a linear-programming based approximation algorithm for it. We evaluate this approach on both synthetic and real-world datasets. Our empirical results show that this approach can produce subsets which significantly improve the fairness metrics despite the presence of noisy protected attributes, and, compared to prior noise-oblivious approaches, has better Pareto-tradeoffs between utility and fairness.
TTVOS: Lightweight Video Object Segmentation with Adaptive Template Attention Module and Temporal Consistency Loss
Venue: arXiv cs.CV 2021
Year: 2021

Semi-supervised video object segmentation (semi-VOS) is widely used in many applications. This task is tracking class-agnostic objects from a given target mask. For doing this, various approaches have been developed based on online-learning, memory networks, and optical flow. These methods show high accuracy but are hard to be utilized in real-world applications due to slow inference time and tremendous complexity. To resolve this problem, template matching methods are devised for fast processing speed but sacrificing lots of performance in previous models. We introduce a novel semi-VOS model based on a template matching method and a temporal consistency loss to reduce the performance gap from heavy models while expediting inference time a lot. Our template matching method consists of short-term and long-term matching. The short-term matching enhances target object localization, while long-term matching improves fine details and handles object shape-changing through the newly proposed adaptive template attention module. However, the long-term matching causes error-propagation due to the inflow of the past estimated results when updating the template. To mitigate this problem, we also propose a temporal consistency loss for better temporal coherence between neighboring frames by adopting the concept of a transition matrix. Our model obtains 79.5% J&F score at the speed of 73.8 FPS on the DAVIS16 benchmark. The code is available in https://github.com/HYOJINPARK/TTVOS.
Reduced-Rank Regression with Operator Norm Error
Venue: arXiv cs.DS 2021
Year: 2021

A common data analysis task is the reduced-rank regression problem: $$\min_{\textrm{rank-}k \ X} \|AX-B\|,$$ where $A \in \mathbb{R}^{n \times c}$ and $B \in \mathbb{R}^{n \times d}$ are given large matrices and $\|\cdot\|$ is some norm. Here the unknown matrix $X \in \mathbb{R}^{c \times d}$ is constrained to be of rank $k$ as it results in a significant parameter reduction of the solution when $c$ and $d$ are large. In the case of Frobenius norm error, there is a standard closed form solution to this problem and a fast algorithm to find a $(1+\varepsilon)$-approximate solution. However, for the important case of operator norm error, no closed form solution is known and the fastest known algorithms take singular value decomposition time. We give the first randomized algorithms for this problem running in time $$(nnz{(A)} + nnz{(B)} + c^2) \cdot k/\varepsilon^{1.5} + (n+d)k^2/ε+ c^ω,$$ up to a polylogarithmic factor involving condition numbers, matrix dimensions, and dependence on $1/\varepsilon$. Here $nnz{(M)}$ denotes the number of non-zero entries of a matrix $M$, and $ω$ is the exponent of matrix multiplication. As both (1) spectral low rank approximation ($A = B$) and (2) linear system solving ($n = c$ and $d = 1$) are special cases, our time cannot be improved by more than a $1/\varepsilon$ factor (up to polylogarithmic factors) without a major breakthrough in linear algebra. Interestingly, known techniques for low rank approximation, such as alternating minimization or sketch-and-solve, provably fail for this problem. Instead, our algorithm uses an existential characterization of a solution, together with Krylov methods, low degree polynomial approximation, and sketching-based preconditioning.
On the hardness of code equivalence problems in rank metric
Venue: arXiv cs.IT 2021
Year: 2021

In the recent years, the notion of rank metric in the context of coding theory has known many interesting developments in terms of applications such as space time coding, network coding or public key cryptography. These applications raised the interest of the community for theoretical properties of this type of codes, such as the hardness of decoding in rank metric. Among classical problems associated to codes for a given metric, the notion of code equivalence (to decide if two codes are isometric) has always been of the greatest interest, for its cryptographic applications or its deep connexions to the graph isomorphism problem. In this article, we discuss the hardness of the code equivalence problem in rank metric for $\mathbb{F}_{q^m}$-linear and general rank metric codes. In the $\mathbb{F}_{q^m}$-linear case, we reduce the underlying problem to another one called {\em Matrix Codes Right Equivalence Problem}. We prove the latter problem to be either in $\mathcal{P}$ or in $\mathcal{ZPP}$ depending of the ground field size. This is obtained by designing an algorithm whose principal routines are linear algebra and factoring polynomials over finite fields. It turns out that the most difficult instances involve codes with non trivial {\em stabilizer algebras}. The resolution of the latter case will involve tools related to finite dimensional algebras and Wedderburn--Artin theory. It is interesting to note that 30 years ago, an important trend in theoretical computer science consisted to design algorithms making effective major results of this theory. These algorithmic results turn out to be particularly useful in the present article. Finally, for general matrix codes, we prove that the equivalence problem (both left and right) is at least as hard as the well--studied {\em Monomial Equivalence Problem} for codes endowed with the Hamming metric.