OpenRaiser/Intern-Atlas huggingface dataset:
Task-adaptive Asymmetric Deep Cross-modal Hashing
Venue: arXiv cs.IR 2022
Year: 2022

Supervised cross-modal hashing aims to embed the semantic correlations of heterogeneous modality data into the binary hash codes with discriminative semantic labels. Because of its advantages on retrieval and storage efficiency, it is widely used for solving efficient cross-modal retrieval. However, existing researches equally handle the different tasks of cross-modal retrieval, and simply learn the same couple of hash functions in a symmetric way for them. Under such circumstance, the uniqueness of different cross-modal retrieval tasks are ignored and sub-optimal performance may be brought. Motivated by this, we present a Task-adaptive Asymmetric Deep Cross-modal Hashing (TA-ADCMH) method in this paper. It can learn task-adaptive hash functions for two sub-retrieval tasks via simultaneous modality representation and asymmetric hash learning. Unlike previous cross-modal hashing approaches, our learning framework jointly optimizes semantic preserving that transforms deep features of multimedia data into binary hash codes, and the semantic regression which directly regresses query modality representation to explicit label. With our model, the binary codes can effectively preserve semantic correlations across different modalities, meanwhile, adaptively capture the query semantics. The superiority of TA-ADCMH is proved on two standard datasets from many aspects.
Understanding Linearity of Cross-Lingual Word Embedding Mappings
Venue: arXiv cs.CL 2022
Year: 2022

The technique of Cross-Lingual Word Embedding (CLWE) plays a fundamental role in tackling Natural Language Processing challenges for low-resource languages. Its dominant approaches assumed that the relationship between embeddings could be represented by a linear mapping, but there has been no exploration of the conditions under which this assumption holds. Such a research gap becomes very critical recently, as it has been evidenced that relaxing mappings to be non-linear can lead to better performance in some cases. We, for the first time, present a theoretical analysis that identifies the preservation of analogies encoded in monolingual word embeddings as a necessary and sufficient condition for the ground-truth CLWE mapping between those embeddings to be linear. On a novel cross-lingual analogy dataset that covers five representative analogy categories for twelve distinct languages, we carry out experiments which provide direct empirical support for our theoretical claim. These results offer additional insight into the observations of other researchers and contribute inspiration for the development of more effective cross-lingual representation learning strategies.
Reselling Information
Venue: arXiv cs.GT 2022
Year: 2022

Information is replicable in that it can be simultaneously consumed and sold to others. We study how resale affects a decentralized market for information. We show that even if the initial seller is an informational monopolist, she captures non-trivial rents from at most a single buyer: her payoffs converge to 0 as soon as a single buyer has bought information. By contrast, if the seller can also sell valueless tokens, there exists a ``prepay equilibrium'' where payment is extracted from all buyers before the information good is released. By exploiting resale possibilities, this prepay equilibrium gives the seller as high a payoff as she would achieve if resale were prohibited.
Radon cumulative distribution transform subspace modeling for image classification
Venue: arXiv cs.CV 2022
Year: 2022

We present a new supervised image classification method applicable to a broad class of image deformation models. The method makes use of the previously described Radon Cumulative Distribution Transform (R-CDT) for image data, whose mathematical properties are exploited to express the image data in a form that is more suitable for machine learning. While certain operations such as translation, scaling, and higher-order transformations are challenging to model in native image space, we show the R-CDT can capture some of these variations and thus render the associated image classification problems easier to solve. The method -- utilizing a nearest-subspace algorithm in R-CDT space -- is simple to implement, non-iterative, has no hyper-parameters to tune, is computationally efficient, label efficient, and provides competitive accuracies to state-of-the-art neural networks for many types of classification problems. In addition to the test accuracy performances, we show improvements (with respect to neural network-based methods) in terms of computational efficiency (it can be implemented without the use of GPUs), number of training samples needed for training, as well as out-of-distribution generalization. The Python code for reproducing our results is available at https://github.com/rohdelab/rcdt_ns_classifier.
VehicleNet: Learning Robust Visual Representation for Vehicle Re-identification
Venue: arXiv cs.CV 2022
Year: 2022

One fundamental challenge of vehicle re-identification (re-id) is to learn robust and discriminative visual representation, given the significant intra-class vehicle variations across different camera views. As the existing vehicle datasets are limited in terms of training images and viewpoints, we propose to build a unique large-scale vehicle dataset (called VehicleNet) by harnessing four public vehicle datasets, and design a simple yet effective two-stage progressive approach to learning more robust visual representation from VehicleNet. The first stage of our approach is to learn the generic representation for all domains (i.e., source vehicle datasets) by training with the conventional classification loss. This stage relaxes the full alignment between the training and testing domains, as it is agnostic to the target vehicle domain. The second stage is to fine-tune the trained model purely based on the target vehicle set, by minimizing the distribution discrepancy between our VehicleNet and any target domain. We discuss our proposed multi-source dataset VehicleNet and evaluate the effectiveness of the two-stage progressive representation learning through extensive experiments. We achieve the state-of-art accuracy of 86.07% mAP on the private test set of AICity Challenge, and competitive results on two other public vehicle re-id datasets, i.e., VeRi-776 and VehicleID. We hope this new VehicleNet dataset and the learned robust representations can pave the way for vehicle re-id in the real-world environments.
A function space analysis of finite neural networks with insights from sampling theory
Venue: arXiv cs.LG 2022
Year: 2022

This work suggests using sampling theory to analyze the function space represented by neural networks. First, it shows, under the assumption of a finite input domain, which is the common case in training neural networks, that the function space generated by multi-layer networks with non-expansive activation functions is smooth. This extends over previous works that show results for the case of infinite width ReLU networks. Then, under the assumption that the input is band-limited, we provide novel error bounds for univariate neural networks. We analyze both deterministic uniform and random sampling showing the advantage of the former.
Polynomial-delay Enumeration Algorithms in Set Systems
Venue: arXiv cs.DM 2022
Year: 2022

We consider a set system $(V, {\mathcal C}\subseteq 2^V)$ on a finite set $V$ of elements, where we call a set $C\in {\mathcal C}$ a component. We assume that two oracles $\mathrm{L}_1$ and $\mathrm{L}_2$ are available, where given two subsets $X,Y\subseteq V$, $\mathrm{L}_1$ returns a maximal component $C\in {\mathcal C}$ with $X\subseteq C\subseteq Y$; and given a set $Y\subseteq V$, $\mathrm{L}_2$ returns all maximal components $C\in {\mathcal C}$ with $C\subseteq Y$. Given a set $I$ of attributes and a function $σ:V\to 2^I$ in a transitive system, a component $C\in {\mathcal C}$ is called a solution if the set of common attributes in $C$ is inclusively maximal; i.e., $\bigcap_{v\in C}σ(v)\supsetneq \bigcap_{v\in X}σ(v)$ for any component $X\in{\mathcal C}$ with $C\subsetneq X$. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size and the running times of the oracles.
A Probabilistic Logic for Verifying Continuous-time Markov Chains
Venue: arXiv cs.LO 2022
Year: 2022

A continuous-time Markov chain (CTMC) execution is a continuous class of probability distributions over states. This paper proposes a probabilistic linear-time temporal logic, namely continuous-time linear logic (CLL), to reason about the probability distribution execution of CTMCs. We define the syntax of CLL on the space of probability distributions. The syntax of CLL includes multiphase timed until formulas, and the semantics of CLL allows time reset to study relatively temporal properties. We derive a corresponding model-checking algorithm for CLL formulas. The correctness of the model-checking algorithm depends on Schanuel's conjecture, a central open problem in transcendental number theory. Furthermore, we provide a running example of CTMCs to illustrate our method.
Incorporating Multiple Cluster Centers for Multi-Label Learning
Venue: arXiv cs.LG 2022
Year: 2022

Multi-label learning deals with the problem that each instance is associated with multiple labels simultaneously. Most of the existing approaches aim to improve the performance of multi-label learning by exploiting label correlations. Although the data augmentation technique is widely used in many machine learning tasks, it is still unclear whether data augmentation is helpful to multi-label learning. In this article, we propose to leverage the data augmentation technique to improve the performance of multi-label learning. Specifically, we first propose a novel data augmentation approach that performs clustering on the real examples and treats the cluster centers as virtual examples, and these virtual examples naturally embody the local label correlations and label importances. Then, motivated by the cluster assumption that examples in the same cluster should have the same label, we propose a novel regularization term to bridge the gap between the real examples and virtual examples, which can promote the local smoothness of the learning function. Extensive experimental results on a number of real-world multi-label datasets clearly demonstrate that our proposed approach outperforms the state-of-the-art counterparts.
Hitting forbidden induced subgraphs on bounded treewidth graphs
Venue: arXiv cs.DS 2022
Year: 2022

For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus S$ does not contain $H$ as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph $H$, the smallest function $f_H(t)$ such that $H$-IS-Deletion can be solved in time $f_H(t) \cdot n^{O(1)}$ assuming the Exponential Time Hypothesis (ETH), where $t$ and $n$ denote the treewidth and the number of vertices of the input graph, respectively. We show that $f_H(t) = 2^{O(t^{h-2})}$ for every graph $H$ on $h \geq 3$ vertices, and that $f_H(t) = 2^{O(t)}$ if $H$ is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when $H$ deviates slightly from a clique, the function $f_H(t)$ suffers a sharp jump: if $H$ is obtained from a clique of size $h$ by removing one edge, then $f_H(t) = 2^{Θ(t^{h-2})}$. We also show that $f_H(t) = 2^{Ω(t^{h})}$ when $H=K_{h,h}$, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function $f_{C_4}(t)$ for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of $G$ is colored with some color from $V(H)$ and we require to hit only induced copies of $H$ with matching colors. In this case, we determine, under the ETH, the function $f_H(t)$ for every connected graph $H$ on $h$ vertices: if $h\leq 2$ the problem can be solved in polynomial time; if $h\geq 3$, $f_H(t) = 2^{Θ(t)}$ if $H$ is a clique, and $f_H(t) = 2^{Θ(t^{h-2})}$ otherwise.
Realistic Large-Scale Fine-Depth Dehazing Dataset from 3D Videos
Venue: arXiv cs.CV 2022
Year: 2022

Image dehazing is one of the important and popular topics in computer vision and machine learning. A reliable real-time dehazing method with reliable performance is highly desired for many applications such as autonomous driving, security surveillance, etc. While recent learning-based methods require datasets containing pairs of hazy images and clean ground truth, it is impossible to capture them in real scenes. Many existing works compromise this difficulty to generate hazy images by rendering the haze from depth on common RGBD datasets using the haze imaging model. However, there is still a gap between the synthetic datasets and real hazy images as large datasets with high-quality depth are mostly indoor and depth maps for outdoor are imprecise. In this paper, we complement the existing datasets with a new, large, and diverse dehazing dataset containing real outdoor scenes from High-Definition (HD) 3D movies. We select a large number of high-quality frames of real outdoor scenes and render haze on them using depth from stereo. Our dataset is clearly more realistic and more diversified with better visual quality than existing ones. More importantly, we demonstrate that using this dataset greatly improves the dehazing performance on real scenes. In addition to the dataset, we also evaluate a series state of the art methods on the proposed benchmarking datasets.
Reachability and liveness in parametric timed automata
Venue: arXiv cs.LO 2022
Year: 2022

We study timed systems in which some timing features are unknown parameters. Parametric timed automata (PTAs) are a classical formalism for such systems but for which most interesting problems are undecidable. Notably, the parametric reachability emptiness problem, i.e., the emptiness of the parameter valuations set allowing to reach some given discrete state, is undecidable. Lower-bound/upper-bound parametric timed automata (L/U-PTAs) achieve decidability for reachability properties by enforcing a separation of parameters used as upper bounds in the automaton constraints, and those used as lower bounds. In this paper, we first study reachability. We exhibit a subclass of PTAs (namely integer-points PTAs) with bounded rational-valued parameters for which the parametric reachability emptiness problem is decidable. Using this class, we present further results improving the boundary between decidability and undecidability for PTAs and their subclasses such as L/U-PTAs. We then study liveness. We prove that: (1) deciding the existence of at least one parameter valuation for which there exists an infinite run in an L/U-PTA is PSpace-complete; (2) the existence of a parameter valuation such that the system has a deadlock is however undecidable; (3) the problem of the existence of a valuation for which a run remains in a given set of locations exhibits a very thin border between decidability and undecidability.
LOCATER: Cleaning WiFi Connectivity Datasets for Semantic Localization
Venue: arXiv cs.DB 2022
Year: 2022

This paper explores the data cleaning challenges that arise in using WiFi connectivity data to locate users to semantic indoor locations such as buildings, regions, rooms. WiFi connectivity data consists of sporadic connections between devices and nearby WiFi access points (APs), each of which may cover a relatively large area within a building. Our system, entitled semantic LOCATion cleanER (LOCATER), postulates semantic localization as a series of data cleaning tasks - first, it treats the problem of determining the AP to which a device is connected between any two of its connection events as a missing value detection and repair problem. It then associates the device with the semantic subregion (e.g., a conference room in the region) by postulating it as a location disambiguation problem. LOCATER uses a bootstrapping semi-supervised learning method for coarse localization and a probabilistic method to achieve finer localization. The paper shows that LOCATER can achieve significantly high accuracy at both the coarse and fine levels.
Discovering Urban Functional Zones from Biased and Sparse Points of Interests and Sparse Human Activities
Venue: arXiv cs.SI 2022
Year: 2022

With rapid development of socio-economics, the task of discovering functional zones becomes critical to better understand the interactions between social activities and spatial locations. In this paper, we propose a framework to discover the real functional zones from the biased and extremely sparse Point of Interests (POIs). To cope with the bias and sparsity of POIs, the unbiased inner influences between spatial locations and human activities are introduced to learn a balanced and dense latent region representation. In addition, a spatial location based clustering method is also included to enrich the spatial information for latent region representation and enhance the region functionality consistency for the fine-grained region segmentation. Moreover, to properly annotate the various and fine-grained region functionalities, we estimate the functionality of the regions and rank them by the differences between the normalized POI distributions to reduce the inconsistency caused by the fine-grained segmentation. Thus, our whole framework is able to properly address the biased categories in sparse POI data and explore the true functional zones with a fine-grained level. To validate the proposed framework, a case study is evaluated by using very large real-world users GPS and POIs data from city of Raleigh. The results demonstrate that the proposed framework can better identify functional zones than the benchmarks, and, therefore, enhance understanding of urban structures with a finer granularity under practical conditions.
Regular matching problems for infinite trees
Venue: arXiv cs.FL 2022
Year: 2022

We study the matching problem of regular tree languages, that is, "$\exists σ:σ(L)\subseteq R$?" where $L,R$ are regular tree languages over the union of finite ranked alphabets $Σ$ and $\mathcal{X}$ where $\mathcal{X}$ is an alphabet of variables and $σ$ is a substitution such that $σ(x)$ is a set of trees in $T(Σ\cup H)\setminus H$ for all $x\in \mathcal{X}$. Here, $H$ denotes a set of "holes" which are used to define a "sorted" concatenation of trees. Conway studied this problem in the special case for languages of finite words in his classical textbook "Regular algebra and finite machines" published in 1971. He showed that if $L$ and $R$ are regular, then the problem "$\exists σ\forall x\in \mathcal{X}: σ(x)\neq \emptyset\wedge σ(L)\subseteq R$?" is decidable. Moreover, there are only finitely many maximal solutions, the maximal solutions are regular substitutions, and they are effectively computable. We extend Conway's results when $L,R$ are regular languages of finite and infinite trees, and language substitution is applied inside-out, in the sense of Engelfriet and Schmidt (1977/78). More precisely, we show that if $L\subseteq T(Σ\cup\mathcal{X})$ and $R\subseteq T(Σ)$ are regular tree languages over finite or infinite trees, then the problem "$\exists σ\forall x\in \mathcal{X}: σ(x)\neq \emptyset\wedge σ_{\mathrm{io}}(L)\subseteq R$?" is decidable. Here, the subscript "$\mathrm{io}$" in $σ_{\mathrm{io}}(L)$ refers to "inside-out". Moreover, there are only finitely many maximal solutions $σ$, the maximal solutions are regular substitutions and effectively computable. The corresponding question for the outside-in extension $σ_{\mathrm{oi}}$ remains open, even in the restricted setting of finite trees.
Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

We present a mean-variance policy iteration (MVPI) framework for risk-averse control in a discounted infinite horizon MDP optimizing the variance of a per-step reward random variable. MVPI enjoys great flexibility in that any policy evaluation method and risk-neutral control method can be dropped in for risk-averse control off the shelf, in both on- and off-policy settings. This flexibility reduces the gap between risk-neutral control and risk-averse control and is achieved by working on a novel augmented MDP directly. We propose risk-averse TD3 as an example instantiating MVPI, which outperforms vanilla TD3 and many previous risk-averse control methods in challenging Mujoco robot simulation tasks under a risk-aware performance metric. This risk-averse TD3 is the first to introduce deterministic policies and off-policy learning into risk-averse reinforcement learning, both of which are key to the performance boost we show in Mujoco domains.
On the proof complexity of logics of bounded branching
Venue: arXiv cs.LO 2022
Year: 2022

We investigate the proof complexity of extended Frege (EF) systems for basic transitive modal logics (K4, S4, GL, ...) augmented with the bounded branching axioms $\mathbf{BB}_k$. First, we study feasibility of the disjunction property and more general extension rules in EF systems for these logics: we show that the corresponding decision problems reduce to total coNP search problems (or equivalently, disjoint NP pairs, in the binary case); more precisely, the decision problem for extension rules is equivalent to a certain special case of interpolation for the classical EF system. Next, we use this characterization to prove superpolynomial (or even exponential, with stronger hypotheses) separations between EF and substitution Frege (SF) systems for all transitive logics contained in $\mathbf{S4.2GrzBB_2}$ or $\mathbf{GL.2BB_2}$ under some assumptions weaker than $\mathrm{PSPACE \ne NP}$. We also prove analogous results for superintuitionistic logics: we characterize the decision complexity of multi-conclusion Visser's rules in EF systems for Gabbay--de Jongh logics $\mathbf T_k$, and we show conditional separations between EF and SF for all intermediate logics contained in $\mathbf{T_2 + KC}$.
Beyond Data Samples: Aligning Differential Networks Estimation with Scientific Knowledge
Venue: arXiv cs.LG 2022
Year: 2022

Learning the differential statistical dependency network between two contexts is essential for many real-life applications, mostly in the high dimensional low sample regime. In this paper, we propose a novel differential network estimator that allows integrating various sources of knowledge beyond data samples. The proposed estimator is scalable to a large number of variables and achieves a sharp asymptotic convergence rate. Empirical experiments on extensive simulated data and four real-world applications (one on neuroimaging and three from functional genomics) show that our approach achieves improved differential network estimation and provides better supports to downstream tasks like classification. Our results highlight significant benefits of integrating group, spatial and anatomic knowledge during differential genetic network identification and brain connectome change discovery.