OpenRaiser/Intern-Atlas huggingface dataset:
POSTER: A Pyramid Cross-Fusion Transformer Network for Facial Expression Recognition
Venue: arXiv cs.CV 2023
Year: 2023

Facial expression recognition (FER) is an important task in computer vision, having practical applications in areas such as human-computer interaction, education, healthcare, and online monitoring. In this challenging FER task, there are three key issues especially prevalent: inter-class similarity, intra-class discrepancy, and scale sensitivity. While existing works typically address some of these issues, none have fully addressed all three challenges in a unified framework. In this paper, we propose a two-stream Pyramid crOss-fuSion TransformER network (POSTER), that aims to holistically solve all three issues. Specifically, we design a transformer-based cross-fusion method that enables effective collaboration of facial landmark features and image features to maximize proper attention to salient facial regions. Furthermore, POSTER employs a pyramid structure to promote scale invariance. Extensive experimental results demonstrate that our POSTER achieves new state-of-the-art results on RAF-DB (92.05%), FERPlus (91.62%), as well as AffectNet 7 class (67.31%) and 8 class (63.34%). The code is available at https://github.com/zczcwh/POSTER.
Stable Matching: Choosing Which Proposals to Make
Venue: arXiv cs.GT 2023
Year: 2023

To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: $\bullet$ Why does it work well? $\bullet$ Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee [17], with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee's result, showing that in large markets, with high probability, for $\it all$ but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for $\it all$ but the agents with the lowest public ratings, each agent has an easily identified length $O(\log n)$ preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to many-to-one settings, e.g. employers and workers, and we also show the existence of an $ε$-Bayes-Nash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.
List covering of regular multigraphs with semi-edges
Venue: arXiv cs.DM 2023
Year: 2023

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-edges}. A graph is called {\em simple} if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph $H$ of valency greater than 2, deciding if an input graph covers $H$ is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called \textsc{List-$H$-Cover}, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the \textsc{List-$H$-Cover} problem is NP-complete for every regular graph $H$ of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of \textsc{ List-$H$-Cover} for cubic graphs.
Robust Fingerprint of Location Trajectories Under Differential Privacy
Venue: arXiv cs.CR 2023
Year: 2023

Directly releasing those data raises privacy and liability (e.g., due to unauthorized distribution of such datasets) concerns since location data contain users' sensitive information, e.g., regular moving patterns and favorite spots. To address this, we propose a novel fingerprinting scheme that simultaneously identifies unauthorized redistribution of location datasets and provides differential privacy guarantees for the shared data. Observing data utility degradation due to differentially-private mechanisms, we introduce a utility-focused post-processing scheme to regain spatio-temporal correlations between points in a location trajectory. We further integrate this post-processing scheme into our fingerprinting scheme as a sampling method. The proposed fingerprinting scheme alleviates the degradation in the utility of the shared dataset due to the noise introduced by differentially-private mechanisms (i.e., adds the fingerprint by preserving the publicly known statistics of the data). Meanwhile, it does not violate differential privacy throughout the entire process due to immunity to post-processing, a fundamental property of differential privacy. Our proposed fingerprinting scheme is robust against known and well-studied attacks against a fingerprinting scheme including random flipping attacks, correlation-based flipping attacks, and collusions among multiple parties, which makes it hard for the attackers to infer the fingerprint codes and avoid accusation. Via experiments on two real-life location datasets and two synthetic ones, we show that our scheme achieves high fingerprinting robustness and outperforms existing approaches. Besides, the proposed fingerprinting scheme increases data utility for differentially-private datasets, which is beneficial for data analyzers.
Optimized SC-F-LOAM: Optimized Fast LiDAR Odometry and Mapping Using Scan Context
Venue: arXiv cs.RO 2023
Year: 2023

LiDAR odometry can achieve accurate vehicle pose estimation for short driving range or in small-scale environments, but for long driving range or in large-scale environments, the accuracy deteriorates as a result of cumulative estimation errors. This drawback necessitates the inclusion of loop closure detection in a SLAM framework to suppress the adverse effects of cumulative errors. To improve the accuracy of pose estimation, we propose a new LiDAR-based SLAM method which uses F-LOAM as LiDAR odometry, Scan Context for loop closure detection, and GTSAM for global optimization. In our approach, an adaptive distance threshold (instead of a fixed threshold) is employed for loop closure detection, which achieves more accurate loop closure detection results. Besides, a feature-based matching method is used in our approach to compute vehicle pose transformations between loop closure point cloud pairs, instead of using the raw point cloud obtained by the LiDAR sensor, which significantly reduces the computation time. The KITTI dataset is used for verifications of our method, and the experimental results demonstrate that the proposed method outperforms typical LiDAR odometry/SLAM methods in the literature. Our code is made publicly available for the benefit of the community.
Resources for Turkish Natural Language Processing: A critical survey
Venue: arXiv cs.CL 2023
Year: 2023

This paper presents a comprehensive survey of corpora and lexical resources available for Turkish. We review a broad range of resources, focusing on the ones that are publicly available. In addition to providing information about the available linguistic resources, we present a set of recommendations, and identify gaps in the data available for conducting research and building applications in Turkish Linguistics and Natural Language Processing.
Speech Sequence Embeddings using Nearest Neighbors Contrastive Learning
Venue: arXiv cs.AI 2023
Year: 2023

We introduce a simple neural encoder architecture that can be trained using an unsupervised contrastive learning objective which gets its positive samples from data-augmented k-Nearest Neighbors search. We show that when built on top of recent self-supervised audio representations, this method can be applied iteratively and yield competitive SSE as evaluated on two tasks: query-by-example of random sequences of speech, and spoken term discovery. On both tasks our method pushes the state-of-the-art by a significant margin across 5 different languages. Finally, we establish a benchmark on a query-by-example task on the LibriSpeech dataset to monitor future improvements in the field.
Domain Adversarial Graph Convolutional Network Based on RSSI and Crowdsensing for Indoor Localization
Venue: arXiv cs.NI 2023
Year: 2023

In recent years, the use of WiFi fingerprints for indoor positioning has grown in popularity, largely due to the widespread availability of WiFi and the proliferation of mobile communication devices. However, many existing methods for constructing fingerprint datasets rely on labor-intensive and time-consuming processes of collecting large amounts of data. Additionally, these methods often focus on ideal laboratory environments, rather than considering the practical challenges of large multi-floor buildings. To address these issues, we present a novel WiDAGCN model that can be trained using a small number of labeled site survey data and large amounts of unlabeled crowdsensed WiFi fingerprints. By constructing heterogeneous graphs based on received signal strength indicators (RSSIs) between waypoints and WiFi access points (APs), our model is able to effectively capture the topological structure of the data. We also incorporate graph convolutional networks (GCNs) to extract graph-level embeddings, a feature that has been largely overlooked in previous WiFi indoor localization studies. To deal with the challenges of large amounts of unlabeled data and multiple data domains, we employ a semi-supervised domain adversarial training scheme to effectively utilize unlabeled data and align the data distributions across domains. Our system is evaluated using a public indoor localization dataset that includes multiple buildings, and the results show that it performs competitively in terms of localization accuracy in large buildings.
A note on occur-check (extended report)
Venue: arXiv cs.LO 2023
Year: 2023

We weaken the notion of "not subject to occur-check" (NSTO), on which most known results on avoiding the occur-check in logic programming are based. NSTO means that unification is performed only on such pairs of atoms for which the occur-check never succeeds in any run of a nondeterministic unification algorithm. Here we show that "any run" can be weakened to "some run". We present some related sufficient conditions under which the occur-check may be safely omitted. We show examples for which the proposed approach provides more general results than the approaches based on well-moded and nicely moded programs (this includes cases to which the latter approaches are inapplicable). We additionally present a sufficient condition based on NSTO, working for arbitrary selection rules.
Financial technologies (FinTech) for mental health: The potential of objective financial data to better understand the relationships between financial behavior and mental health
Venue: arXiv cs.HC 2023
Year: 2023

In this paper, we present novel research methods for collecting and analyzing personal financial data alongside mental health factors, illustrated through a N=1 case study using data from one individual with bipolar disorder. While we have not found statistically significant trends nor our findings are generalizable beyond this case, our approach provides an insight into the challenges of accessing objective financial data. We outline what data is currently available, what can be done with it, and what factors to consider when working with financial data. More specifically, using these methods researchers might be able to identify symptomatic traces of mental ill health in personal financial data such as identifying early warning signs and thereby enable preemptive care for individuals with serious mental illnesses. Based on this work, we have also explored future directions for developing interventions to support financial wellbeing. Furthermore, we have described the technical, ethical, and equity challenges for financial data-driven assessments and intervention methods, as well as provided a broad research agenda to address these challenges. By leveraging objective, personalized financial data in a privacy-preserving and ethical manner help lead to a shift in mental health care.
Proximal Policy Optimization Learning based Control of Congested Freeway Traffic
Venue: arXiv cs.AI 2023
Year: 2023

This study proposes a delay-compensated feedback controller based on proximal policy optimization (PPO) reinforcement learning to stabilize traffic flow in the congested regime by manipulating the time-gap of adaptive cruise control-equipped (ACC-equipped) vehicles.The traffic dynamics on a freeway segment are governed by an Aw-Rascle-Zhang (ARZ) model, consisting of $2\times 2$ nonlinear first-order partial differential equations (PDEs).Inspired by the backstepping delay compensator [18] but different from whose complex segmented control scheme, the PPO control is composed of three feedbacks, namely the current traffic flow velocity, the current traffic flow density and previous one step control input. The control gains for the three feedbacks are learned from the interaction between the PPO and the numerical simulator of the traffic system without knowing the system dynamics. Numerical simulation experiments are designed to compare the Lyapunov control, the backstepping control and the PPO control. The results show that for a delay-free system, the PPO control has faster convergence rate and less control effort than the Lyapunov control. For a traffic system with input delay, the performance of the PPO controller is comparable to that of the Backstepping controller, even for the situation that the delay value does not match. However, the PPO is robust to parameter perturbations, while the Backstepping controller cannot stabilize a system where one of the parameters is disturbed by Gaussian noise.
Computing $k$-Bisimulations for Large Graphs: A Comparison and Efficiency Analysis
Venue: arXiv cs.DS 2023
Year: 2023

Summarizing graphs w.r.t. structural features is important to reduce the graph's size and make tasks like indexing, querying, and visualization feasible. Our generic parallel BRS algorithm efficiently summarizes large graphs w.r.t. a custom equivalence relation $\sim$ defined on the graph's vertices $V$. Moreover, the definition of $\sim$ can be chained $k\geq 1$ times, so the defined equivalence relation becomes a $k$-bisimulation. We evaluate the runtime and memory performance of the BRS algorithm for $k$-bisimulation with $k=1,\ldots,10$ against two algorithms found in the literature (a sequential algorithm due to Kaushik et al. and a parallel algorithm of Schätzle et al.), which we implemented in the same software stack as BRS. We use five real-world and synthetic graph datasets containing 100 million to two billion edges. Our results show that the generic BRS algorithm outperforms the respective native bisimulation algorithms on all datasets for all $k\geq5$ and for smaller $k$ in some cases. The BRS implementations of the two bisimulation algorithms run almost as fast as each other. Thus, the BRS algorithm is an effective parallelization of the sequential Kaushik et al. bisimulation algorithm.
Efficient Construction of the BWT for Repetitive Text Using String Compression
Venue: arXiv cs.DS 2023
Year: 2023

We present a new semi-external algorithm that builds the Burrows--Wheeler transform variant of Bauer et al. (a.k.a., BCR BWT) in linear expected time. Our method uses compression techniques to reduce computational costs when the input is massive and repetitive. Concretely, we build on induced suffix sorting (ISS) and resort to run-length and grammar compression to maintain our intermediate results in compact form. Our compression format not only saves space but also speeds up the required computations. Our experiments show important space and computation time savings when the text is repetitive. In moderate-size collections of real human genome assemblies (14.2 GB - 75.05 GB), our memory peak is, on average, 1.7x smaller than the peak of the state-of-the-art BCR BWT construction algorithm (\texttt{ropebwt2}), while running 5x faster. Our current implementation was also able to compute the BCR BWT of 400 real human genome assemblies (1.2 TB) in 41.21 hours using 118.83 GB of working memory (around 10\% of the input size). Interestingly, the results we report in the 1.2 TB file are dominated by the difficulties of scanning huge files under memory constraints (specifically, I/O operations). This fact indicates we can perform much better with a more careful implementation of our method, thus scaling to even bigger sizes efficiently.
Stealing and Evading Malware Classifiers and Antivirus at Low False Positive Conditions
Venue: arXiv cs.CR 2023
Year: 2023

Model stealing attacks have been successfully used in many machine learning domains, but there is little understanding of how these attacks work against models that perform malware detection. Malware detection and, in general, security domains have unique conditions. In particular, there are very strong requirements for low false positive rates (FPR). Antivirus products (AVs) that use machine learning are very complex systems to steal, malware binaries continually change, and the whole environment is adversarial by nature. This study evaluates active learning model stealing attacks against publicly available stand-alone machine learning malware classifiers and also against antivirus products. The study proposes a new neural network architecture for surrogate models (dualFFNN) and a new model stealing attack that combines transfer and active learning for surrogate creation (FFNN-TL). We achieved good surrogates of the stand-alone classifiers with up to 99\% agreement with the target models, using less than 4% of the original training dataset. Good surrogates of AV systems were also trained with up to 99% agreement and less than 4,000 queries. The study uses the best surrogates to generate adversarial malware to evade the target models, both stand-alone and AVs (with and without an internet connection). Results show that surrogate models can generate adversarial malware that evades the targets but with a lower success rate than directly using the target models to generate adversarial malware. Using surrogates, however, is still a good option since using the AVs for malware generation is highly time-consuming and easily detected when the AVs are connected to the internet.
Assessing cloudiness in nonwovens
Venue: arXiv cs.CV 2023
Year: 2023

The homogeneity of filter media is important for material selection and quality control, along with the specific weight (nominal grammage) and the distribution of the local weight. Cloudiness or formation is a concept used to describe deviations from homogeneity in filter media. We suggest to derive the cloudiness index from the power spectrum of the relative local areal weight, integrated over a selected frequency range. The power spectrum captures the energy density in a broad spectral range. Moreover, under certain conditions, the structure of a nonwoven is fully characterized by the areal weight, the variance of the local areal weight, and the power spectrum. Consequently, the power spectrum is the parameter that exclusively reflects the cloudiness. Here, we address questions arising from practical application. The most prominent is the choice of the spectral band. It certainly depends on the characteristic "size of the clouds", but is limited by the size and lateral resolution of the images. We show that the cloudiness index based on the power spectrum of the relative local areal weight is theoretically well founded and can be robustly measured from image data. Choosing the spectral band allows to capture the cloudiness either visually perceived or found to be decisive for product properties. It is thus well suited to build a technical standard on it.
Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata
Venue: arXiv cs.DS 2023
Year: 2023

Given a matrix $A$ and vector $b$ with polynomial entries in $d$ real variables $δ=(δ_1,\ldots,δ_d)$ we consider the following notion of feasibility: the pair $(A,b)$ is locally feasible if there exists an open neighborhood $U$ of $0$ such that for every $δ\in U$ there exists $x$ satisfying $A(δ)x\ge b(δ)$ entry-wise. For $d=1$ we construct a polynomial time algorithm for deciding local feasibility. For $d \ge 2$ we show local feasibility is NP-hard. This also gives the first polynomial-time algorithm for the asymptotic linear program problem introduced by Jeroslow in 1973. As an application (which was the primary motivation for this work) we give a computer-assisted proof of ergodicity of the following elementary 1D cellular automaton: given the current state $η_t \in \{0,1\}^{\mathbb{Z}}$ the next state $η_{t+1}(n)$ at each vertex $n\in \mathbb{Z}$ is obtained by $η_{t+1}(n)= \text{NAND}\big(\text{BSC}_δ(η_t(n-1)), \text{BSC}_δ(η_t(n))\big)$. Here the binary symmetric channel $\text{BSC}_δ$ takes a bit as input and flips it with probability $δ$ (and leaves it unchanged with probability $1-δ$). It is shown that there exists $δ_0>0$ such that for all $0<δ<δ_0$ the distribution of $η_t$ converges to a unique stationary measure irrespective of the initial condition $η_0$. We also consider the problem of broadcasting information on the 2D-grid of noisy binary-symmetric channels $\text{BSC}_δ$, where each node may apply an arbitrary processing function to its input bits. We prove that there exists $δ_0'>0$ such that for all noise levels $0<δ<δ_0'$ it is impossible to broadcast information for any processing function, as conjectured by Makur, Mossel and Polyanskiy.