OpenRaiser/Intern-Atlas huggingface dataset:
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Venue: arXiv cs.CC 2023
Year: 2023

We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by natural size parameters using simultaneously polynomial time and sub-linear space. We are particularly focused on $\mathrm{2SAT}_3$ -- a restricted variant of the 2CNF Boolean (propositional) formula satisfiability problem in which each variable of a given 2CNF formula appears at most 3 times in the form of literals -- parameterized by the total number $m_{vbl}(ϕ)$ of variables of each given Boolean formula $ϕ$. We propose a new, practical working hypothesis, called the linear space hypothesis (LSH), which asserts that $(\mathrm{2SAT}_3,m_{vbl})$ cannot be solved in polynomial time using only ``sub-linear'' space (i.e., $m_{vbl}(x)^{\varepsilon}\, polylog(|x|)$ space for a constant $\varepsilon\in[0,1)$) on all instances $x$. Immediate consequences of LSH include $\mathrm{L}l\neq\mathrm{NL}$, $\mathrm{LOGDCFL}\neq\mathrm{LOGCFL}$, and $\mathrm{SC}\neq \mathrm{NSC}$. For our investigation, we fully utilize a key notion of ``short reductions'', under which the class $\mathrm{PsubLIN}$ of all parameterized polynomial-time sub-linear-space solvable problems is indeed closed.
Personalized Recommender System for Children's Book Recommendation with A Realtime Interactive Robot
Venue: arXiv cs.IR 2023
Year: 2023

In this paper we study the personalized book recommender system in a child-robot interactive environment. Firstly, we propose a novel text search algorithm using an inverse filtering mechanism that improves the efficiency. Secondly, we propose a user interest prediction method based on the Bayesian network and a novel feedback mechanism. According to children's fuzzy language input, the proposed method gives the predicted interests. Thirdly, the domain specific synonym association is proposed based on word vectorization, in order to improve the understanding of user intention. Experimental results show that the proposed recommender system has an improved performance and it can operate on embedded consumer devices with limited computational resources.
MSC: A Dataset for Macro-Management in StarCraft II
Venue: arXiv cs.AI 2023
Year: 2023

Macro-management is an important problem in StarCraft, which has been studied for a long time. Various datasets together with assorted methods have been proposed in the last few years. But these datasets have some defects for boosting the academic and industrial research: 1) There're neither standard preprocessing, parsing and feature extraction procedures nor predefined training, validation and test set in some datasets. 2) Some datasets are only specified for certain tasks in macro-management. 3) Some datasets are either too small or don't have enough labeled data for modern machine learning algorithms such as deep neural networks. So most previous methods are trained with various features, evaluated on different test sets from the same or different datasets, making it difficult to be compared directly. To boost the research of macro-management in StarCraft, we release a new dataset MSC based on the platform SC2LE. MSC consists of well-designed feature vectors, pre-defined high-level actions and final result of each match. We also split MSC into training, validation and test set for the convenience of evaluation and comparison. Besides the dataset, we propose a baseline model and present initial baseline results for global state evaluation and build order prediction, which are two of the key tasks in macro-management. Various downstream tasks and analyses of the dataset are also described for the sake of research on macro-management in StarCraft II. Homepage: https://github.com/wuhuikai/MSC.
NELS -- Never-Ending Learner of Sounds
Venue: arXiv cs.SD 2023
Year: 2023

Sounds are essential to how humans perceive and interact with the world and are captured in recordings and shared on the Internet on a minute-by-minute basis. These recordings, which are predominantly videos, constitute the largest archive of sounds we know. However, most of these recordings have undescribed content making necessary methods for automatic sound analysis, indexing and retrieval. These methods have to address multiple challenges, such as the relation between sounds and language, numerous and diverse sound classes, and large-scale evaluation. We propose a system that continuously learns from the web relations between sounds and language, improves sound recognition models over time and evaluates its learning competency in the large-scale without references. We introduce the Never-Ending Learner of Sounds (NELS), a project for continuously learning of sounds and their associated knowledge, available on line in nels.cs.cmu.edu
Leveraging Statistical Multi-Agent Online Planning with Emergent Value Function Approximation
Venue: arXiv cs.MA 2023
Year: 2023

Making decisions is a great challenge in distributed autonomous environments due to enormous state spaces and uncertainty. Many online planning algorithms rely on statistical sampling to avoid searching the whole state space, while still being able to make acceptable decisions. However, planning often has to be performed under strict computational constraints making online planning in multi-agent systems highly limited, which could lead to poor system performance, especially in stochastic domains. In this paper, we propose Emergent Value function Approximation for Distributed Environments (EVADE), an approach to integrate global experience into multi-agent online planning in stochastic domains to consider global effects during local planning. For this purpose, a value function is approximated online based on the emergent system behaviour by using methods of reinforcement learning. We empirically evaluated EVADE with two statistical multi-agent online planning algorithms in a highly complex and stochastic smart factory environment, where multiple agents need to process various items at a shared set of machines. Our experiments show that EVADE can effectively improve the performance of multi-agent online planning while offering efficiency w.r.t. the breadth and depth of the planning process.
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
Venue: arXiv cs.DS 2023
Year: 2023

We study the distinct elements and $\ell_p$-heavy hitters problems in the sliding window model, where only the most recent $n$ elements in the data stream form the underlying set. We first introduce the composable histogram, a simple twist on the exponential (Datar et al., SODA 2002) and smooth histograms (Braverman and Ostrovsky, FOCS 2007) that may be of independent interest. We then show that the composable histogram along with a careful combination of existing techniques to track either the identity or frequency of a few specific items suffices to obtain algorithms for both distinct elements and $\ell_p$-heavy hitters that are nearly optimal in both $n$ and $ε$. Applying our new composable histogram framework, we provide an algorithm that outputs a $(1+ε)$-approximation to the number of distinct elements in the sliding window model and uses $\mathcal{O}\left(\frac{1}{ε^2}\log n\log\frac{1}ε\log\log n+\frac{1}ε\log^2 n\right)$ bits of space. For $\ell_p$-heavy hitters, we provide an algorithm using space $\mathcal{O}\left(\frac{1}{ε^p}\log^3 n\left(\log\log n+\log\frac{1}ε\right)\right)$ for $0<p\le 2$, improving upon the best-known algorithm for $\ell_2$-heavy hitters (Braverman et al., COCOON 2014), which has space complexity $\mathcal{O}\left(\frac{1}{ε^4}\log^3 n\right)$. We also show lower bounds of $Ω\left(\frac{1}ε\log^2 n+\frac{1}{ε^2}\log n\right)$ for distinct elements and $Ω\left(\frac{1}{ε^p}\log^2 n\right)$ for $\ell_p$-heavy hitters.
TI-CNN: Convolutional Neural Networks for Fake News Detection
Venue: arXiv cs.CL 2023
Year: 2023

With the development of social networks, fake news for various commercial and political purposes has been appearing in large numbers and gotten widespread in the online world. With deceptive words, people can get infected by the fake news very easily and will share them without any fact-checking. For instance, during the 2016 US president election, various kinds of fake news about the candidates widely spread through both official news media and the online social networks. These fake news is usually released to either smear the opponents or support the candidate on their side. The erroneous information in the fake news is usually written to motivate the voters' irrational emotion and enthusiasm. Such kinds of fake news sometimes can bring about devastating effects, and an important goal in improving the credibility of online social networks is to identify the fake news timely. In this paper, we propose to study the fake news detection problem. Automatic fake news identification is extremely hard, since pure model based fact-checking for news is still an open problem, and few existing models can be applied to solve the problem. With a thorough investigation of a fake news data, lots of useful explicit features are identified from both the text words and images used in the fake news. Besides the explicit features, there also exist some hidden patterns in the words and images used in fake news, which can be captured with a set of latent features extracted via the multiple convolutional layers in our model. A model named as TI-CNN (Text and Image information based Convolutinal Neural Network) is proposed in this paper. By projecting the explicit and latent features into a unified feature space, TI-CNN is trained with both the text and image information simultaneously. Extensive experiments carried on the real-world fake news datasets have demonstrate the effectiveness of TI-CNN.
Using Nonlinear Normal Modes for Execution of Efficient Cyclic Motions in Articulated Soft Robots
Venue: arXiv cs.RO 2023
Year: 2023

Inspired by the vertebrate branch of the animal kingdom, articulated soft robots are robotic systems embedding elastic elements into a classic rigid (skeleton-like) structure. Leveraging on their bodies elasticity, soft robots promise to push their limits far beyond the barriers that affect their rigid counterparts. However, existing control strategies aiming at achieving this goal are either tailored on specific examples, or rely on model cancellations -- thus defeating the purpose of introducing elasticity in the first place. In a series of recent works, we proposed to implement efficient oscillatory motions in robots subject to a potential field, aimed at solving these issues. A main component of this theory are Eigenmanifolds, that we defined as nonlinear continuations of the classic linear eigenspaces. When the soft robot is initialized on one of these manifolds, it evolves autonomously while presenting regular -- and thus practically useful -- evolutions, called normal modes. In addition to that, we proposed a control strategy making modal manifolds attractors for the system, and acting on the total energy of the soft robot to move from a modal evolution to the other. In this way, a large class of autonomous behaviors can be excited, which are direct expression of the embodied intelligence of the soft robot. Despite the fact that the idea behind our work comes from physical intuition and preliminary experimental validations, the formulation that we have provided so far is however rather theoretical, and very much in need of an experimental validation. The aim of this paper is to provide such an experimental validation using as testbed the articulated soft leg. We will introduce a simplified control strategy, and we will test its effectiveness on this system, to implement swing-like oscillations. We plan to extend this validation with a soft quadruped.
A concrete model for a typed linear algebraic lambda calculus
Venue: arXiv cs.LO 2023
Year: 2023

We give an adequate, concrete, categorical-based model for Lambda-S, which is a typed version of a linear-algebraic lambda calculus, extended with measurements. Lambda-S is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi: to forbid duplication of variables, and to consider all lambda-terms as algebraic linear functions. The type system of Lambda-S have a superposition constructor S such that a type A is considered as the base of a vector space while SA is its span. Our model considers S as the composition of two functors in an adjunction relation between the category of sets and the category of vector spaces over C. The right adjoint is a forgetful functor U, which is hidden in the language, and plays a central role in the computational reasoning.
Almost optimal query algorithm for hitting set using a subset query
Venue: arXiv cs.DS 2023
Year: 2023

Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter $k$, the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized $d$-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Formally, GPIS is defined as follows: GPIS oracle for a $d$-uniform hypergraph $\mathcal{H}$ takes as input $d$ pairwise disjoint non-empty subsets $A_1, \ldots, A_d$ of vertices in $\cal H$ and answers whether there is a hyperedge in $\mathcal{H}$ that intersects each set $A_i$, where $i \in \{1, \, 2, \, \ldots, d\}$. } For $d=2$, the GPIS oracle is nothing but BIS oracle. We show that $d$-Hitting-Set, the hitting set problem for $d$-uniform hypergraphs, can be solved using $\widetilde{\mathcal{O}}_d(k^{d} \log n)$ GPIS queries. Additionally, we also showed that $d$-Decesion-Hitting-Set, the decision version of $d$-Hitting-Set can be solved with $\widetilde{\mathcal{O}}_d\left( \min \left\{ k^d\log n, k^{2d^2} \right\} \right)$ {\sc GPIS} queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves $d$-Decesion-Hitting-Set requires $Ω\left( \binom{k+d}{d} \right)$ GPIS queries.
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
Venue: arXiv cs.DS 2023
Year: 2023

Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation. This algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.
Capacity of Locally Recoverable Codes
Venue: arXiv cs.IT 2023
Year: 2023

Motivated by applications in distributed storage, the notion of a locally recoverable code (LRC) was introduced a few years back. In an LRC, any coordinate of a codeword is recoverable by accessing only a small number of other coordinates. While different properties of LRCs have been well-studied, their performance on channels with random erasures or errors has been mostly unexplored. In this paper, we analyze the performance of LRCs over such stochastic channels. In particular, for input-symmetric discrete memoryless channels, we give a tight characterization of the gap to Shannon capacity when LRCs are used over the channel. Our results hold for a general notion of LRCs that correct multiple local erasures.
Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
Venue: arXiv cs.LG 2023
Year: 2023

While machine learning has achieved remarkable results in a wide variety of domains, the training of models often requires large datasets that may need to be collected from different individuals. As sensitive information may be contained in the individual's dataset, sharing training data may lead to severe privacy concerns. Therefore, there is a compelling need to develop privacy-aware machine learning methods, for which one effective approach is to leverage the generic framework of differential privacy. Considering that stochastic gradient descent (SGD) is one of the most commonly adopted methods for large-scale machine learning problems, a decentralized differentially private SGD algorithm is proposed in this work. Particularly, we focus on SGD without replacement due to its favorable structure for practical implementation. Both privacy and convergence analysis are provided for the proposed algorithm. Finally, extensive experiments are performed to demonstrate the effectiveness of the proposed method.
BlockTag: Design and applications of a tagging system for blockchain analysis
Venue: arXiv cs.CR 2023
Year: 2023

Annotating blockchains with auxiliary data is useful for many applications. For example, e-crime investigations of illegal Tor hidden services, such as Silk Road, often involve linking Bitcoin addresses, from which money is sent or received, to user accounts and related online activities. We present BlockTag, an open-source tagging system for blockchains that facilitates such tasks. We describe BlockTag's design and present three analyses that illustrate its capabilities in the context of privacy research and law enforcement.
Controllable Neural Story Plot Generation via Reward Shaping
Venue: arXiv cs.CL 2023
Year: 2023

Language-modeling--based approaches to story plot generation attempt to construct a plot by sampling from a language model (LM) to predict the next character, word, or sentence to add to the story. LM techniques lack the ability to receive guidance from the user to achieve a specific goal, resulting in stories that don't have a clear sense of progression and lack coherence. We present a reward-shaping technique that analyzes a story corpus and produces intermediate rewards that are backpropagated into a pre-trained LM in order to guide the model towards a given goal. Automated evaluations show our technique can create a model that generates story plots which consistently achieve a specified goal. Human-subject studies show that the generated stories have more plausible event ordering than baseline plot generation techniques.
Convolutional Neural Networks for Epileptic Seizure Prediction
Venue: arXiv cs.LG 2023
Year: 2023

Epilepsy is the most common neurological disorder and an accurate forecast of seizures would help to overcome the patient's uncertainty and helplessness. In this contribution, we present and discuss a novel methodology for the classification of intracranial electroencephalography (iEEG) for seizure prediction. Contrary to previous approaches, we categorically refrain from an extraction of hand-crafted features and use a convolutional neural network (CNN) topology instead for both the determination of suitable signal characteristics and the binary classification of preictal and interictal segments. Three different models have been evaluated on public datasets with long-term recordings from four dogs and three patients. Overall, our findings demonstrate the general applicability. In this work we discuss the strengths and limitations of our methodology.
Marshall-Olkin Power-Law Distributions in Length-Frequency of Entities
Venue: arXiv cs.CL 2023
Year: 2023

Entities involve important concepts with concrete meanings and play important roles in numerous linguistic tasks. Entities have different forms in different linguistic tasks and researchers treat those different forms as different concepts. In this paper, we are curious to know whether there are some common characteristics that connect those different forms of entities. Specifically, we investigate the underlying distributions of entities from different types and different languages, trying to figure out some common characteristics behind those diverse entities. After analyzing twelve datasets about different types of entities and eighteen datasets about entities in different languages, we find that while these entities are dramatically diverse from each other in many aspects, their length-frequencies can be well characterized by a family of Marshall-Olkin power-law (MOPL) distributions. We conduct experiments on those thirty datasets about entities in different types and different languages, and experimental results demonstrate that MOPL models characterize the length-frequencies of entities much better than two state-of-the-art power-law models and an alternative log-normal model. Experimental results also demonstrate that MOPL models are scalable to the length-frequency of entities in large-scale real-world datasets.
Channel Coding at Low Capacity
Venue: arXiv cs.IT 2023
Year: 2023

Low-capacity scenarios have become increasingly important in the technology of the Internet of Things (IoT) and the next generation of wireless networks. Such scenarios require efficient and reliable transmission over channels with an extremely small capacity. Within these constraints, the state-of-the-art coding techniques may not be directly applicable. Moreover, the prior work on the finite-length analysis of optimal channel coding provides inaccurate predictions of the limits in the low-capacity regime. In this paper, we study channel coding at low capacity from two perspectives: fundamental limits at finite length and code constructions. We first specify what a low-capacity regime means. We then characterize finite-length fundamental limits of channel coding in the low-capacity regime for various types of channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), and additive white Gaussian noise (AWGN) channels. From the code construction perspective, we characterize the optimal number of repetitions for transmission over binary memoryless symmetric (BMS) channels, in terms of the code blocklength and the underlying channel capacity, such that the capacity loss due to the repetition is negligible. Furthermore, it is shown that capacity-achieving polar codes naturally adopt the aforementioned optimal number of repetitions.