OpenRaiser/Intern-Atlas huggingface dataset:
Focal Inverse Distance Transform Maps for Crowd Localization
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we focus on the crowd localization task, a crucial topic of crowd analysis. Most regression-based methods utilize convolution neural networks (CNN) to regress a density map, which can not accurately locate the instance in the extremely dense scene, attributed to two crucial reasons: 1) the density map consists of a series of blurry Gaussian blobs, 2) severe overlaps exist in the dense region of the density map. To tackle this issue, we propose a novel Focal Inverse Distance Transform (FIDT) map for the crowd localization task. Compared with the density maps, the FIDT maps accurately describe the persons' locations without overlapping in dense regions. Based on the FIDT maps, a Local-Maxima-Detection-Strategy (LMDS) is derived to effectively extract the center point for each individual. Furthermore, we introduce an Independent SSIM (I-SSIM) loss to make the model tend to learn the local structural information, better recognizing local maxima. Extensive experiments demonstrate that the proposed method reports state-of-the-art localization performance on six crowd datasets and one vehicle dataset. Additionally, we find that the proposed method shows superior robustness on the negative and extremely dense scenes, which further verifies the effectiveness of the FIDT maps. The code and model will be available at https://github.com/dk-liang/FIDTM.
Just Noticeable Difference for Deep Machine Vision
Venue: arXiv cs.CV 2022
Year: 2022

As an important perceptual characteristic of the Human Visual System (HVS), the Just Noticeable Difference (JND) has been studied for decades with image and video processing (e.g., perceptual visual signal compression). However, there is little exploration on the existence of JND for the Deep Machine Vision (DMV), although the DMV has made great strides in many machine vision tasks. In this paper, we take an initial attempt, and demonstrate that the DMV has the JND, termed as the DMV-JND. We then propose a JND model for the image classification task in the DMV. It has been discovered that the DMV can tolerate distorted images with average PSNR of only 9.56dB (the lower the better), by generating JND via unsupervised learning with the proposed DMV-JND-NET. In particular, a semantic-guided redundancy assessment strategy is designed to restrain the magnitude and spatial distribution of the DMV-JND. Experimental results on image classification demonstrate that we successfully find the JND for deep machine vision. Our DMV-JND facilitates a possible direction for DMV-oriented image and video compression, watermarking, quality assessment, deep neural network security, and so on.
Evaluating Node Embeddings of Complex Networks
Venue: arXiv cs.SI 2022
Year: 2022

Graph embedding is a transformation of nodes of a graph into a set of vectors. A~good embedding should capture the graph topology, node-to-node relationship, and other relevant information about the graph, its subgraphs, and nodes. If these objectives are achieved, an embedding is a meaningful, understandable, compressed representations of a network that can be used for other machine learning tools such as node classification, community detection, or link prediction. The main challenge is that one needs to make sure that embeddings describe the properties of the graphs well. As a result, selecting the best embedding is a challenging task and very often requires domain experts. In this paper, we do a series of extensive experiments with selected graph embedding algorithms, both on real-world networks as well as artificially generated ones. Based on those experiments we formulate two general conclusions. First, if one needs to pick one embedding algorithm before running the experiments, then node2vec is the best choice as it performed best in our tests. Having said that, there is no single winner in all tests and, additionally, most embedding algorithms have hyperparameters that should be tuned and are randomized. Therefore, our main recommendation for practitioners is, if possible, to generate several embeddings for a problem at hand and then use a general framework that provides a tool for an unsupervised graph embedding comparison. This framework (introduced recently in the literature and easily available on GitHub repository) assigns the divergence score to embeddings to help distinguish good ones from bad ones.
An Information-Theoretic Justification for Model Pruning
Venue: arXiv cs.LG 2022
Year: 2022

We study the neural network (NN) compression problem, viewing the tension between the compression ratio and NN performance through the lens of rate-distortion theory. We choose a distortion metric that reflects the effect of NN compression on the model output and derive the tradeoff between rate (compression) and distortion. In addition to characterizing theoretical limits of NN compression, this formulation shows that \emph{pruning}, implicitly or explicitly, must be a part of a good compression algorithm. This observation bridges a gap between parts of the literature pertaining to NN and data compression, respectively, providing insight into the empirical success of model pruning. Finally, we propose a novel pruning strategy derived from our information-theoretic formulation and show that it outperforms the relevant baselines on CIFAR-10 and ImageNet datasets.
Preventing Oversmoothing in VAE via Generalized Variance Parameterization
Venue: arXiv cs.LG 2022
Year: 2022

Variational autoencoders (VAEs) often suffer from posterior collapse, which is a phenomenon in which the learned latent space becomes uninformative. This is often related to the hyperparameter resembling the data variance. It can be shown that an inappropriate choice of this hyperparameter causes the oversmoothness in the linearly approximated case and can be empirically verified for the general cases. Moreover, determining such appropriate choice becomes infeasible if the data variance is non-uniform or conditional. Therefore, we propose VAE extensions with generalized parameterizations of the data variance and incorporate maximum likelihood estimation into the objective function to adaptively regularize the decoder smoothness. The images generated from proposed VAE extensions show improved Fréchet inception distance (FID) on MNIST and CelebA datasets.
HyMap: eliciting hypotheses in early-stage software startups using cognitive mapping
Venue: arXiv cs.CY 2022
Year: 2022

Context: Software startups develop innovative, software-intensive products. Given the uncertainty associated with such an innovative context, experimentation is a valuable approach for these companies, especially in the early stages of the development, when implementing unnecessary features represents a higher risk for companies' survival. Nevertheless, researchers have argued that the lack of clearly defined practices led to limited adoption of experimentation. In this regard, the first step is to define the hypotheses based on which teams will create experiments. Objective: We aim to develop a systematic technique to identify hypotheses for early-stage software startups. Methods: We followed a Design Science approach consisted of three cycles in the construction phase, that involved seven startups in total, and an evaluation of the final artifact within three startups. Results: We developed the HyMap, a hypotheses elicitation technique based on cognitive mapping. It consists of a visual language to depict a cognitive map representing the founder's understanding of the product, and a process to elicit this map consisted of a series of questions the founder must answer. Our evaluation showed that the artifacts are clear, easy to use, and useful leading to hypotheses and facilitating founders to visualize their idea. Conclusion: Our study contributes to both descriptive and prescriptive bodies of knowledge. Regarding the first, it provides a better understanding of the guidance founders use to develop their startups and, for the latter, a technique to identify hypotheses in early-stage software startups.
Scaling Creative Inspiration with Fine-Grained Functional Aspects of Ideas
Venue: arXiv cs.HC 2022
Year: 2022

Large repositories of products, patents and scientific papers offer an opportunity for building systems that scour millions of ideas and help users discover inspirations. However, idea descriptions are typically in the form of unstructured text, lacking key structure that is required for supporting creative innovation interactions. Prior work has explored idea representations that were either limited in expressivity, required significant manual effort from users, or dependent on curated knowledge bases with poor coverage. We explore a novel representation that automatically breaks up products into fine-grained functional aspects capturing the purposes and mechanisms of ideas, and use it to support important creative innovation interactions: functional search for ideas, and exploration of the design space around a focal problem by viewing related problem perspectives pooled from across many products. In user studies, our approach boosts the quality of creative search and inspirations, substantially outperforming strong baselines by 50-60%.
E(n) Equivariant Graph Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

This paper introduces a new model to learn graph neural networks equivariant to rotations, translations, reflections and permutations called E(n)-Equivariant Graph Neural Networks (EGNNs). In contrast with existing methods, our work does not require computationally expensive higher-order representations in intermediate layers while it still achieves competitive or better performance. In addition, whereas existing methods are limited to equivariance on 3 dimensional spaces, our model is easily scaled to higher-dimensional spaces. We demonstrate the effectiveness of our method on dynamical systems modelling, representation learning in graph autoencoders and predicting molecular properties.
Self-Confidence of Undergraduate Students in Designing Software Architecture
Venue: arXiv cs.SE 2022
Year: 2022

Software architecture students, often, lack self-confidence in their ability to use their knowledge to design software architectures. This paper investigates the relations between undergraduate software architecture students' self-confidence and their course expectations, cognitive levels, preferred learning methods, and critical thinking. We developed a questionnaire with open-ended questions to assess the self-confidence levels and related factors, which was taken by one-hundred ten students in two semesters. The students answers were coded and analyzed afterward. We found that self-confidence is weakly associated with the students' critical thinking and independent from their cognitive levels, preferred learning methods, and expectations from the course. The results suggest that to improve the self-confidence of the students, the instructors should work on improving the students' critical thinking capabilities.
A Tb/s Indoor MIMO Optical Wireless Backhaul System Using VCSEL Arrays
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, the design of a multiple-input multiple-output (MIMO) optical wireless communication (OWC) link based on vertical cavity surface emitting laser (VCSEL) arrays is systematically carried out with the aim to support data rates in excess of 1 Tb/s for the backhaul of sixth generation (6G) indoor wireless networks. The proposed design combines direct current optical orthogonal frequency division multiplexing (DCO-OFDM) and a spatial multiplexing MIMO architecture. For such an ultra-high-speed line-of-sight (LOS) OWC link with low divergence laser beams, maintaining alignment is of high importance. In this paper, two types of misalignment error between the transmitter and receiver are distinguished, namely, radial displacement error and orientation angle error, and they are thoroughly modeled in a unified analytical framework assuming Gaussian laser beams, resulting in a generalized misalignment model (GMM). The derived GMM is then extended to MIMO arrays and the performance of the MIMO-OFDM OWC system is analyzed in terms of the aggregate data rate. Novel insights are provided into the system performance based on computer simulations by studying various influential factors such as beam waist, array configuration and different misalignment errors, which can be used as guidelines for designing short range Tb/s MIMO OWC systems.
Molecular Contrastive Learning of Representations via Graph Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Molecular Machine Learning (ML) bears promise for efficient molecule property prediction and drug discovery. However, labeled molecule data can be expensive and time-consuming to acquire. Due to the limited labeled data, it is a great challenge for supervised-learning ML models to generalize to the giant chemical space. In this work, we present MolCLR: Molecular Contrastive Learning of Representations via Graph Neural Networks (GNNs), a self-supervised learning framework that leverages large unlabeled data (~10M unique molecules). In MolCLR pre-training, we build molecule graphs and develop GNN encoders to learn differentiable representations. Three molecule graph augmentations are proposed: atom masking, bond deletion, and subgraph removal. A contrastive estimator maximizes the agreement of augmentations from the same molecule while minimizing the agreement of different molecules. Experiments show that our contrastive learning framework significantly improves the performance of GNNs on various molecular property benchmarks including both classification and regression tasks. Benefiting from pre-training on the large unlabeled database, MolCLR even achieves state-of-the-art on several challenging benchmarks after fine-tuning. Additionally, further investigations demonstrate that MolCLR learns to embed molecules into representations that can distinguish chemically reasonable molecular similarities.
Fast and Sample-Efficient Federated Low Rank Matrix Recovery from column-wise Linear and Quadratic Projections
Venue: arXiv cs.IT 2022
Year: 2022

We study the following lesser-known low rank (LR) recovery problem: recover an $n \times q$ rank-$r$ matrix, $X^* =[x^*_1 , x^*_2, ..., x^*_q]$, with $r \ll \min(n,q)$, from $m$ independent linear projections of each of its $q$ columns, i.e., from $y_k := A_k x^*_k , k \in [q]$, when $y_k$ is an $m$-length vector with $m < n$. The matrices $A_k$ are known and mutually independent for different $k$. We introduce a novel gradient descent (GD) based solution called AltGD-Min. We show that, if the $A_k$s are i.i.d. with i.i.d. Gaussian entries, and if the right singular vectors of $X^*$ satisfy the incoherence assumption, then $ε$-accurate recovery of $X^*$ is possible with order $(n+q) r^2 \log(1/ε)$ total samples and order $ mq nr \log (1/ε)$ time. Compared with existing work, this is the fastest solution. For $ε< r^{1/4}$, it also has the best sample complexity. A simple extension of AltGD-Min also provably solves LR Phase Retrieval, which is a magnitude-only generalization of the above problem. AltGD-Min factorizes the unknown $X$ as $X = UB$ where $U$ and $B$ are matrices with $r$ columns and rows respectively. It alternates between a (projected) GD step for updating $U$, and a minimization step for updating $B$. Its each iteration is as fast as that of regular projected GD because the minimization over $B$ decouples column-wise. At the same time, we can prove exponential error decay for it, which we are unable to for projected GD. Finally, it can also be efficiently federated with a communication cost of only $nr$ per node, instead of $nq$ for projected GD.
Imitation Learning for Variable Speed Contact Motion for Operation up to Control Bandwidth
Venue: arXiv cs.RO 2022
Year: 2022

The generation of robot motions in the real world is difficult by using conventional controllers alone and requires highly intelligent processing. In this regard, learning-based motion generations are currently being investigated. However, the main issue has been improvements of the adaptability to spatially varying environments, but a variation of the operating speed has not been investigated in detail. In contact-rich tasks, it is especially important to be able to adjust the operating speed because a nonlinear relationship occurs between the operating speed and force (e.g., inertial and frictional forces), and it affects the results of the tasks. Therefore, in this study, we propose a method for generating variable operating speeds while adapting to spatial perturbations in the environment. The proposed method can be adapted to nonlinearities by utilizing a small amount of motion data. We experimentally evaluated the proposed method by erasing a line using an eraser fixed to the tip of the robot as an example of a contact-rich task. Furthermore, the proposed method enables a robot to perform a task faster than a human operator and is capable of operating close to the control bandwidth.
Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees
Venue: arXiv cs.GT 2022
Year: 2022

The internet advertising market is a multi-billion dollar industry, in which advertisers buy thousands of ad placements every day by repeatedly participating in auctions. An important and ubiquitous feature of these auctions is the presence of campaign budgets, which specify the maximum amount the advertisers are willing to pay over a specified time period. In this paper, we present a new model to study the equilibrium bidding strategies in standard auctions, a large class of auctions that includes first- and second-price auctions, for advertisers who satisfy budget constraints on average. Our model dispenses with the common, yet unrealistic assumption that advertisers' values are independent and instead assumes a contextual model in which advertisers determine their values using a common feature vector. We show the existence of a natural value-pacing-based Bayes-Nash equilibrium under very mild assumptions. Furthermore, we prove a revenue equivalence showing that all standard auctions yield the same revenue even in the presence of budget constraints. Leveraging this equivalence, we prove Price of Anarchy bounds for liquid welfare and structural properties of pacing-based equilibria that hold for all standard auctions. In recent years, the internet advertising market has adopted first-price auctions as the preferred paradigm for selling advertising slots. Our work thus takes an important step toward understanding the implications of the shift to first-price auctions in internet advertising markets by studying how the choice of the selling mechanism impacts revenues, welfare, and advertisers' bidding strategies.
Automatic sequences: from rational bases to trees
Venue: arXiv cs.FL 2022
Year: 2022

The $n$th term of an automatic sequence is the output of a deterministic finite automaton fed with the representation of $n$ in a suitable numeration system. In this paper, instead of considering automatic sequences built on a numeration system with a regular numeration language, we consider those built on languages associated with trees having periodic labeled signatures and, in particular, rational base numeration systems. We obtain two main characterizations of these sequences. The first one is concerned with $r$-block substitutions where $r$ morphisms are applied periodically. In particular, we provide examples of such sequences that are not morphic. The second characterization involves the factors, or subtrees of finite height, of the tree associated with the numeration system and decorated by the terms of the sequence.
Softmax Policy Gradient Methods Can Take Exponential Time to Converge
Venue: arXiv cs.LG 2022
Year: 2022

The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For $γ$-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space $\mathcal{S}$ and the effective horizon $\frac{1}{1-γ}$, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize $η$ can take \[ \frac{1}η |\mathcal{S}|^{2^{Ω\big(\frac{1}{1-γ}\big)}} ~\text{iterations} \] to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.
On Meritocracy in Optimal Set Selection
Venue: arXiv cs.AI 2022
Year: 2022

Typically, merit is defined with respect to some intrinsic measure of worth. We instead consider a setting where an individual's worth is \emph{relative}: when a Decision Maker (DM) selects a set of individuals from a population to maximise expected utility, it is natural to consider the \emph{Expected Marginal Contribution} (EMC) of each person to the utility. We show that this notion satisfies an axiomatic definition of fairness for this setting. We also show that for certain policy structures, this notion of fairness is aligned with maximising expected utility, while for linear utility functions it is identical to the Shapley value. However, for certain natural policies, such as those that select individuals with a specific set of attributes (e.g. high enough test scores for college admissions), there is a trade-off between meritocracy and utility maximisation. We analyse the effect of constraints on the policy on both utility and fairness in extensive experiments based on college admissions and outcomes in Norwegian universities.
PADA: Example-based Prompt Learning for on-the-fly Adaptation to Unseen Domains
Venue: arXiv cs.CL 2022
Year: 2022

Natural Language Processing algorithms have made incredible progress, but they still struggle when applied to out-of-distribution examples. We address a challenging and underexplored version of this domain adaptation problem, where an algorithm is trained on several source domains, and then applied to examples from unseen domains that are unknown at training time. Particularly, no examples, labeled or unlabeled, or any other knowledge about the target domain are available to the algorithm at training time. We present PADA: An example-based autoregressive Prompt learning algorithm for on-the-fly Any-Domain Adaptation, based on the T5 language model. Given a test example, PADA first generates a unique prompt for it and then, conditioned on this prompt, labels the example with respect to the NLP prediction task. PADA is trained to generate a prompt which is a token sequence of unrestricted length, consisting of Domain Related Features (DRFs) that characterize each of the source domains. Intuitively, the generated prompt is a unique signature that maps the test example to a semantic space spanned by the source domains. In experiments with 3 tasks (text classification and sequence tagging), for a total of 14 multi-source adaptation scenarios, PADA substantially outperforms strong baselines.