OpenRaiser/Intern-Atlas huggingface dataset:
Single image reflection removal via learning with multi-image constraints
Venue: arXiv cs.CV 2023
Year: 2023

Reflections are very common phenomena in our daily photography, which distract people's attention from the scene behind the glass. The problem of removing reflection artifacts is important but challenging due to its ill-posed nature. The traditional approaches solve an optimization problem over the constraints induced from multiple images, at the expense of large computation costs. Recent learning-based approaches have demonstrated a significant improvement in both performance and running time for single image reflection removal, but are limited as they require a large number of synthetic reflection/clean image pairs for direct supervision to approximate the ground truth, at the risk of overfitting in the synthetic image domain and degrading in the real image domain. In this paper, we propose a novel learning-based solution that combines the advantages of the aforementioned approaches and overcomes their drawbacks. Our algorithm works by learning a deep neural network to optimize the target with joint constraints enhanced among multiple input images during the training phase, but is able to eliminate reflections only from a single input for evaluation. Our algorithm runs in real-time and achieves state-of-the-art reflection removal performance on real images. We further propose a strong network backbone that disentangles the background and reflection information into separate latent codes, which are embedded into a shared one-branch deep neural network for both background and reflection predictions. The proposed backbone experimentally performs better than the other common network implementations, and provides insightful knowledge to understand the reflection removal task.
Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations
Venue: arXiv cs.LG 2023
Year: 2023

I study how the shadow prices of a linear program that allocates an endowment of $nβ\in \mathbb{R}^{m}$ resources to $n$ customers behave as $n \rightarrow \infty$. I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like $Θ(1/n)$. I use these results to prove that the expected regret in \cites{Li2019b} online linear program is $Θ(\log n)$, both when the customer variable distribution is known upfront and must be learned on the fly. I thus tighten \citeauthors{Li2019b} upper bound from $O(\log n \log \log n)$ to $O(\log n)$, and extend \cites{Lueker1995} $Ω(\log n)$ lower bound to the multi-dimensional setting. I illustrate my new techniques with a simple analysis of \cites{Arlotto2019} multisecretary problem.
A Region-based Randers Geodesic Approach for Image Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

The geodesic model based on the eikonal partial differential equation (PDE) has served as a fundamental tool for the applications of image segmentation and boundary detection in the past two decades. However, the existing approaches commonly only exploit the image edge-based features for computing minimal geodesic paths, potentially limiting their performance in complicated segmentation situations. In this paper, we introduce a new variational image segmentation model based on the minimal geodesic path framework and the eikonal PDE, where the region-based appearance term that defines then regional homogeneity features can be taken into account for estimating the associated minimal geodesic paths. This is done by constructing a Randers geodesic metric interpretation of the region-based active contour energy functional. As a result, the minimization of the active contour energy functional is transformed into finding the solution to the Randers eikonal PDE. We also suggest a practical interactive image segmentation strategy, where the target boundary can be delineated by the concatenation of several piecewise geodesic paths. We invoke the Finsler variant of the fast marching method to estimate the geodesic distance map, yielding an efficient implementation of the proposed region-based Randers geodesic model for image segmentation. Experimental results on both synthetic and real images exhibit that our model indeed achieves encouraging segmentation performance.
Coarse-Grained Complexity for Dynamic Algorithms
Venue: arXiv cs.CC 2023
Year: 2023

To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific problems such as the Strong Exponential Time Hypothesis (SETH) and the Online Matrix-Vector Multiplication Conjecture (OMv). While they have led to many exciting discoveries, dynamic algorithms still miss out some benefits and lessons from the traditional ``coarse-grained'' approach that relates together classes of problems such as P and NP. In this paper we initiate the study of coarse-grained complexity theory for dynamic algorithms. Below are among questions that this theory can answer. What if dynamic Orthogonal Vector (OV) is easy in the cell-probe model? A research program for proving polynomial unconditional lower bounds for dynamic OV in the cell-probe model is motivated by the fact that many conditional lower bounds can be shown via reductions from the dynamic OV problem. Since the cell-probe model is more powerful than word RAM and has historically allowed smaller upper bounds, it might turn out that dynamic OV is easy in the cell-probe model, making this research direction infeasible. Our theory implies that if this is the case, there will be very interesting algorithmic consequences: If dynamic OV can be maintained in polylogarithmic worst-case update time in the cell-probe model, then so are several important dynamic problems such as $k$-edge connectivity, $(1+ε)$-approximate mincut, $(1+ε)$-approximate matching, planar nearest neighbors, Chan's subset union and 3-vs-4 diameter. The same conclusion can be made when we replace dynamic OV by, e.g., subgraph connectivity, single source reachability, Chan's subset union, and 3-vs-4 diameter. Lower bounds for $k$-edge connectivity via dynamic OV? (see the full abstract in the pdf file).
Provenance for the Description Logic ELHr
Venue: arXiv cs.LO 2023
Year: 2023

We address the problem of handling provenance information in ELHr ontologies. We consider a setting recently introduced for ontology-based data access, based on semirings and extending classical data provenance, in which ontology axioms are annotated with provenance tokens. A consequence inherits the provenance of the axioms involved in deriving it, yielding a provenance polynomial as an annotation. We analyse the semantics for the ELHr case and show that the presence of conjunctions poses various difficulties for handling provenance, some of which are mitigated by assuming multiplicative idempotency of the semiring. Under this assumption, we study three problems: ontology completion with provenance, computing the set of relevant axioms for a consequence, and query answering.
`Why didn't you allocate this task to them?' Negotiation-Aware Explicable Task Allocation and Contrastive Explanation Generation
Venue: arXiv cs.AI 2023
Year: 2023

Task allocation is an important problem in multi-agent systems. It becomes more challenging when the team-members are humans with imperfect knowledge about their teammates' costs and the overall performance metric. In this paper, we propose a centralized Artificial Intelligence Task Allocation (AITA) that simulates a negotiation and produces a negotiation-aware explicable task allocation. If a team-member is unhappy with the proposed allocation, we allow them to question the proposed allocation using a counterfactual. By using parts of the simulated negotiation, we are able to provide contrastive explanations that provide minimum information about other's cost to refute their foil. With human studies, we show that (1) the allocation proposed using our method appears fair to the majority, and (2) when a counterfactual is raised, explanations generated are easy to comprehend and convincing. Finally, we empirically study the effect of different kinds of incompleteness on the explanation-length and find that underestimation of a teammate's costs often increases it.
Geometric rank of tensors and subrank of matrix multiplication
Venue: arXiv cs.CC 2023
Year: 2023

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987.
Hyperbolic Minesweeper is in P
Venue: arXiv cs.CC 2023
Year: 2023

We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
A Systematic Survey of General Sparse Matrix-Matrix Multiplication
Venue: arXiv cs.DC 2023
Year: 2023

General Sparse Matrix-Matrix Multiplication (SpGEMM) has attracted much attention from researchers in graph analyzing, scientific computing, and deep learning. Many optimization techniques have been developed for different applications and computing architectures over the past decades. The objective of this paper is to provide a structured and comprehensive overview of the researches on SpGEMM. Existing researches have been grouped into different categories based on target architectures and design choices. Covered topics include typical applications, compression formats, general formulations, key problems and techniques, architecture-oriented optimizations, and programming models. The rationales of different algorithms are analyzed and summarized. This survey sufficiently reveals the latest progress of SpGEMM research to 2021. Moreover, a thorough performance comparison of existing implementations is presented. Based on our findings, we highlight future research directions, which encourage better design and implementations in later studies.
Nonlinear classifiers for ranking problems based on kernelized SVM
Venue: arXiv cs.LG 2023
Year: 2023

Many classification problems focus on maximizing the performance only on the samples with the highest relevance instead of all samples. As an example, we can mention ranking problems, accuracy at the top or search engines where only the top few queries matter. In our previous work, we derived a general framework including several classes of these linear classification problems. In this paper, we extend the framework to nonlinear classifiers. Utilizing a similarity to SVM, we dualize the problems, add kernels and propose a componentwise dual ascent method.
Generalized Gumbel-Softmax Gradient Estimator for Generic Discrete Random Variables
Venue: arXiv cs.LG 2023
Year: 2023

Estimating the gradients of stochastic nodes in stochastic computational graphs is one of the crucial research questions in the deep generative modeling community, which enables the gradient descent optimization on neural network parameters. Stochastic gradient estimators of discrete random variables are widely explored, for example, Gumbel-Softmax reparameterization trick for Bernoulli and categorical distributions. Meanwhile, other discrete distribution cases such as the Poisson, geometric, binomial, multinomial, negative binomial, etc. have not been explored. This paper proposes a generalized version of the Gumbel-Softmax estimator, which is able to reparameterize generic discrete distributions, not restricted to the Bernoulli and the categorical. The proposed estimator utilizes the truncation of discrete random variables, the Gumbel-Softmax trick, and a special form of linear transformation. Our experiments consist of (1) synthetic examples and applications on VAE, which show the efficacy of our methods; and (2) topic models, which demonstrate the value of the proposed estimation in practice.
An Online Framework to Interact and Efficiently Compute Linear Layouts of Graphs
Venue: arXiv cs.DM 2023
Year: 2023

We present a prototype online system to automate the procedure of computing different types of linear layouts of graphs under different user-specific constraints. Currently, four different types of linear layouts are supported: stack, queue, rique and deque, as well as, any mixture of them. The system consists of two main components; the client and the server sides. The client side is built upon an easy-to-use editor, which supports basic interaction with graphs, enriched with several additional features to allow the user to define and further constraint the linear layout to be computed. The server side, which is available to multiple clients through a well-documented API, is responsible for the actual computation of the linear layout. Its algorithmic core is an extension of a SAT formulation that is known to be robust enough to solve non-trivial instances in reasonable amount of time.
Learning Cross-domain Semantic-Visual Relationships for Transductive Zero-Shot Learning
Venue: arXiv cs.CV 2023
Year: 2023

Zero-Shot Learning (ZSL) learns models for recognizing new classes. One of the main challenges in ZSL is the domain discrepancy caused by the category inconsistency between training and testing data. Domain adaptation is the most intuitive way to address this challenge. However, existing domain adaptation techniques cannot be directly applied into ZSL due to the disjoint label space between source and target domains. This work proposes the Transferrable Semantic-Visual Relation (TSVR) approach towards transductive ZSL. TSVR redefines image recognition as predicting the similarity/dissimilarity labels for semantic-visual fusions consisting of class attributes and visual features. After the above transformation, the source and target domains can have the same label space, which hence enables to quantify domain discrepancy. For the redefined problem, the number of similar semantic-visual pairs is significantly smaller than that of dissimilar ones. To this end, we further propose to use Domain-Specific Batch Normalization to align the domain discrepancy.
Error correction and extraction in request dialogs
Venue: arXiv cs.CL 2023
Year: 2023

We propose a dialog system utility component that gets the last two utterances of a user and can detect whether the last utterance is an error correction of the second last utterance. If yes, it corrects the second last utterance according to the error correction in the last utterance and outputs the extracted pairs of reparandum and repair entity. This component offers two advantages, learning the concept of corrections to avoid collecting corrections for every new domain and extracting reparandum and repair pairs, which offers the possibility to learn out of it. For the error correction one sequence labeling and two sequence to sequence approaches are presented. For the error correction detection these three error correction approaches can also be used and in addition, we present a sequence classification approach. One error correction detection and one error correction approach can be combined to a pipeline or the error correction approaches can be trained and used end-to-end to avoid two components. We modified the EPIC-KITCHENS-100 dataset to evaluate the approaches for correcting entity phrases in request dialogs. For error correction detection and correction, we got an accuracy of 96.40 % on synthetic validation data and an accuracy of 77.81 % on human-created real-world test data.
A tale of two toolkits, report the third: on the usage and performance of HIVE-COTE v1.0
Venue: arXiv cs.LG 2023
Year: 2023

The Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-COTE) is a heterogeneous meta ensemble for time series classification. Since it was first proposed in 2016, the algorithm has undergone some minor changes and there is now a configurable, scalable and easy to use version available in two open source repositories. We present an overview of the latest stable HIVE-COTE, version 1.0, and describe how it differs to the original. We provide a walkthrough guide of how to use the classifier, and conduct extensive experimental evaluation of its predictive performance and resource usage. We compare the performance of HIVE-COTE to three recently proposed algorithms using the aeon toolkit.
On the Parameterised Complexity of Induced Multipartite Graph Parameters
Venue: arXiv cs.CC 2023
Year: 2023

We introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity. First, we consider the following decision problem: an instance is an induced multipartite graph parameter $p$ and a given graph $G$, and for natural numbers $k\geq2$ and $\ell$, we must decide whether the maximum value of $p$ over all induced $k$-partite subgraphs of $G$ is at most $\ell$. We prove that this problem is W[1]-hard. Next, we consider a variant of this problem, where we must decide whether the given graph $G$ contains a sufficiently large induced $k$-partite subgraph $H$ such that $p(H)\leq\ell$. We show that for certain parameters this problem is para-NP-hard, while for others it is fixed-parameter tractable.
A general framework for enumerating equivalence classes of solutions
Venue: arXiv cs.DS 2023
Year: 2023

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.
Human in Events: A Large-Scale Benchmark for Human-centric Video Analysis in Complex Events
Venue: arXiv cs.CV 2023
Year: 2023

Along with the development of modern smart cities, human-centric video analysis has been encountering the challenge of analyzing diverse and complex events in real scenes. A complex event relates to dense crowds, anomalous individuals, or collective behaviors. However, limited by the scale and coverage of existing video datasets, few human analysis approaches have reported their performances on such complex events. To this end, we present a new large-scale dataset with comprehensive annotations, named Human-in-Events or HiEve (Human-centric video analysis in complex Events), for the understanding of human motions, poses, and actions in a variety of realistic events, especially in crowd & complex events. It contains a record number of poses (>1M), the largest number of action instances (>56k) under complex events, as well as one of the largest numbers of trajectories lasting for longer time (with an average trajectory length of >480 frames). Based on its diverse annotation, we present two simple baselines for action recognition and pose estimation, respectively. They leverage cross-label information during training to enhance the feature learning in corresponding visual tasks. Experiments show that they could boost the performance of existing action recognition and pose estimation pipelines. More importantly, they prove the widely ranged annotations in HiEve can improve various video tasks. Furthermore, we conduct extensive experiments to benchmark recent video analysis approaches together with our baseline methods, demonstrating HiEve is a challenging dataset for human-centric video analysis. We expect that the dataset will advance the development of cutting-edge techniques in human-centric analysis and the understanding of complex events. The dataset is available at http://humaninevents.org
Whole-grain Petri nets and processes
Venue: arXiv cs.LO 2023
Year: 2023

We present a formalism for Petri nets based on polynomial-style finite-set configurations and etale maps. The formalism supports both a geometric semantics in the style of Goltz and Reisig (processes are etale maps from graphs) and an algebraic semantics in the style of Meseguer and Montanari, in terms of free coloured props, and allows the following unification: for P a Petri net, the Segal space of P-processes is shown to be the free coloured prop-in-groupoids on P. There is also an unfolding semantics à la Winskel, which bypasses the classical symmetry problems: with the new formalism, every Petri net admits a universal unfolding, which in turn has associated an event structure and a Scott domain. Since everything is encoded with explicit sets, Petri nets and their processes have elements. In particular, individual-token semantics is native. (Collective-token semantics emerges from rather drastic quotient constructions à la Best-Devillers, involving taking π_0 of the groupoids of states.)
Impact of Geo-distribution and Mining Pools on Blockchains: A Study of Ethereum
Venue: arXiv cs.DC 2023
Year: 2023

Given the large adoption and economical impact of permissionless blockchains, the complexity of the underlying systems and the adversarial environment in which they operate, it is fundamental to properly study and understand the emergent behavior and properties of these systems. We describe our experience on a detailed, one-month study of the Ethereum network from several geographically dispersed observation points. We leverage multiple geographic vantage points to assess the key pillars of Ethereum, namely geographical dispersion, network efficiency, blockchain efficiency and security, and the impact of mining pools. Among other new findings, we identify previously undocumented forms of selfish behavior and show that the prevalence of powerful mining pools exacerbates the geographical impact on block propagation delays. Furthermore, we provide a set of open measurement and processing tools, as well as the data set of the collected measurements, in order to promote further research on understanding permissionless blockchains.
Software Implementation of Optimized Bicubic Interpolated Scan Conversion in Echocardiography
Venue: arXiv cs.GR 2023
Year: 2023

This paper introduces a novel approach leveraging objective image quality assessment (IQA) metrics to optimize the outcomes of traditional bicubic (BIC) image interpolation and interpolated scan conversion algorithms. Specifically, feature selection through line chart data visualization and computing the IQA metrics scores are used to estimate the IQA-guided coefficient-k that up-dates the traditional BIC algorithm weighting function. The resulting optimized bicubic (OBIC) algorithm was subjectively and objectively evaluated using natural and ultrasound images. Results showed that the overall performance of the OBIC algorithm was equivalent to 92.22% of 180 occurrences when compared to the BIC algorithm, while it was 57.22% of 180 occurrences when compared to other algorithms. On top of that, the OBIC interpolated scan conversion algorithm generally produced crisper and better contrast cropped ultrasound sectored images than the BIC algorithm, as well as other interpolated scan conversion algorithms mentioned.