OpenRaiser/Intern-Atlas huggingface dataset:
Modeling and mitigating human annotation errors to design efficient stream processing systems with human-in-the-loop machine learning
Venue: arXiv cs.HC 2022
Year: 2022

High-quality human annotations are necessary for creating effective machine learning-driven stream processing systems. We study hybrid stream processing systems based on a Human-In-The-Loop Machine Learning (HITL-ML) paradigm, in which one or many human annotators and an automatic classifier (trained at least partially by the human annotators) label an incoming stream of instances. This is typical of many near-real-time social media analytics and web applications, including annotating social media posts during emergencies by digital volunteer groups. From a practical perspective, low-quality human annotations result in wrong labels for retraining automated classifiers and indirectly contribute to the creation of inaccurate classifiers. Considering human annotation as a psychological process allows us to address these limitations. We show that human annotation quality is dependent on the ordering of instances shown to annotators and can be improved by local changes in the instance sequence/order provided to the annotators, yielding a more accurate annotation of the stream. We adapt a theoretically-motivated human error framework of mistakes and slips for the human annotation task to study the effect of ordering instances (i.e., an "annotation schedule"). Further, we propose an error-avoidance approach to the active learning paradigm for stream processing applications robust to these likely human errors (in the form of slips) when deciding a human annotation schedule. We support the human error framework using crowdsourcing experiments and evaluate the proposed algorithm against standard baselines for active learning via extensive experimentation on classification tasks of filtering relevant social media posts during natural disasters.
RGBT Salient Object Detection: A Large-scale Dataset and Benchmark
Venue: arXiv cs.CV 2022
Year: 2022

Salient object detection in complex scenes and environments is a challenging research topic. Most works focus on RGB-based salient object detection, which limits its performance of real-life applications when confronted with adverse conditions such as dark environments and complex backgrounds. Taking advantage of RGB and thermal infrared images becomes a new research direction for detecting salient object in complex scenes recently, as thermal infrared spectrum imaging provides the complementary information and has been applied to many computer vision tasks. However, current research for RGBT salient object detection is limited by the lack of a large-scale dataset and comprehensive benchmark. This work contributes such a RGBT image dataset named VT5000, including 5000 spatially aligned RGBT image pairs with ground truth annotations. VT5000 has 11 challenges collected in different scenes and environments for exploring the robustness of algorithms. With this dataset, we propose a powerful baseline approach, which extracts multi-level features within each modality and aggregates these features of all modalities with the attention mechanism, for accurate RGBT salient object detection. Extensive experiments show that the proposed baseline approach outperforms the state-of-the-art methods on VT5000 dataset and other two public datasets. In addition, we carry out a comprehensive analysis of different algorithms of RGBT salient object detection on VT5000 dataset, and then make several valuable conclusions and provide some potential research directions for RGBT salient object detection.
Single-Frame based Deep View Synchronization for Unsynchronized Multi-Camera Surveillance
Venue: arXiv cs.CV 2022
Year: 2022

Multi-camera surveillance has been an active research topic for understanding and modeling scenes. Compared to a single camera, multi-cameras provide larger field-of-view and more object cues, and the related applications are multi-view counting, multi-view tracking, 3D pose estimation or 3D reconstruction, etc. It is usually assumed that the cameras are all temporally synchronized when designing models for these multi-camera based tasks. However, this assumption is not always valid,especially for multi-camera systems with network transmission delay and low frame-rates due to limited network bandwidth, resulting in desynchronization of the captured frames across cameras. To handle the issue of unsynchronized multi-cameras, in this paper, we propose a synchronization model that works in conjunction with existing DNN-based multi-view models, thus avoiding the redesign of the whole model. Under the low-fps regime, we assume that only a single relevant frame is available from each view, and synchronization is achieved by matching together image contents guided by epipolar geometry. We consider two variants of the model, based on where in the pipeline the synchronization occurs, scene-level synchronization and camera-level synchronization. The view synchronization step and the task-specific view fusion and prediction step are unified in the same framework and trained in an end-to-end fashion. Our view synchronization models are applied to different DNNs-based multi-camera vision tasks under the unsynchronized setting, including multi-view counting and 3D pose estimation, and achieve good performance compared to baselines.
IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics
Venue: arXiv cs.NE 2022
Year: 2022

Benchmarking and performance analysis play an important role in understanding the behaviour of iterative optimization heuristics (IOHs) such as local search algorithms, genetic and evolutionary algorithms, Bayesian optimization algorithms, etc. This task, however, involves manual setup, execution, and analysis of the experiment on an individual basis, which is laborious and can be mitigated by a generic and well-designed platform. For this purpose, we propose IOHanalyzer, a new user-friendly tool for the analysis, comparison, and visualization of performance data of IOHs. Implemented in R and C++, IOHanalyzer is fully open source. It is available on CRAN and GitHub. IOHanalyzer provides detailed statistics about fixed-target running times and about fixed-budget performance of the benchmarked algorithms with a real-valued codomain, single-objective optimization tasks. Performance aggregation over several benchmark problems is possible, for example in the form of empirical cumulative distribution functions. Key advantages of IOHanalyzer over other performance analysis packages are its highly interactive design, which allows users to specify the performance measures, ranges, and granularity that are most useful for their experiments, and the possibility to analyze not only performance traces, but also the evolution of dynamic state parameters. IOHanalyzer can directly process performance data from the main benchmarking platforms, including the COCO platform, Nevergrad, the SOS platform, and IOHexperimenter. An R programming interface is provided for users preferring to have a finer control over the implemented functionalities.
Automatic Personality Prediction; an Enhanced Method Using Ensemble Modeling
Venue: arXiv cs.CL 2022
Year: 2022

Human personality is significantly represented by those words which he/she uses in his/her speech or writing. As a consequence of spreading the information infrastructures (specifically the Internet and social media), human communications have reformed notably from face to face communication. Generally, Automatic Personality Prediction (or Perception) (APP) is the automated forecasting of the personality on different types of human generated/exchanged contents (like text, speech, image, video, etc.). The major objective of this study is to enhance the accuracy of APP from the text. To this end, we suggest five new APP methods including term frequency vector-based, ontology-based, enriched ontology-based, latent semantic analysis (LSA)-based, and deep learning-based (BiLSTM) methods. These methods as the base ones, contribute to each other to enhance the APP accuracy through ensemble modeling (stacking) based on a hierarchical attention network (HAN) as the meta-model. The results show that ensemble modeling enhances the accuracy of APP.
Solving the Clustered Traveling Salesman Problem via TSP methods
Venue: arXiv cs.AI 2022
Year: 2022

The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.
Revealing the State of the Art of Large-Scale Agile Development Research: A Systematic Mapping Study
Venue: arXiv cs.SE 2022
Year: 2022

Context: Success with agile methods in the small scale has led to an increasing adoption also in large development undertakings and organizations. Recent years have also seen an increasing amount of primary research on the topic, as well as a number of systematic literature reviews. However, there is no systematic overview of the whole research field. Objective: This work identifies, classifies, and evaluates the state of the art of research in large-scale agile development. Method: We conducted a systematic mapping study and rigorously selected 136 studies. We designed a classification framework and extracted key information from the studies. We synthesized the obtained data and created an overview of the state of the art. Results: This work contributes with (i) a description of large-scale agile endeavors reported in the industry, (ii) a systematic map of existing research in the field, (iii) an overview of influential studies, (iv) an overview of the central research themes, and (v) a research agenda for future research. Conclusion: This study portrays the state of the art in large-scale agile development and offers researchers and practitioners a reflection of the past thirteen years of research and practice on the large-scale application of agile methods.
Open Data Quality
Venue: arXiv cs.DB 2022
Year: 2022

The research discusses how (open) data quality could be described, what should be considered developing a data quality management solution and how it could be applied to open data to check its quality. The proposed approach focuses on development of data quality specification which can be executed to get data quality evaluation results, find errors in data and possible problems which must be solved. The proposed approach is applied to several open data sets to evaluate their quality. Open data is very popular, free available for every stakeholder - it is often used to make business decisions. It is important to be sure that this data is trustable and error-free as its quality problems can lead to huge losses.
Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
Venue: arXiv cs.GT 2022
Year: 2022

A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that the egalitarian version of this problem admits a polynomial-time algorithm. For the utilitarian version, we prove that winner determination remains NP-hard, even for the Borda scoring function; however, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We also consider several other optimization criteria for trees: for some we obtain polynomial-time algorithms, while for others we show NP-hardness results.
The Price of Anarchy for Instantaneous Dynamic Equilibria
Venue: arXiv cs.GT 2022
Year: 2022

We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $\mathcal{O}(U\cdot τ)$ for single-sink instances, where $U$ denotes the total inflow volume and $τ$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $Ω(U\cdot\logτ)$.
A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows
Venue: arXiv cs.GT 2022
Year: 2022

Instantaneous dynamic equilibrium (IDE) is a standard game-theoretic concept in dynamic traffic assignment in which individual flow particles myopically select en route currently shortest paths towards their destination. We analyze IDE within the Vickrey bottleneck model, where current travel times along a path consist of the physical travel times plus the sum of waiting times in all the queues along a path. Although IDE have been studied for decades, several fundamental questions regarding equilibrium computation and complexity are not well understood. In particular, all existence results and computational methods are based on fixed-point theorems and numerical discretization schemes and no exact finite time algorithm for equilibrium computation is known to date. As our main result we show that a natural extension algorithm needs only finitely many phases to converge leading to the first finite time combinatorial algorithm computing an IDE. We complement this result by several hardness results showing that computing IDE with natural properties is NP-hard.
How Inclusive Are Wikipedia's Hyperlinks in Articles Covering Polarizing Topics?
Venue: arXiv cs.SI 2022
Year: 2022

Wikipedia relies on an extensive review process to verify that the content of each individual page is unbiased and presents a neutral point of view. Less attention has been paid to possible biases in the hyperlink structure of Wikipedia, which has a significant influence on the user's exploration process when visiting more than one page. The evaluation of hyperlink bias is challenging because it depends on the global view rather than the text of individual pages. In this paper, we focus on the influence of the interconnect topology between articles describing complementary aspects of polarizing topics. We introduce a novel measure of exposure to diverse information to quantify users' exposure to different aspects of a topic throughout an entire surfing session, rather than just one click ahead. We apply this measure to six polarizing topics (e.g., gun control and gun right), and we identify cases in which the network topology significantly limits the exposure of users to diverse information on the topic, encouraging users to remain in a knowledge bubble. Our findings demonstrate the importance of evaluating Wikipedia's network structure in addition to the extensive review of individual articles.
EllSeg: An Ellipse Segmentation Framework for Robust Gaze Tracking
Venue: arXiv cs.CV 2022
Year: 2022

Ellipse fitting, an essential component in pupil or iris tracking based video oculography, is performed on previously segmented eye parts generated using various computer vision techniques. Several factors, such as occlusions due to eyelid shape, camera position or eyelashes, frequently break ellipse fitting algorithms that rely on well-defined pupil or iris edge segments. In this work, we propose training a convolutional neural network to directly segment entire elliptical structures and demonstrate that such a framework is robust to occlusions and offers superior pupil and iris tracking performance (at least 10$\%$ and 24$\%$ increase in pupil and iris center detection rate respectively within a two-pixel error margin) compared to using standard eye parts segmentation for multiple publicly available synthetic segmentation datasets.
A Note on Stabbing Convex Bodies with Points, Lines, and Flats
Venue: arXiv cs.CG 2022
Year: 2022

$\newcommand{\eps}{\varepsilon}\newcommand{\tldO}{\widetilde{O}}$Consider the problem of constructing weak $\eps$-nets where the stabbing elements are lines or $k$-flats instead of points. We study this problem in the simplest setting where it is still interesting -- namely, the uniform measure of volume over the hypercube $[0,1]^d\bigr.$. Specifically, a $(k,\eps)$-net is a set of $k$-flats, such that any convex body in $[0,1]^d$ of volume larger than $\eps$ is stabbed by one of these $k$-flats. We show that for $k \geq 1$, one can construct $(k,\eps)$-nets of size $O(1/\eps^{1-k/d})$. We also prove that any such net must have size at least $Ω(1/\eps^{1-k/d})$. As a concrete example, in three dimensions all $\eps$-heavy bodies in $[0,1]^3$ can be stabbed by $Θ(1/\eps^{2/3})$ lines. Note, that these bounds are \emph{sublinear} in $1/\eps$, and are thus somewhat surprising. The new construction also works for points providing a weak $\eps$-net of size $O(\tfrac{1}{\eps}\log^{d-1} \tfrac{1}{\eps} )$.
Graph Neural Network for Video Relocalization
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we focus on video relocalization task, which uses a query video clip as input to retrieve a semantic relative video clip in another untrimmed long video. we find that in video relocalization datasets, there exists a phenomenon showing that there does not exist consistent relationship between feature similarity by frame and feature similarity by video, which affects the feature fusion among frames. However, existing video relocalization methods do not fully consider it. Taking this phenomenon into account, in this article, we treat video features as a graph by concatenating the query video feature and proposal video feature along time dimension, where each timestep is treated as a node, each row of the feature matrix is treated as feature of each node. Then, with the power of graph neural networks, we propose a Multi-Graph Feature Fusion Module to fuse the relation feature of this graph. After evaluating our method on ActivityNet v1.2 dataset and Thumos14 dataset, we find that our proposed method outperforms the state of art methods.
Program algebra for random access machine programs
Venue: arXiv cs.PL 2022
Year: 2022

This paper presents an algebraic theory of instruction sequences with instructions for a random access machine (RAM) as basic instructions, the behaviours produced by the instruction sequences concerned under execution, and the interaction between such behaviours and RAM memories. This theory provides a setting for the development of theory in areas such as computational complexity and analysis of algorithms that distinguishes itself by offering the possibility of equational reasoning to establish whether an instruction sequence computes a given function and being more general than the setting provided by any known version of the RAM model of computation. In this setting, a semi-realistic version of the RAM model of computation and a bit-oriented time complexity measure for this version are introduced. Under the time measure concerned, semi-realistic RAMs can be simulated by multi-tape Turing machines with quadratic time overhead.
Stick graphs: examples and counter-examples
Venue: arXiv cs.DM 2022
Year: 2022

Grid intersection graphs are the intersection graphs of vertical and horizontal segments in the plane. When the bottom and respectively left endpoints of the vertical and horizontals segments belong to a line with negative slope, the graph is called a Stick graph. Very few results exist on Stick graphs: only small classes of Stick graphs have been identified; recognizing Stick graphs is an open problem; and even building examples of graphs that are not Stick graphs is quite tricky. In this paper, we first prove that the complements of circle graphs and of circular arc graphs are Stick graphs. Then, we propose two certificates allowing to decide that a graph is not a Stick graph, and use them to build new examples of non-Stick graphs. It turns out that these examples of non-Stick graphs, as well as all those from literature, have long holes. We thus also investigate the place of chordal grid intersection graphs in the hierarchy of classes built around Stick graphs.
Learnable Descent Algorithm for Nonsmooth Nonconvex Image Reconstruction
Venue: arXiv cs.CV 2022
Year: 2022

We propose a general learning based framework for solving nonsmooth and nonconvex image reconstruction problems. We model the regularization function as the composition of the $l_{2,1}$ norm and a smooth but nonconvex feature mapping parametrized as a deep convolutional neural network. We develop a provably convergent descent-type algorithm to solve the nonsmooth nonconvex minimization problem by leveraging the Nesterov's smoothing technique and the idea of residual learning, and learn the network parameters such that the outputs of the algorithm match the references in training data. Our method is versatile as one can employ various modern network structures into the regularization, and the resulting network inherits the guaranteed convergence of the algorithm. We also show that the proposed network is parameter-efficient and its performance compares favorably to the state-of-the-art methods in a variety of image reconstruction problems in practice.
Approximation Benefits of Policy Gradient Methods with Aggregated States
Venue: arXiv cs.LG 2022
Year: 2022

Folklore suggests that policy gradient can be more robust to misspecification than its relative, approximate policy iteration. This paper studies the case of state-aggregated representations, where the state space is partitioned and either the policy or value function approximation is held constant over partitions. This paper shows a policy gradient method converges to a policy whose regret per-period is bounded by $ε$, the largest difference between two elements of the state-action value function belonging to a common partition. With the same representation, both approximate policy iteration and approximate value iteration can produce policies whose per-period regret scales as $ε/(1-γ)$, where $γ$ is a discount factor. Faced with inherent approximation error, methods that locally optimize the true decision-objective can be far more robust.