OpenRaiser/Intern-Atlas huggingface dataset:
Combinatorial Characterizations and Impossibilities for Higher-order Homophily
Venue: arXiv cs.SI 2023
Year: 2023

Homophily is the seemingly ubiquitous tendency for people to connect and interact with other individuals who are similar to them. This is a well-documented principle and is fundamental for how society organizes. Although many social interactions occur in groups, homophily has traditionally been measured using a graph model, which only accounts for pairwise interactions involving two individuals. Here, we develop a framework using hypergraphs to quantify homophily from group interactions. This reveals natural patterns of group homophily that appear with gender in scientific collaboration and political affiliation in legislative bill co-sponsorship, and also reveals distinctive gender distributions in group photographs, all of which cannot be fully captured by pairwise measures. At the same time, we show that seemingly natural ways to define group homophily are combinatorially impossible. This reveals important pitfalls to avoid when defining and interpreting notions of group homophily, as higher-order homophily patterns are governed by combinatorial constraints that are independent of human behavior but are easily overlooked.
Raven's Progressive Matrices Completion with Latent Gaussian Process Priors
Venue: arXiv cs.AI 2023
Year: 2023

Abstract reasoning ability is fundamental to human intelligence. It enables humans to uncover relations among abstract concepts and further deduce implicit rules from the relations. As a well-known abstract visual reasoning task, Raven's Progressive Matrices (RPM) are widely used in human IQ tests. Although extensive research has been conducted on RPM solvers with machine intelligence, few studies have considered further advancing the standard answer-selection (classification) problem to a more challenging answer-painting (generating) problem, which can verify whether the model has indeed understood the implicit rules. In this paper we aim to solve the latter one by proposing a deep latent variable model, in which multiple Gaussian processes are employed as priors of latent variables to separately learn underlying abstract concepts from RPMs; thus the proposed model is interpretable in terms of concept-specific latent variables. The latent Gaussian process also provides an effective way of extrapolation for answer painting based on the learned concept-changing rules. We evaluate the proposed model on RPM-like datasets with multiple continuously-changing visual concepts. Experimental results demonstrate that our model requires only few training samples to paint high-quality answers, generate novel RPM panels, and achieve interpretability through concept-specific latent variables.
BoXHED2.0: Scalable boosting of dynamic survival analysis
Venue: arXiv cs.LG 2023
Year: 2023

Modern applications of survival analysis increasingly involve time-dependent covariates. The Python package BoXHED2.0 is a tree-boosted hazard estimator that is fully nonparametric, and is applicable to survival settings far more general than right-censoring, including recurring events and competing risks. BoXHED2.0 is also scalable to the point of being on the same order of speed as parametric boosted survival models, in part because its core is written in C++ and it also supports the use of GPUs and multicore CPUs. BoXHED2.0 is available from PyPI and also from www.github.com/BoXHED.
A VAE-Bayesian Deep Learning Scheme for Solar Generation Forecasting based on Dimensionality Reduction
Venue: arXiv cs.LG 2023
Year: 2023

The advancement of distributed generation technologies in modern power systems has led to a widespread integration of renewable power generation at customer side. However, the intermittent nature of renewable energy poses new challenges to the network operational planning with underlying uncertainties. This paper proposes a novel Bayesian probabilistic technique for forecasting renewable solar generation by addressing data and model uncertainties by integrating bidirectional long short-term memory (BiLSTM) neural networks while compressing the weight parameters using variational autoencoder (VAE). Existing Bayesian deep learning methods suffer from high computational complexities as they require to draw a large number of samples from weight parameters expressed in the form of probability distributions. The proposed method can deal with uncertainty present in model and data in a more computationally efficient manner by reducing the dimensionality of model parameters. The proposed method is evaluated using quantile loss, reconstruction error, and deterministic forecasting evaluation metrics such as root-mean square error. It is inferred from the numerical results that VAE-Bayesian BiLSTM outperforms other probabilistic and deterministic deep learning methods for solar power forecasting in terms of accuracy and computational efficiency for different sizes of the dataset.
Anytime informed path re-planning and optimization for robots in changing environments
Venue: arXiv cs.RO 2023
Year: 2023

In this paper, we propose a path re-planning algorithm that makes robots able to work in scenarios with moving obstacles. The algorithm switches between a set of pre-computed paths to avoid collisions with moving obstacles. It also improves the current path in an anytime fashion. The use of informed sampling enhances the search speed. Numerical results show the effectiveness of the strategy in different simulation scenarios.
Prioritise the Best Variation
Venue: arXiv cs.PL 2023
Year: 2023

Binary session types guarantee communication safety and session fidelity, but alone they cannot rule out deadlocks arising from the interleaving of different sessions. In Classical Processes (CP)$-$a process calculus based on classical linear logic$-$deadlock freedom is guaranteed by combining channel creation and parallel composition under the same logical cut rule. Similarly, in Good Variation (GV)$-$a linear concurrent $λ$-calculus$-$deadlock freedom is guaranteed by combining channel creation and thread spawning under the same operation, called fork. In both CP and GV, deadlock freedom is achieved at the expense of expressivity, as the only processes allowed are tree-structured. Dardha and Gay define Priority CP (PCP), which allows cyclic-structured processes and restores deadlock freedom by using priorities, in line with Kobayashi and Padovani. Following PCP, we present Priority GV (PGV), a variant of GV which decouples channel creation from thread spawning. Consequently, we type cyclic-structured processes and restore deadlock freedom by using priorities. We show that our type system is sound by proving subject reduction and progress. We define an encoding from PCP to PGV and prove that the encoding preserves typing and is sound and complete with respect to the operational semantics.
Deriving Laws for Developing Concurrent Programs in a Rely-Guarantee Style
Venue: arXiv cs.LO 2023
Year: 2023

This paper presents a theory for the refinement of shared-memory concurrent algorithms from specifications. We augment pre and post condition specifications with Jones' rely and guarantee conditions, all of which are encoded as commands within a wide-spectrum language. Program components are specified using either partial or total correctness versions of postcondition specifications. Operations on shared data structures and atomic machine operations (e.g. compare-and-swap) are specified using an atomic specification command. All the above constructs are defined in terms of a simple core language, based on a small set of primitive commands and a handful of operators. A comprehensive set of laws for refining such specifications to code is derived in the theory. The approach supports fine-grained concurrency, avoiding atomicity assumptions on expression evaluation and assignment commands. The theory has been formalised in Isabelle/HOL, and the refinement laws and supporting lemmas have been proven in Isabelle/HOL.
An In-depth Analysis of Passage-Level Label Transfer for Contextual Document Ranking
Venue: arXiv cs.IR 2023
Year: 2023

Pre-trained contextual language models such as BERT, GPT, and XLnet work quite well for document retrieval tasks. Such models are fine-tuned based on the query-document/query-passage level relevance labels to capture the ranking signals. However, the documents are longer than the passages and such document ranking models suffer from the token limitation (512) of BERT. Researchers proposed ranking strategies that either truncate the documents beyond the token limit or chunk the documents into units that can fit into the BERT. In the later case, the relevance labels are either directly transferred from the original query-document pair or learned through some external model. In this paper, we conduct a detailed study of the design decisions about splitting and label transfer on retrieval effectiveness and efficiency. We find that direct transfer of relevance labels from documents to passages introduces label noise that strongly affects retrieval effectiveness for large training datasets. We also find that query processing times are adversely affected by fine-grained splitting schemes. As a remedy, we propose a careful passage level labelling scheme using weak supervision that delivers improved performance (3-14% in terms of nDCG score) over most of the recently proposed models for ad-hoc retrieval while maintaining manageable computational complexity on four diverse document retrieval datasets.
Learning by Aligning Videos in Time
Venue: arXiv cs.CV 2023
Year: 2023

We present a self-supervised approach for learning video representations using temporal video alignment as a pretext task, while exploiting both frame-level and video-level information. We leverage a novel combination of temporal alignment loss and temporal regularization terms, which can be used as supervision signals for training an encoder network. Specifically, the temporal alignment loss (i.e., Soft-DTW) aims for the minimum cost for temporally aligning videos in the embedding space. However, optimizing solely for this term leads to trivial solutions, particularly, one where all frames get mapped to a small cluster in the embedding space. To overcome this problem, we propose a temporal regularization term (i.e., Contrastive-IDM) which encourages different frames to be mapped to different points in the embedding space. Extensive evaluations on various tasks, including action phase classification, action phase progression, and fine-grained frame retrieval, on three datasets, namely Pouring, Penn Action, and IKEA ASM, show superior performance of our approach over state-of-the-art methods for self-supervised representation learning from videos. In addition, our method provides significant performance gain where labeled data is lacking. Our code and labels are available on our research website: https://retrocausal.ai/research/
Curl-Flow: Boundary-Respecting Pointwise Incompressible Velocity Interpolation for Grid-Based Fluids
Venue: arXiv cs.GR 2023
Year: 2023

We propose to augment standard grid-based fluid solvers with pointwise divergence-free velocity interpolation, thereby ensuring exact incompressibility down to the sub-cell level. Our method takes as input a discretely divergence-free velocity field generated by a staggered grid pressure projection, and first recovers a corresponding discrete vector potential. Instead of solving a costly vector Poisson problem for the potential, we develop a fast parallel sweeping strategy to find a candidate potential and apply a gauge transformation to enforce the Coulomb gauge condition and thereby make it numerically smooth. Interpolating this discrete potential generates a pointwise vector potential whose analytical curl is a pointwise incompressible velocity field. Our method further supports irregular solid geometry through the use of level set-based cut-cells and a novel Curl-Noise-inspired potential ramping procedure that simultaneously offers strictly non-penetrating velocities and incompressibility. Experimental comparisons demonstrate that the vector potential reconstruction procedure at the heart of our approach is consistently faster than prior such reconstruction schemes, especially those that solve vector Poisson problems. Moreover, in exchange for its modest extra cost, our overall Curl-Flow framework produces significantly improved particle trajectories that closely respect irregular obstacles, do not suffer from spurious sources or sinks, and yield superior particle distributions over time.
CAROM -- Vehicle Localization and Traffic Scene Reconstruction from Monocular Cameras on Road Infrastructures
Venue: arXiv cs.RO 2023
Year: 2023

Traffic monitoring cameras are powerful tools for traffic management and essential components of intelligent road infrastructure systems. In this paper, we present a vehicle localization and traffic scene reconstruction framework using these cameras, dubbed as CAROM, i.e., "CARs On the Map". CAROM processes traffic monitoring videos and converts them to anonymous data structures of vehicle type, 3D shape, position, and velocity for traffic scene reconstruction and replay. Through collaborating with a local department of transportation in the United States, we constructed a benchmarking dataset containing GPS data, roadside camera videos, and drone videos to validate the vehicle tracking results. On average, the localization error is approximately 0.8 m and 1.7 m within the range of 50 m and 120 m from the cameras, respectively.
A Survey on Social-Physical Sensing: An Emerging Sensing Paradigm that Explores the Collective Intelligence of Humans and Machine
Venue: arXiv cs.SI 2023
Year: 2023

Propelled by the omnipresence of versatile data capture, communication, and computing technologies, physical sensing has revolutionized the avenue for decisively interpreting the real world. However, various limitations hinder physical sensing's effectiveness in critical scenarios such as disaster response and urban anomaly detection. Meanwhile, social sensing is contriving as a pervasive sensing paradigm leveraging observations from human participants equipped with portable devices and ubiquitous Internet connectivity to perceive the environment. Despite its virtues, social sensing also inherently suffers from a few drawbacks (e.g., inconsistent reliability and uncertain data provenance). Motivated by the complementary strengths of the two sensing modes, social-physical sensing (SPS) is protruding as an emerging sensing paradigm that explores the collective intelligence of humans and machines to reconstruct the "state of the world", both physically and socially. While a good number of interesting SPS applications have been studied, several critical unsolved challenges still exist in SPS. In this paper, we provide a comprehensive survey of SPS, emphasizing its definition, key enablers, state-of-the-art applications, potential research challenges, and roadmap for future work. This paper intends to bridge the knowledge gap of existing sensing-focused survey papers by thoroughly examining the various aspects of SPS crucial for building potent SPS systems.
Achieving Domain Generalization in Underwater Object Detection by Domain Mixup and Contrastive Learning
Venue: arXiv cs.CV 2023
Year: 2023

The performance of existing underwater object detection methods degrades seriously when facing domain shift caused by complicated underwater environments. Due to the limitation of the number of domains in the dataset, deep detectors easily memorize a few seen domains, which leads to low generalization ability. There are two common ideas to improve the domain generalization performance. First, it can be inferred that the detector trained on as many domains as possible is domain-invariant. Second, for the images with the same semantic content in different domains, their hidden features should be equivalent. This paper further excavates these two ideas and proposes a domain generalization framework (named DMC) that learns how to generalize across domains from Domain Mixup and Contrastive Learning. First, based on the formation of underwater images, an image in an underwater environment is the linear transformation of another underwater environment. Thus, a style transfer model, which outputs a linear transformation matrix instead of the whole image, is proposed to transform images from one source domain to another, enriching the domain diversity of the training data. Second, mixup operation interpolates different domains on the feature level, sampling new domains on the domain manifold. Third, contrastive loss is selectively applied to features from different domains to force the model to learn domain invariant features but retain the discriminative capacity. With our method, detectors will be robust to domain shift. Also, a domain generalization benchmark S-UODAC2020 for detection is set up to measure the performance of our method. Comprehensive experiments on S-UODAC2020 and two object recognition benchmarks (PACS and VLCS) demonstrate that the proposed method is able to learn domain-invariant representations, and outperforms other domain generalization methods.
Visual Vibration Tomography: Estimating Interior Material Properties from Monocular Video
Venue: arXiv cs.CV 2023
Year: 2023

An object's interior material properties, while invisible to the human eye, determine motion observed on its surface. We propose an approach that estimates heterogeneous material properties of an object from a monocular video of its surface vibrations. Specifically, we show how to estimate Young's modulus and density throughout a 3D object with known geometry. Knowledge of how these values change across the object is useful for simulating its motion and characterizing any defects. Traditional non-destructive testing approaches, which often require expensive instruments, generally estimate only homogenized material properties or simply identify the presence of defects. In contrast, our approach leverages monocular video to (1) identify image-space modes from an object's sub-pixel motion, and (2) directly infer spatially-varying Young's modulus and density values from the observed modes. We demonstrate our approach on both simulated and real videos.
Py-Feat: Python Facial Expression Analysis Toolbox
Venue: arXiv cs.CV 2023
Year: 2023

Studying facial expressions is a notoriously difficult endeavor. Recent advances in the field of affective computing have yielded impressive progress in automatically detecting facial expressions from pictures and videos. However, much of this work has yet to be widely disseminated in social science domains such as psychology. Current state of the art models require considerable domain expertise that is not traditionally incorporated into social science training programs. Furthermore, there is a notable absence of user-friendly and open-source software that provides a comprehensive set of tools and functions that support facial expression research. In this paper, we introduce Py-Feat, an open-source Python toolbox that provides support for detecting, preprocessing, analyzing, and visualizing facial expression data. Py-Feat makes it easy for domain experts to disseminate and benchmark computer vision models and also for end users to quickly process, analyze, and visualize face expression data. We hope this platform will facilitate increased use of facial expression data in human behavior research.
A Neural Pre-Conditioning Active Learning Algorithm to Reduce Label Complexity
Venue: arXiv cs.LG 2023
Year: 2023

Deep learning (DL) algorithms rely on massive amounts of labeled data. Semi-supervised learning (SSL) and active learning (AL) aim to reduce this label complexity by leveraging unlabeled data or carefully acquiring labels, respectively. In this work, we primarily focus on designing an AL algorithm but first argue for a change in how AL algorithms should be evaluated. Although unlabeled data is readily available in pool-based AL, AL algorithms are usually evaluated by measuring the increase in supervised learning (SL) performance at consecutive acquisition steps. Because this measures performance gains from both newly acquired instances and newly acquired labels, we propose to instead evaluate the label efficiency of AL algorithms by measuring the increase in SSL performance at consecutive acquisition steps. After surveying tools that can be used to this end, we propose our neural pre-conditioning (NPC) algorithm inspired by a Neural Tangent Kernel (NTK) analysis. Our algorithm incorporates the classifier's uncertainty on unlabeled data and penalizes redundant samples within candidate batches to efficiently acquire a diverse set of informative labels. Furthermore, we prove that NPC improves downstream training in the large-width regime in a manner previously observed to correlate with generalization. Comparisons with other AL algorithms show that a state-of-the-art SSL algorithm coupled with NPC can achieve high performance using very few labeled data.
Universally-Optimal Distributed Algorithms for Known Topologies
Venue: arXiv cs.DS 2023
Year: 2023

Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (1) What network topology parameters determine the complexity of distributed optimization? (2) Are there universally-optimal algorithms that are as fast as possible on every topology? We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, $(1+\varepsilon)$-min cut, various approximate shortest paths problems, sub-graph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the low-congestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable. We leverage a recent result in hop-constrained oblivious routing to show this is the case if the topology is known -- giving universally-optimal algorithms for all above problems.
Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
Venue: arXiv cs.DM 2023
Year: 2023

The \emph{thinness} of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Graphs with thinness at most two include, for example, bipartite convex graphs. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. \emph{Proper thinness} is defined analogously, generalizing proper interval graphs, and a larger family of NP-complete problems are known to be polynomially solvable for graphs with bounded proper thinness. The complexity of recognizing 2-thin and proper 2-thin graphs is still open. In this work, we present characterizations of 2-thin and proper 2-thin graphs as intersection graphs of rectangles in the plane, as vertex intersection graphs of paths on a grid (VPG graphs), and by forbidden ordered patterns. We also prove that independent 2-thin graphs are exactly the interval bigraphs, and that proper independent 2-thin graphs are exactly the bipartite permutation graphs. Finally, we take a step towards placing the thinness and its variations in the landscape of width parameters, by upper bounding the proper thinness in terms of the bandwidth.