OpenRaiser/Intern-Atlas huggingface dataset:
On Nash-Solvability of Finite Two-Person Tight Vector Game Forms
Venue: arXiv cs.GT 2022
Year: 2022

We consider finite two-person normal form games. The following four properties of their game forms are equivalent: (i) Nash-solvability, (ii) zero-sum-solvability, (iii) win-lose-solvability, and (iv) tightness. For (ii, iii, iv) this was shown by Edmonds and Fulkerson in 1970. Then, in 1975, (i) was added to this list and it was also shown that these results cannot be generalized for $n$-person case with $n > 2$. In 1990, tightness was extended to vector game forms ($v$-forms) and it was shown that such $v$-tightness and zero-sum-solvability are still equivalent, yet, do not imply Nash-solvability. These results are applicable to several classes of stochastic games with perfect information. Here we suggest one more extension of tightness introducing $v^+$-tight vector game forms ($v^+$-forms). We show that such $v^+$-tightness and Nash-solvability are equivalent in case of weakly rectangular game forms and positive cost functions. This result allows us to reduce the so-called bi-shortest path conjecture to $v^+$-tightness of $v^+$-forms. However, both (equivalent) statements remain open.
A Real-time Calculus Approach for Integrating Sporadic Events in Time-triggered Systems
Venue: arXiv cs.NI 2022
Year: 2022

In time-triggered systems, where the schedule table is predefined and statically configured at design time, sporadic event-triggered (ET) tasks are handled within specially dedicated slots or when time-triggered (TT) tasks finish their execution early. We introduce a new paradigm for synthesizing TT schedules that guarantee the correct temporal behavior of TT tasks and the schedulability of sporadic ET tasks with arbitrary deadlines. The approach first expresses a constraint for the TT task schedule in the form of a maximal affine envelope that guarantees that as long as the schedule generation respects this envelope, all sporadic ET tasks meet their deadline. The second step consists of modeling this envelope as a burst limiting constraint and building the TT schedule via simulating a modified Least-Laxity-First (LLF) scheduler. Using this novel technique, we show that we achieve equal or better schedulability and a faster schedule generation for most use-cases compared to simple polling approaches. Moreover, we present an extension to our method that finds the most favourable schedule for TT tasks with respect to ET schedulability, thus increasing the probability of the computed TT schedule remaining feasible when ET tasks are later added or changed.
Addressing Tactic Volatility in Self-Adaptive Systems Using Evolved Recurrent Neural Networks and Uncertainty Reduction Tactics
Venue: arXiv cs.LG 2022
Year: 2022

Self-adaptive systems frequently use tactics to perform adaptations. Tactic examples include the implementation of additional security measures when an intrusion is detected, or activating a cooling mechanism when temperature thresholds are surpassed. Tactic volatility occurs in real-world systems and is defined as variable behavior in the attributes of a tactic, such as its latency or cost. A system's inability to effectively account for tactic volatility adversely impacts its efficiency and resiliency against the dynamics of real-world environments. To enable systems' efficiency against tactic volatility, we propose a Tactic Volatility Aware (TVA-E) process utilizing evolved Recurrent Neural Networks (eRNN) to provide accurate tactic predictions. TVA-E is also the first known process to take advantage of uncertainty reduction tactics to provide additional information to the decision-making process and reduce uncertainty. TVA-E easily integrates into popular adaptation processes enabling it to immediately benefit a large number of existing self-adaptive systems. Simulations using 52,106 tactic records demonstrate that: I) eRNN is an effective prediction mechanism, II) TVA-E represents an improvement over existing state-of-the-art processes in accounting for tactic volatility, and III) Uncertainty reduction tactics are beneficial in accounting for tactic volatility. The developed dataset and tool can be found at https://tacticvolatility.github.io/
Future Object Detection with Spatiotemporal Transformers
Venue: arXiv cs.CV 2022
Year: 2022

We propose the task Future Object Detection, in which the goal is to predict the bounding boxes for all visible objects in a future video frame. While this task involves recognizing temporal and kinematic patterns, in addition to the semantic and geometric ones, it only requires annotations in the standard form for individual, single (future) frames, in contrast to expensive full sequence annotations. We propose to tackle this task with an end-to-end method, in which a detection transformer is trained to directly output the future objects. In order to make accurate predictions about the future, it is necessary to capture the dynamics in the scene, both object motion and the movement of the ego-camera. To this end, we extend existing detection transformers in two ways. First, we experiment with three different mechanisms that enable the network to spatiotemporally process multiple frames. Second, we provide ego-motion information to the model in a learnable manner. We show that both of these extensions improve the future object detection performance substantially. Our final approach learns to capture the dynamics and makes predictions on par with an oracle for prediction horizons up to 100 ms, and outperforms all baselines for longer prediction horizons. By visualizing the attention maps, we observe that a form of tracking emerges within the network. Code is available at github.com/atonderski/future-object-detection.
Monocular Depth Estimation Using Cues Inspired by Biological Vision Systems
Venue: arXiv cs.CV 2022
Year: 2022

Monocular depth estimation (MDE) aims to transform an RGB image of a scene into a pixelwise depth map from the same camera view. It is fundamentally ill-posed due to missing information: any single image can have been taken from many possible 3D scenes. Part of the MDE task is, therefore, to learn which visual cues in the image can be used for depth estimation, and how. With training data limited by cost of annotation or network capacity limited by computational power, this is challenging. In this work we demonstrate that explicitly injecting visual cue information into the model is beneficial for depth estimation. Following research into biological vision systems, we focus on semantic information and prior knowledge of object sizes and their relations, to emulate the biological cues of relative size, familiar size, and absolute size. We use state-of-the-art semantic and instance segmentation models to provide external information, and exploit language embeddings to encode relational information between classes. We also provide a prior on the average real-world size of objects. This external information overcomes the limitation in data availability, and ensures that the limited capacity of a given network is focused on known-helpful cues, therefore improving performance. We experimentally validate our hypothesis and evaluate the proposed model on the widely used NYUD2 indoor depth estimation benchmark. The results show improvements in depth prediction when the semantic information, size prior and instance size are explicitly provided along with the RGB images, and our method can be easily adapted to any depth estimation system.
Staying the course: Locating equilibria of dynamical systems on Riemannian manifolds defined by point-clouds
Venue: arXiv cs.LG 2022
Year: 2022

We introduce a method to successively locate equilibria (steady states) of dynamical systems on Riemannian manifolds. The manifolds need not be characterized by an a priori known atlas or by the zeros of a smooth map. Instead, they can be defined by point-clouds and sampled as needed through an iterative process. If the manifold is an Euclidean space, our method follows isoclines, curves along which the direction of the vector field $X$ is constant. For a generic vector field $X$, isoclines are smooth curves and every equilibrium lies on isoclines. We generalize the definition of isoclines to Riemannian manifolds through the use of parallel transport: generalized isoclines are curves along which the directions of $X$ are parallel transports of each other. As in the Euclidean case, generalized isoclines of generic vector fields $X$ are smooth curves that connect equilibria of $X$. Our algorithm can be regarded as an extension of the method of Newton trajectories to the manifold setting when the manifold is unknown. This work is motivated by computational statistical mechanics, specifically high dimensional (stochastic) differential equations that model the dynamics of molecular systems. Often, these dynamics concentrate near low-dimensional manifolds and have transitions (saddle points with a single unstable direction) between metastable equilibria. We employ iteratively sampled data and isoclines to locate these saddle points. Coupling a black-box sampling scheme (e.g., Markov chain Monte Carlo) with manifold learning techniques (diffusion maps in the case presented here), we show that our method reliably locates equilibria of $X$.
WaBERT: A Low-resource End-to-end Model for Spoken Language Understanding and Speech-to-BERT Alignment
Venue: arXiv cs.CL 2022
Year: 2022

Historically lower-level tasks such as automatic speech recognition (ASR) and speaker identification are the main focus in the speech field. Interest has been growing in higher-level spoken language understanding (SLU) tasks recently, like sentiment analysis (SA). However, improving performances on SLU tasks remains a big challenge. Basically, there are two main methods for SLU tasks: (1) Two-stage method, which uses a speech model to transfer speech to text, then uses a language model to get the results of downstream tasks; (2) One-stage method, which just fine-tunes a pre-trained speech model to fit in the downstream tasks. The first method loses emotional cues such as intonation, and causes recognition errors during ASR process, and the second one lacks necessary language knowledge. In this paper, we propose the Wave BERT (WaBERT), a novel end-to-end model combining the speech model and the language model for SLU tasks. WaBERT is based on the pre-trained speech and language model, hence training from scratch is not needed. We also set most parameters of WaBERT frozen during training. By introducing WaBERT, audio-specific information and language knowledge are integrated in the short-time and low-resource training process to improve results on the dev dataset of SLUE SA tasks by 1.15% of recall score and 0.82% of F1 score. Additionally, we modify the serial Continuous Integrate-and-Fire (CIF) mechanism to achieve the monotonic alignment between the speech and text modalities.
Some Optimization Solutions for Relief Distribution
Venue: arXiv cs.DS 2022
Year: 2022

Humanitarian logistics remain a challenging area of application for operations research. In relief distribution, the main goal is to deliver all the supplies to those that are in need in the fastest way possible. In this paper, we present different optimization solutions for relief distribution. We present a formalization of the three main problems in the humanitarian logistics aspect of relief distribution. We identify the optimal location of the distribution centers. We match the number of supplies to the number of demands for each distribution center based on the distribution of demands. We provide the assignment of tasks to delivery fleet according to the location and the road network of the region. For each delivery truck, we provide an optimal sequence of visits to pre-assigned distribution centers.
Taygete at SemEval-2022 Task 4: RoBERTa based models for detecting Patronising and Condescending Language
Venue: arXiv cs.CL 2022
Year: 2022

This work describes the development of different models to detect patronising and condescending language within extracts of news articles as part of the SemEval 2022 competition (Task-4). This work explores different models based on the pre-trained RoBERTa language model coupled with LSTM and CNN layers. The best models achieved 15$^{th}$ rank with an F1-score of 0.5924 for subtask-A and 12$^{th}$ in subtask-B with a macro-F1 score of 0.3763.
Fourier Imager Network (FIN): A deep neural network for hologram reconstruction with superior external generalization
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning-based image reconstruction methods have achieved remarkable success in phase recovery and holographic imaging. However, the generalization of their image reconstruction performance to new types of samples never seen by the network remains a challenge. Here we introduce a deep learning framework, termed Fourier Imager Network (FIN), that can perform end-to-end phase recovery and image reconstruction from raw holograms of new types of samples, exhibiting unprecedented success in external generalization. FIN architecture is based on spatial Fourier transform modules that process the spatial frequencies of its inputs using learnable filters and a global receptive field. Compared with existing convolutional deep neural networks used for hologram reconstruction, FIN exhibits superior generalization to new types of samples, while also being much faster in its image inference speed, completing the hologram reconstruction task in ~0.04 s per 1 mm^2 of the sample area. We experimentally validated the performance of FIN by training it using human lung tissue samples and blindly testing it on human prostate, salivary gland tissue and Pap smear samples, proving its superior external generalization and image reconstruction speed. Beyond holographic microscopy and quantitative phase imaging, FIN and the underlying neural network architecture might open up various new opportunities to design broadly generalizable deep learning models in computational imaging and machine vision fields.
Uniform Operational Consistent Query Answering
Venue: arXiv cs.DB 2022
Year: 2022

Operational consistent query answering (CQA) is a recent framework for CQA, based on revised definitions of repairs and consistent answers, which opens up the possibility of efficient approximations with explicit error guarantees. The main idea is to iteratively apply operations (e.g., fact deletions), starting from an inconsistent database, until we reach a database that is consistent w.r.t. the given set of constraints. This gives us the flexibility of choosing the probability with which we apply an operation, which in turn allows us to calculate the probability of an operational repair, and thus, the probability with which a consistent answer is entailed. A natural way of assigning probabilities to operations is by targeting the uniform probability distribution over a reasonable space such as the set of operational repairs, the set of sequences of operations that lead to an operational repair, and the set of available operations at a certain step of the repairing process. This leads to what we generally call uniform operational CQA. The goal of this work is to perform a data complexity analysis of both exact and approximate uniform operational CQA, focusing on functional dependencies (and subclasses thereof), and conjunctive queries. The main outcome of our analysis (among other positive and negative results), is that uniform operational CQA pushes the efficiency boundaries further by ensuring the existence of efficient approximation schemes in scenarios that go beyond the simple case of primary keys, which seems to be the limit of the classical approach to CQA.
Spacing Loss for Discovering Novel Categories
Venue: arXiv cs.CV 2022
Year: 2022

Novel Class Discovery (NCD) is a learning paradigm, where a machine learning model is tasked to semantically group instances from unlabeled data, by utilizing labeled instances from a disjoint set of classes. In this work, we first characterize existing NCD approaches into single-stage and two-stage methods based on whether they require access to labeled and unlabeled data together while discovering new classes. Next, we devise a simple yet powerful loss function that enforces separability in the latent space using cues from multi-dimensional scaling, which we refer to as Spacing Loss. Our proposed formulation can either operate as a standalone method or can be plugged into existing methods to enhance them. We validate the efficacy of Spacing Loss with thorough experimental evaluation across multiple settings on CIFAR-10 and CIFAR-100 datasets.
Modelling graph dynamics in fraud detection with "Attention"
Venue: arXiv cs.LG 2022
Year: 2022

At online retail platforms, detecting fraudulent accounts and transactions is crucial to improve customer experience, minimize loss, and avoid unauthorized transactions. Despite the variety of different models for deep learning on graphs, few approaches have been proposed for dealing with graphs that are both heterogeneous and dynamic. In this paper, we propose DyHGN (Dynamic Heterogeneous Graph Neural Network) and its variants to capture both temporal and heterogeneous information. We first construct dynamic heterogeneous graphs from registration and transaction data from eBay. Then, we build models with diachronic entity embedding and heterogeneous graph transformer. We also use model explainability techniques to understand the behaviors of DyHGN-* models. Our findings reveal that modelling graph dynamics with heterogeneous inputs need to be conducted with "attention" depending on the data structure, distribution, and computation cost.
DFAM-DETR: Deformable feature based attention mechanism DETR on slender object detection
Venue: arXiv cs.CV 2022
Year: 2022

Object detection is one of the most significant aspects of computer vision, and it has achieved substantial results in a variety of domains. It is worth noting that there are few studies focusing on slender object detection. CNNs are widely employed in object detection, however it performs poorly on slender object detection due to the fixed geometric structure and sampling points. In comparison, Deformable DETR has the ability to obtain global to specific features. Even though it outperforms the CNNs in slender objects detection accuracy and efficiency, the results are still not satisfactory. Therefore, we propose Deformable Feature based Attention Mechanism (DFAM) to increase the slender object detection accuracy and efficiency of Deformable DETR. The DFAM has adaptive sampling points of deformable convolution and attention mechanism that aggregate information from the entire input sequence in the backbone network. This improved detector is named as Deformable Feature based Attention Mechanism DETR (DFAM- DETR). Results indicate that DFAM-DETR achieves outstanding detection performance on slender objects.
The mixed search game against an agile and visible fugitive is monotone
Venue: arXiv cs.DM 2022
Year: 2022

We consider the mixed search game against an agile and visible fugitive. This is the variant of the classic fugitive search game on graphs where searchers may be placed to (or removed from) the vertices or slide along edges. Moreover, the fugitive resides on the edges of the graph and can move at any time along unguarded paths. The mixed search number against an agile and visible fugitive of a graph $G$, denoted $avms(G)$, is the minimum number of searchers required to capture to fugitive in this graph searching variant. Our main result is that this graph searching variant is monotone in the sense that the number of searchers required for a successful search strategy does not increase if we restrict the search strategies to those that do not permit the fugitive to visit an already clean edge. This means that mixed search strategies against an agile and visible fugitive can be polynomially certified, and therefore that the problem of deciding, given a graph $G$ and an integer $k,$ whether $avms(G)\leq k$ is in NP. Our proof is based on the introduction of the notion of tight bramble, that serves as an obstruction for the corresponding search parameter. Our results imply that for a graph $G$, $avms(G)$ is equal to the Cartesian tree product number of $G$ that is the minimum $k$ for which $G$ is a minor of the Cartesian product of a tree and a clique on $k$ vertices.
EmbedTrack -- Simultaneous Cell Segmentation and Tracking Through Learning Offsets and Clustering Bandwidths
Venue: arXiv cs.CV 2022
Year: 2022

A systematic analysis of the cell behavior requires automated approaches for cell segmentation and tracking. While deep learning has been successfully applied for the task of cell segmentation, there are few approaches for simultaneous cell segmentation and tracking using deep learning. Here, we present EmbedTrack, a single convolutional neural network for simultaneous cell segmentation and tracking which predicts easy to interpret embeddings. As embeddings, offsets of cell pixels to their cell center and bandwidths are learned. We benchmark our approach on nine 2D data sets from the Cell Tracking Challenge, where our approach performs on seven out of nine data sets within the top 3 contestants including three top 1 performances. The source code is publicly available at https://git.scc.kit.edu/kit-loe-ge/embedtrack.
Pathways through Conspiracy: The Evolution of Conspiracy Radicalization through Engagement in Online Conspiracy Discussions
Venue: arXiv cs.CY 2022
Year: 2022

The disruptive offline mobilization of participants in online conspiracy theory (CT) discussions has highlighted the importance of understanding how online users may form radicalized conspiracy beliefs. While prior work researched the factors leading up to joining online CT discussions and provided theories of how conspiracy beliefs form, we have little understanding of how conspiracy radicalization evolves after users join CT discussion communities. In this paper, we provide the empirical modeling of various radicalization phases in online CT discussion participants. To unpack how conspiracy engagement is related to radicalization, we first characterize the users' journey through CT discussions via conspiracy engagement pathways. Specifically, by studying 36K Reddit users through their 169M contributions, we uncover four distinct pathways of conspiracy engagement: steady high, increasing, decreasing, and steady low. We further model three successive stages of radicalization guided by prior theoretical works. Specific sub-populations of users, namely those on steady high and increasing conspiracy engagement pathways, progress successively through various radicalization stages. In contrast, users on the decreasing engagement pathway show distinct behavior: they limit their CT discussions to specialized topics, participate in diverse discussion groups, and show reduced conformity with conspiracy subreddits. By examining users who disengage from online CT discussions, this paper provides promising insights about conspiracy recovery process.