OpenRaiser/Intern-Atlas huggingface dataset:
Leaving Goals on the Pitch: Evaluating Decision Making in Soccer
Venue: arXiv cs.AI 2023
Year: 2023

Analysis of the popular expected goals (xG) metric in soccer has determined that a (slightly) smaller number of high-quality attempts will likely yield more goals than a slew of low-quality ones. This observation has driven a change in shooting behavior. Teams are passing up on shots from outside the penalty box, in the hopes of generating a better shot closer to goal later on. This paper evaluates whether this decrease in long-distance shots is warranted. Therefore, we propose a novel generic framework to reason about decision-making in soccer by combining techniques from machine learning and artificial intelligence (AI). First, we model how a team has behaved offensively over the course of two seasons by learning a Markov Decision Process (MDP) from event stream data. Second, we use reasoning techniques arising from the AI literature on verification to each team's MDP. This allows us to reason about the efficacy of certain potential decisions by posing counterfactual questions to the MDP. Our key conclusion is that teams would score more goals if they shot more often from outside the penalty box in a small number of team-specific locations. The proposed framework can easily be extended and applied to analyze other aspects of the game.
Semantical Investigations on Non-classical Logics with Recovery Operators: Negation
Venue: arXiv cs.LO 2023
Year: 2023

We investigate mathematical structures that provide natural semantics for families of (quantified) non-classical logics featuring special unary connectives, known as recovery operators, that allow us to 'recover' the properties of classical logic in a controlled manner. These structures are known as topological Boolean algebras, which are Boolean algebras extended with additional operations subject to specific conditions of a topological nature. In this study we focus on the paradigmatic case of negation. We demonstrate how these algebras are well-suited to provide a semantics for some families of paraconsistent Logics of Formal Inconsistency and paracomplete Logics of Formal Undeterminedness. These logics feature recovery operators used to earmark propositions that behave 'classically' when interacting with non-classical negations. Unlike traditional semantical investigations, which are carried out in natural language (extended with mathematical shorthand), our formal meta-language is a system of higher-order logic (HOL) for which automated reasoning tools exist. In our approach, topological Boolean algebras are encoded as algebras of sets via their Stone-type representation. We use our higher-order meta-logic to define and interrelate several transformations on unary set operations, which naturally give rise to a topological cube of opposition. Additionally, our approach enables a uniform characterization of propositional, first-order, and higher-order quantification, including restrictions to constant and varying domains. With this work, we aim to make a case for the utilization of automated theorem proving technology for conducting computer-supported research in non-classical logics. All the results presented in this paper have been formally verified, and in many cases obtained, using the Isabelle/HOL proof assistant.
Proof of Travel for Trust-Based Data Validation in V2I Communication
Venue: arXiv cs.CR 2023
Year: 2023

Previous work on misbehavior detection and trust management for Vehicle-to-Everything (V2X) communication security is effective in identifying falsified and malicious V2X data. Each vehicle in a given region can be a witness to report on the misbehavior of other nearby vehicles, which will then be added to a "blacklist." However, there may not exist enough witness vehicles that are willing to opt-in in the early stage of connected-vehicle deployment. In this paper, we propose a "whitelisting" approach to V2X security, titled Proof-of-Travel (POT), which leverages the support of roadside infrastructure. Our goal is to transform the power of cryptography techniques embedded within Vehicle-to-Infrastructure (V2I) protocols into game-theoretic mechanisms to incentivize connected-vehicle data sharing and validate data trustworthiness simultaneously. The key idea is to determine the reputation of and the contribution made by a vehicle based on its distance traveled and the information it shared through V2I channels. In particular, the total vehicle miles traveled for a vehicle must be testified by digital signatures signed by each infrastructure component along the path of its movement. While building a chain of proofs of spatial movement creates burdens for malicious vehicles, acquiring proofs does not result in extra costs for normal vehicles, which naturally want to move from the origin to the destination. The POT protocol is used to enhance the security of previous voting-based data validation algorithms for V2I crowdsensing applications. For the POT-enhanced voting, we prove that all vehicles choosing to cheat are not a pure Nash equilibrium using game-theoretic analysis. Simulation results suggest that the POT-enhanced voting is more robust to malicious data.
Learning from Censored and Dependent Data: The case of Linear Dynamics
Venue: arXiv cs.LG 2023
Year: 2023

Observations from dynamical systems often exhibit irregularities, such as censoring, where values are recorded only if they fall within a certain range. Censoring is ubiquitous in practice, due to saturating sensors, limit-of-detection effects, and image-frame effects. In light of recent developments on learning linear dynamical systems (LDSs), and on censored statistics with independent data, we revisit the decades-old problem of learning an LDS, from censored observations (Lee and Maddala (1985); Zeger and Brookmeyer (1986)). Here, the learner observes the state $x_t \in \mathbb{R}^d$ if and only if $x_t$ belongs to some set $S_t \subseteq \mathbb{R}^d$. We develop the first computationally and statistically efficient algorithm for learning the system, assuming only oracle access to the sets $S_t$. Our algorithm, Stochastic Online Newton with Switching Gradients, is a novel second-order method that builds on the Online Newton Step (ONS) of Hazan et al. (2007). Our Switching-Gradient scheme does not always use (stochastic) gradients of the function we want to optimize, which we call "censor-aware" function. Instead, in each iteration, it performs a simple test to decide whether to use the censor-aware, or another "censor-oblivious" function, for getting a stochastic gradient. In our analysis, we consider a "generic" Online Newton method, which uses arbitrary vectors instead of gradients, and we prove an error-bound for it. This can be used to appropriately design these vectors, leading to our Switching-Gradient scheme. This framework significantly deviates from the recent long line of works on censored statistics (e.g., Daskalakis et al. (2018); Kontonis et al. (2019); Daskalakis et al. (2019)), which apply Stochastic Gradient Descent (SGD), and their analysis reduces to establishing conditions for off-the-shelf SGD-bounds.
Lessons on Parameter Sharing across Layers in Transformers
Venue: arXiv cs.CL 2023
Year: 2023

We propose a parameter sharing method for Transformers (Vaswani et al., 2017). The proposed approach relaxes a widely used technique, which shares parameters for one layer with all layers such as Universal Transformers (Dehghani et al., 2019), to increase the efficiency in the computational time. We propose three strategies: Sequence, Cycle, and Cycle (rev) to assign parameters to each layer. Experimental results show that the proposed strategies are efficient in the parameter size and computational time. Moreover, we indicate that the proposed strategies are also effective in the configuration where we use many training data such as the recent WMT competition.
Not All Requirements Prioritization Criteria Are Equal at All Times: A Quantitative Analysis
Venue: arXiv cs.SE 2023
Year: 2023

Requirement prioritization is recognized as an important decision-making activity in requirements engineering and software development. Requirement prioritization is applied to determine which requirements should be implemented and released. In order to prioritize requirements, there are several approaches/techniques/tools that use different requirements prioritization criteria, which are often identified by gut feeling instead of an in-depth analysis of which criteria are most important to use. Therefore, in this study we investigate which requirements prioritization criteria are most important to use in industry when determining which requirements are implemented and released, and if the importance of the criteria change depending on how far a requirement has reached in the development process. We conducted a quantitative study of one completed project from one software developing company by extracting 32,139 requirements prioritization decisions based on eight requirements prioritization criteria for 11,110 requirements. The results show that not all requirements prioritization criteria are equally important, and this change depending on how far a requirement has reached in the development process.
Holistic Guidance for Occluded Person Re-Identification
Venue: arXiv cs.CV 2023
Year: 2023

In real-world video surveillance applications, person re-identification (ReID) suffers from the effects of occlusions and detection errors. Despite recent advances, occlusions continue to corrupt the features extracted by state-of-art CNN backbones, and thereby deteriorate the accuracy of ReID systems. To address this issue, methods in the literature use an additional costly process such as pose estimation, where pose maps provide supervision to exclude occluded regions. In contrast, we introduce a novel Holistic Guidance (HG) method that relies only on person identity labels, and on the distribution of pairwise matching distances of datasets to alleviate the problem of occlusion, without requiring additional supervision. Hence, our proposed student-teacher framework is trained to address the occlusion problem by matching the distributions of between- and within-class distances (DCDs) of occluded samples with that of holistic (non-occluded) samples, thereby using the latter as a soft labeled reference to learn well separated DCDs. This approach is supported by our empirical study where the distribution of between- and within-class distances between images have more overlap in occluded than holistic datasets. In particular, features extracted from both datasets are jointly learned using the student model to produce an attention map that allows separating visible regions from occluded ones. In addition to this, a joint generative-discriminative backbone is trained with a denoising autoencoder, allowing the system to self-recover from occlusions. Extensive experiments on several challenging public datasets indicate that the proposed approach can outperform state-of-the-art methods on both occluded and holistic datasets
Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time
Venue: arXiv cs.DS 2023
Year: 2023

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of $23.313 + ε$, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of $11.657$; and a $(4 + O(ε))$-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of $e + ε$ in $O_ε(n \log(n))$ time, close to the best known expected ratio of $e - 0.121$ in polynomial time.
On Existence of Truthful Fair Cake Cutting Mechanisms
Venue: arXiv cs.GT 2023
Year: 2023

We study the fair division problem on divisible heterogeneous resources (the cake cutting problem) with strategic agents, where each agent can manipulate his/her private valuation in order to receive a better allocation. A (direct-revelation) mechanism takes agents' reported valuations as input and outputs an allocation that satisfies a given fairness requirement. A natural and fundamental open problem, first raised by [Chen et al., 2010] and subsequently raised by [Procaccia, 2013] [Aziz and Ye, 2014] [Branzei and Miltersen, 2015] [Menon and Larson, 2017] [Bei et al., 2017] [Bei et al., 2020], etc., is whether there exists a deterministic, truthful and envy-free (or even proportional) cake cutting mechanism. In this paper, we resolve this open problem by proving that there does not exist a deterministic, truthful and proportional cake cutting mechanism, even in the special case where all of the following hold: 1) there are only two agents; 2) agents' valuations are piecewise-constant; 3) agents are hungry. The impossibility result extends to the case where the mechanism is allowed to leave some part of the cake unallocated. We also present a truthful and envy-free mechanism when each agent's valuation is piecewise-constant and monotone. However, if we require Pareto-optimality, we show that truthful is incompatible with approximate proportionality for any positive approximation ratio under this setting. To circumvent this impossibility result, motivated by the kind of truthfulness possessed by the I-cut-you-choose protocol, we propose a weaker notion of truthfulness: the proportional risk-averse truthfulness. We show that several well-known algorithms do not have this truthful property. We propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.
Performance Comparison Between A Simple Full-Duplex Multi-Antenna Relay And A Passive Reflecting Intelligent Surface
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we propose to investigate a single RF chain multi-antenna full-duplex (FD) relay built with $b$-bit analog phase shifters and passive self-interference cancellation. Next, assuming only passive self-interference cancellation at the FD relay, we derive the achievable data rate of a system comprised of a source, the proposed FD relay, and a destination. We then compare the achievable data rate of the proposed FD relaying system with the achievable data rate of the same system but with the FD relay replaced by an ideal passive RIS. Our results show that the proposed relaying system with 2-bit quantized analog phase shifters significantly outperforms the RIS-assisted system. In fact, the performance gains are so large, at least for small to intermediate numbers of antenna elements, that we believe it makes this result of interest to the wireless community. The proposed FD relay can also be built with reconfigurable holographic surfaces, one surface for the transmit-side and one for the receive-side. For such a scenario, we derive the energy efficiency of the relay-assisted system and compare it with the RIS-assisted system. Our numerical results show that the energy efficiency of the relay-assisted system built with reconfigurable holographic surfaces is significantly higher than the energy efficiency of the RIS-assisted system. Intuitively, the RIS system is at a disadvantage since there the total transmit power $P_T$ is used entirely by the source, whereas in the FD relaying system the total transmit power $P_T$ is shared by the source and the FD relay in addition to the noise-cleansing process performed by the decode-and-forwarding at the FD relay.
Towards Standardising Reinforcement Learning Approaches for Production Scheduling Problems
Venue: arXiv cs.LG 2023
Year: 2023

Recent years have seen a rise in interest in terms of using machine learning, particularly reinforcement learning (RL), for production scheduling problems of varying degrees of complexity. The general approach is to break down the scheduling problem into a Markov Decision Process (MDP), whereupon a simulation implementing the MDP is used to train an RL agent. Since existing studies rely on (sometimes) complex simulations for which the code is unavailable, the experiments presented are hard, or, in the case of stochastic environments, impossible to reproduce accurately. Furthermore, there is a vast array of RL designs to choose from. To make RL methods widely applicable in production scheduling and work out their strength for the industry, the standardisation of model descriptions - both production setup and RL design - and validation scheme are a prerequisite. Our contribution is threefold: First, we standardize the description of production setups used in RL studies based on established nomenclature. Secondly, we classify RL design choices from existing publications. Lastly, we propose recommendations for a validation scheme focusing on reproducibility and sufficient benchmarking.
Print Your Money: Cash-Like Experiences with Digital Money
Venue: arXiv cs.HC 2023
Year: 2023

The use of digital money has become increasingly popular, but it comes with certain drawbacks. For instance, it can be challenging to make payments during power outages or internet failures. Additionally, some groups may find it difficult to use digital money. To address these concerns, we propose a design for a central bank digital currency (CBDC) similar to physical cash but also integrates with digital payment systems. This would enable users to access digital money without needing a third party. Our design also addresses technical and security concerns by implementing a trust-level model and ensuring that the system meets users' security needs. Ultimately, our design has the potential to replace physical banknotes and coins.
LGD-GCN: Local and Global Disentangled Graph Convolutional Networks
Venue: arXiv cs.LG 2023
Year: 2023

Disentangled Graph Convolutional Network (DisenGCN) is an encouraging framework to disentangle the latent factors arising in a real-world graph. However, it relies on disentangling information heavily from a local range (i.e., a node and its 1-hop neighbors), while the local information in many cases can be uneven and incomplete, hindering the interpretabiliy power and model performance of DisenGCN. In this paper\footnote{This paper is a lighter version of \href{https://jingweio.github.io/assets/pdf/tnnls22.pdf}{"Learning Disentangled Graph Convolutional Networks Locally and Globally"} where the results and analysis have been reworked substantially. Digital Object Identifier \url{https://doi.org/10.1109/TNNLS.2022.3195336}.}, we introduce a novel Local and Global Disentangled Graph Convolutional Network (LGD-GCN) to capture both local and global information for graph disentanglement. LGD-GCN performs a statistical mixture modeling to derive a factor-aware latent continuous space, and then constructs different structures w.r.t. different factors from the revealed space. In this way, the global factor-specific information can be efficiently and selectively encoded via a message passing along these built structures, strengthening the intra-factor consistency. We also propose a novel diversity promoting regularizer employed with the latent space modeling, to encourage inter-factor diversity. Evaluations of the proposed LGD-GCN on the synthetic and real-world datasets show a better interpretability and improved performance in node classification over the existing competitive models. Code is available at \url{https://github.com/jingweio/LGD-GCN}.
Move Schedules: Fast persistence computations in coarse dynamic settings
Venue: arXiv cs.CG 2023
Year: 2023

Matrix reduction is the standard procedure for computing the persistent homology of a filtered simplicial complex with $m$ simplices. Its output is a particular decomposition of the total boundary matrix, from which the persistence diagrams and generating cycles are derived. Persistence diagrams are known to vary continuously with respect to their input, motivating the study of their computation for time-varying filtered complexes. Computing persistence dynamically can be reduced to maintaining a valid decomposition under adjacent transpositions in the filtration order. Since there are $O(m^2)$ such transpositions, this maintenance procedure exhibits limited scalability and is often too fine for many applications. We propose a coarser strategy for maintaining the decomposition over a 1-parameter family of filtrations. By reduction to a particular longest common subsequence problem, we show that the minimal number of decomposition updates $d$ can be found in $O(m \log \log m)$ time and $O(m)$ space, and that the corresponding sequence of permutations -- which we call a schedule -- can be constructed in $O(d m \log m)$ time. We also show that, in expectation, the storage needed to employ this strategy is actually sublinear in $m$. Exploiting this connection, we show experimentally that the decrease in operations to compute diagrams across a family of filtrations is proportional to the difference between the expected quadratic number of states and the proposed sublinear coarsening. Applications to video data, dynamic metric space data, and multiparameter persistence are also presented.
Resynchronized Uniformization and Definability Problems for Rational Relations
Venue: arXiv cs.FL 2023
Year: 2023

Regular synchronization languages can be used to define rational relations of finite words, and to characterize subclasses of rational relations, like automatic or recognizable relations. We provide a systematic study of the decidability of uniformization and definability problems for subclasses of rational relations defined in terms of such synchronization languages. We rephrase known results in this setting and complete the picture by adding several new decidability and undecidability results.
Algorithmic Solution for Systems of Linear Equations, in $\mathcal{O}(mn)$ time
Venue: arXiv cs.LG 2023
Year: 2023

We present a novel algorithm attaining excessively fast, the sought solution of linear systems of equations. The algorithm is short in its basic formulation and, by definition, vectorized, while the memory allocation demands are trivial, because, for each iteration, only one dimension of the given input matrix $\mathbf X$ is utilized. The execution time is very short compared with state-of-the-art methods, exhibiting $> \times 10^2$ speed-up and low memory allocation demands, especially for non-square Systems of Linear Equations, with ratio of equations versus features high (tall systems), or low (wide systems) accordingly. The accuracy is high and straightforwardly controlled, and the numerical results highlight the efficiency of the proposed algorithm, in terms of computation time, solution accuracy and memory demands. The paper also comprises a theoretical proof for the algorithmic convergence, and we extend the implementation of the proposed algorithmic rationale to feature selection tasks.