OpenRaiser/Intern-Atlas huggingface dataset:
The FOLE Table
Venue: arXiv cs.LO 2023
Year: 2023

This paper continues the discussion of the representation of ontologies in the first-order logical environment FOLE. According to Gruber, an ontology defines the primitives with which to model the knowledge resources for a community of discourse. These primitives, consisting of classes, relationships and properties, are represented by the entity-relationship-attribute ERA data model of Chen. An ontology uses formal axioms to constrain the interpretation of these primitives. In short, an ontology specifies a logical theory. A series of three papers by the author provide a rigorous mathematical representation for the ERA data model in particular, and ontologies in general, within FOLE. The first two papers, which provide a foundation and superstructure for FOLE, represent the formalism and semantics of (many-sorted) first-order logic in a classification form corresponding to ideas discussed in the Information Flow Framework (IFF). The third paper will define an interpretation of FOLE in terms of the transformational passage, first described in (Kent, 2013), from the classification form of first-order logic to an equivalent interpretation form, thereby defining the formalism and semantics of first-order logical/relational database systems. Two papers will provide a precise mathematical basis for FOLE interpretation: the current paper develops the notion of a FOLE relational table following the relational model of Codd, and a follow-up paper will develop the notion of a FOLE relational database. Both of these papers expand on material found in the paper (Kent, 2011). Although the classification form follows the entity-relationship-attribute data model of Chen, the interpretation form follows the relational data model of Codd. In general, the FOLE representation uses a conceptual structures approach, that is completely compatible with formal concept analysis and information flow.
Decentralized Exploration in Multi-Armed Bandits -- Extended version
Venue: arXiv cs.LG 2023
Year: 2023

We consider the decentralized exploration problem: a set of players collaborate to identify the best arm by asynchronously interacting with the same stochastic environment. The objective is to insure privacy in the best arm identification problem between asynchronous, collaborative, and thrifty players. In the context of a digital service, we advocate that this decentralized approach allows a good balance between the interests of users and those of service providers: the providers optimize their services, while protecting the privacy of the users and saving resources. We define the privacy level as the amount of information an adversary could infer by intercepting the messages concerning a single user. We provide a generic algorithm Decentralized Elimination, which uses any best arm identification algorithm as a subroutine. We prove that this algorithm insures privacy, with a low communication cost, and that in comparison to the lower bound of the best arm identification problem, its sample complexity suffers from a penalty depending on the inverse of the probability of the most frequent players. Then, thanks to the genericity of the approach, we extend the proposed algorithm to the non-stationary bandits. Finally, experiments illustrate and complete the analysis.
Cluster Editing with Vertex Splitting
Venue: arXiv cs.CC 2023
Year: 2023

Cluster Editing, also known as Correlation Clustering, is a well-studied graph modification problem. In this problem, one is given a graph and the task is to perform up to $k$ edge additions or deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Other strong motivations come from biological network analysis and from language networks. Trying to cluster words with similar usage in the latter can be confounded by homonyms, that is, words with multiple meanings like "bat." In this paper, we introduce a new variant of Cluster Editing whereby a vertex can be split into two or more vertices. First used in the context of graph drawing, this operation allows a vertex $v$ to be replaced by two vertices whose combined neighborhood is the neighborhood of $v$ (and thus $v$ can belong to more than one cluster). We call the new problem Cluster Editing with Vertex Splitting and we initiate the study of it. We show that it is NP-complete and fixed-parameter tractable when parameterized by the total number $k$ of allowed vertex-splitting and edge-editing operations. In particular, we obtain an $O(2^{9k log k} + n + m)$-time algorithm and a $6k$-vertex kernel.
Pedestrian Attribute Recognition: A Survey
Venue: arXiv cs.CV 2023
Year: 2023

Recognizing pedestrian attributes is an important task in the computer vision community due to it plays an important role in video surveillance. Many algorithms have been proposed to handle this task. The goal of this paper is to review existing works using traditional methods or based on deep learning networks. Firstly, we introduce the background of pedestrian attribute recognition (PAR, for short), including the fundamental concepts of pedestrian attributes and corresponding challenges. Secondly, we introduce existing benchmarks, including popular datasets and evaluation criteria. Thirdly, we analyze the concept of multi-task learning and multi-label learning and also explain the relations between these two learning algorithms and pedestrian attribute recognition. We also review some popular network architectures which have been widely applied in the deep learning community. Fourthly, we analyze popular solutions for this task, such as attributes group, part-based, etc. Fifthly, we show some applications that take pedestrian attributes into consideration and achieve better performance. Finally, we summarize this paper and give several possible research directions for pedestrian attribute recognition. We continuously update the following GitHub to keep tracking the most cutting-edge related works on pedestrian attribute recognition~\url{https://github.com/wangxiao5791509/Pedestrian-Attribute-Recognition-Paper-List}
Word Embeddings: A Survey
Venue: arXiv cs.CL 2023
Year: 2023

This work lists and describes the main recent strategies for building fixed-length, dense and distributed representations for words, based on the distributional hypothesis. These representations are now commonly called word embeddings and, in addition to encoding surprisingly good syntactic and semantic information, have been proven useful as extra features in many downstream NLP tasks.
Certified Reinforcement Learning with Logic Guidance
Venue: arXiv cs.LG 2023
Year: 2023

Reinforcement Learning (RL) is a widely employed machine learning architecture that has been applied to a variety of control problems. However, applications in safety-critical domains require a systematic and formal approach to specifying requirements as tasks or goals. We propose a model-free RL algorithm that enables the use of Linear Temporal Logic (LTL) to formulate a goal for unknown continuous-state/action Markov Decision Processes (MDPs). The given LTL property is translated into a Limit-Deterministic Generalised Buchi Automaton (LDGBA), which is then used to shape a synchronous reward function on-the-fly. Under certain assumptions, the algorithm is guaranteed to synthesise a control policy whose traces satisfy the LTL specification with maximal probability.
A new Potential-Based Reward Shaping for Reinforcement Learning Agent
Venue: arXiv cs.AI 2023
Year: 2023

Potential-based reward shaping (PBRS) is a particular category of machine learning methods which aims to improve the learning speed of a reinforcement learning agent by extracting and utilizing extra knowledge while performing a task. There are two steps in the process of transfer learning: extracting knowledge from previously learned tasks and transferring that knowledge to use it in a target task. The latter step is well discussed in the literature with various methods being proposed for it, while the former has been explored less. With this in mind, the type of knowledge that is transmitted is very important and can lead to considerable improvement. Among the literature of both the transfer learning and the potential-based reward shaping, a subject that has never been addressed is the knowledge gathered during the learning process itself. In this paper, we presented a novel potential-based reward shaping method that attempted to extract knowledge from the learning process. The proposed method extracts knowledge from episodes' cumulative rewards. The proposed method has been evaluated in the Arcade learning environment and the results indicate an improvement in the learning process in both the single-task and the multi-task reinforcement learner agents.
Advanced Capsule Networks via Context Awareness
Venue: arXiv cs.LG 2023
Year: 2023

Capsule Networks (CN) offer new architectures for Deep Learning (DL) community. Though its effectiveness has been demonstrated in MNIST and smallNORB datasets, the networks still face challenges in other datasets for images with distinct contexts. In this research, we improve the design of CN (Vector version) namely we expand more Pooling layers to filter image backgrounds and increase Reconstruction layers to make better image restoration. Additionally, we perform experiments to compare accuracy and speed of CN versus DL models. In DL models, we utilize Inception V3 and DenseNet V201 for powerful computers besides NASNet, MobileNet V1 and MobileNet V2 for small and embedded devices. We evaluate our models on a fingerspelling alphabet dataset from American Sign Language (ASL). The results show that CNs perform comparably to DL models while dramatically reducing training time. We also make a demonstration and give a link for the purpose of illustration.
Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
Venue: arXiv cs.SI 2023
Year: 2023

Multiplex networks have become increasingly more prevalent in many fields, and have emerged as a powerful tool for modeling the complexity of real networks. There is a critical need for developing inference models for multiplex networks that can take into account potential dependencies across different layers, particularly when the aim is community detection. We add to a limited literature by proposing a novel and efficient Bayesian model for community detection in multiplex networks. A key feature of our approach is the ability to model varying communities at different network layers. In contrast, many existing models assume the same communities for all layers. Moreover, our model automatically picks up the necessary number of communities at each layer (as validated by real data examples). This is appealing, since deciding the number of communities is a challenging aspect of community detection, and especially so in the multiplex setting, if one allows the communities to change across layers. Borrowing ideas from hierarchical Bayesian modeling, we use a hierarchical Dirichlet prior to model community labels across layers, allowing dependency in their structure. Given the community labels, a stochastic block model (SBM) is assumed for each layer. We develop an efficient slice sampler for sampling the posterior distribution of the community labels as well as the link probabilities between communities. In doing so, we address some unique challenges posed by coupling the complex likelihood of SBM with the hierarchical nature of the prior on the labels. An extensive empirical validation is performed on simulated and real data, demonstrating the superior performance of the model over single-layer alternatives, as well as the ability to uncover interesting structures in real networks.
Approximation Algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions
Venue: arXiv cs.DS 2023
Year: 2023

Two-stage stochastic optimization is a framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A criticism of this model is that the underlying probability distribution is itself often imprecise! To address this, a versatile approach that has been proposed is the {\em distributionally robust 2-stage model}: given a collection of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in this collection. We provide a framework for designing approximation algorithms in such settings when the collection is a ball around a central distribution and the central distribution is accessed {\em only via a sampling black box}. We first show that one can utilize the {\em sample average approximation} (SAA) method to reduce the problem to the case where the central distribution has {\em polynomial-size} support. We then show how to approximately solve a fractional relaxation of the SAA (i.e., polynomial-scenario central-distribution) problem. By complementing this via LP-rounding algorithms that provide {\em local} (i.e., per-scenario) approximation guarantees, we obtain the {\em first} approximation algorithms for the distributionally robust versions of a variety of discrete-optimization problems including set cover, vertex cover, edge cover, facility location, and Steiner tree, with guarantees that are, except for set cover, within $O(1)$-factors of the guarantees known for the deterministic version of the problem.
A formulation of the relaxation phenomenon for lane changing dynamics in an arbitrary car following model
Venue: arXiv cs.SY 2023
Year: 2023

Lane changing dynamics are an important part of traffic microsimulation and are vital for modeling weaving sections and merge bottlenecks. However, there is often much more emphasis placed on car following and gap acceptance models, whereas lane changing dynamics such as tactical, cooperation, and relaxation models receive comparatively little attention. This paper develops a general relaxation model which can be applied to an arbitrary parametric or nonparametric microsimulation model. The relaxation model modifies car following dynamics after a lane change, when vehicles can be far from equilibrium. Relaxation prevents car following models from reacting too strongly to the changes in space headway caused by lane changing, leading to more accurate and realistic simulated trajectories. We also show that relaxation is necessary for correctly simulating traffic breakdown with realistic values of capacity drop.
Object Detection in 20 Years: A Survey
Venue: arXiv cs.CV 2023
Year: 2023

Object detection, as of one the most fundamental and challenging problems in computer vision, has received great attention in recent years. Over the past two decades, we have seen a rapid technological evolution of object detection and its profound impact on the entire computer vision field. If we consider today's object detection technique as a revolution driven by deep learning, then back in the 1990s, we would see the ingenious thinking and long-term perspective design of early computer vision. This paper extensively reviews this fast-moving research field in the light of technical evolution, spanning over a quarter-century's time (from the 1990s to 2022). A number of topics have been covered in this paper, including the milestone detectors in history, detection datasets, metrics, fundamental building blocks of the detection system, speed-up techniques, and the recent state-of-the-art detection methods.
Uneven illumination surface defects inspection based on convolutional neural network
Venue: arXiv cs.CV 2023
Year: 2023

Surface defect inspection based on machine vision is often affected by uneven illumination. In order to improve the inspection rate of surface defects inspection under uneven illumination condition, this paper proposes a method for detecting surface image defects based on convolutional neural network, which is based on the adjustment of convolutional neural networks, training parameters, changing the structure of the network, to achieve the purpose of accurately identifying various defects. Experimental on defect inspection of copper strip and steel images shows that the convolutional neural network can automatically learn features without preprocessing the image, and correct identification of various types of image defects affected by uneven illumination, thus overcoming the drawbacks of traditional machine vision inspection methods under uneven illumination.
DDPNAS: Efficient Neural Architecture Search via Dynamic Distribution Pruning
Venue: arXiv cs.CV 2023
Year: 2023

Neural Architecture Search (NAS) has demonstrated state-of-the-art performance on various computer vision tasks. Despite the superior performance achieved, the efficiency and generality of existing methods are highly valued due to their high computational complexity and low generality. In this paper, we propose an efficient and unified NAS framework termed DDPNAS via dynamic distribution pruning, facilitating a theoretical bound on accuracy and efficiency. In particular, we first sample architectures from a joint categorical distribution. Then the search space is dynamically pruned and its distribution is updated every few epochs. With the proposed efficient network generation method, we directly obtain the optimal neural architectures on given constraints, which is practical for on-device models across diverse search spaces and constraints. The architectures searched by our method achieve remarkable top-1 accuracies, 97.56 and 77.2 on CIFAR-10 and ImageNet (mobile settings), respectively, with the fastest search process, i.e., only 1.8 GPU hours on a Tesla V100. Codes for searching and network generation are available at: https://openi.pcl.ac.cn/PCL AutoML/XNAS.
Transfer Learning for Hate Speech Detection in Social Media
Venue: arXiv cs.SI 2023
Year: 2023

Today, the internet is an integral part of our daily lives, enabling people to be more connected than ever before. However, this greater connectivity and access to information increase exposure to harmful content such as cyber-bullying and cyber-hatred. Models based on machine learning and natural language offer a way to make online platforms safer by identifying hate speech in web text autonomously. However, the main difficulty is annotating a sufficiently large number of examples to train these models. This paper uses a transfer learning technique to leverage two independent datasets jointly and builds a single representation of hate speech. We build an interpretable two-dimensional visualization tool of the constructed hate speech representation -- dubbed the Map of Hate -- in which multiple datasets can be projected and comparatively analyzed. The hateful content is annotated differently across the two datasets (racist and sexist in one dataset, hateful and offensive in another). However, the common representation successfully projects the harmless class of both datasets into the same space and can be used to uncover labeling errors (false positives). We also show that the joint representation boosts prediction performances when only a limited amount of supervision is available. These methods and insights hold the potential for safer social media and reduce the need to expose human moderators and annotators to distressing online messaging.
Copula Representations and Error Surface Projections for the Exclusive Or Problem
Venue: arXiv cs.LG 2023
Year: 2023

The exclusive or (xor) function is one of the simplest examples that illustrate why nonlinear feedforward networks are superior to linear regression for machine learning applications. We review the xor representation and approximation problems and discuss their solutions in terms of probabilistic logic and associative copula functions. After briefly reviewing the specification of feedforward networks, we compare the dynamics of learned error surfaces with different activation functions such as RELU and tanh through a set of colorful three-dimensional charts. The copula representations extend xor from Boolean to real values, thereby providing a convenient way to demonstrate the concept of cross-validation on in-sample and out-sample data sets. Our approach is pedagogical and is meant to be a machine learning prolegomenon.
Lower Bounding the AND-OR Tree via Symmetrization
Venue: arXiv cs.CC 2023
Year: 2023

We prove a simple, nearly tight lower bound on the approximate degree of the two-level $\mathsf{AND}$-$\mathsf{OR}$ tree using symmetrization arguments. Specifically, we show that $\widetilde{\mathrm{deg}}(\mathsf{AND}_m \circ \mathsf{OR}_n) = \widetildeΩ(\sqrt{mn})$. We prove this lower bound via reduction to the $\mathsf{OR}$ function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].
Labelings vs. Embeddings: On Distributed Representations of Distances
Venue: arXiv cs.DS 2023
Year: 2023

We investigate for which metric spaces the performance of distance labeling and of $\ell_\infty$-embeddings differ, and how significant can this difference be. Recall that a distance labeling is a distributed representation of distances in a metric space $(X,d)$, where each point $x\in X$ is assigned a succinct label, such that the distance between any two points $x,y \in X$ can be approximated given only their labels. A highly structured special case is an embedding into $\ell_\infty$, where each point $x\in X$ is assigned a vector $f(x)$ such that $\|f(x)-f(y)\|_\infty$ is approximately $d(x,y)$. The performance of a distance labeling or an $\ell_\infty$-embedding is measured via its distortion and its label-size/dimension. We also study the analogous question for the prioritized versions of these two measures. Here, a priority order $π=(x_1,\dots,x_n)$ of the point set $X$ is given, and higher-priority points should have shorter labels. Formally, a distance labeling has prioritized label-size $α(\cdot)$ if every $x_j$ has label size at most $α(j)$. Similarly, an embedding $f: X \to \ell_\infty$ has prioritized dimension $α(\cdot)$ if $f(x_j)$ is non-zero only in the first $α(j)$ coordinates. In addition, we compare these prioritized measures to their classical (worst-case) versions. We answer these questions in several scenarios, uncovering a surprisingly diverse range of behaviors. First, in some cases labelings and embeddings have very similar worst-case performance, but in other cases there is a huge disparity. However in the prioritized setting, we most often find a strict separation between the performance of labelings and embeddings. And finally, when comparing the classical and prioritized settings, we find that the worst-case bound for label size often "translates" to a prioritized one, but also find a surprising exception to this rule.