OpenRaiser/Intern-Atlas huggingface dataset:
A Framework of Reconfigurable Transducer Nodes for Smart Home Environments
Venue: arXiv cs.NI 2022
Year: 2022

This letter presents a transducer network framework that supports the amalgamation of multiple transducers into single wireless nodes. This approach is aimed at decreasing energy consumption by reducing the number of wireless transceivers involved in such networks. To make wireless nodes easily reconfigurable, a plug and play mechanism is applied to enable the clustering of any number of transducers. Furthermore, an algorithm is proposed to dynamically detect added and removed transducers from a node. Lastly, an XML based protocol is devised to allow nodes to communicate a description of their layout, measured data and control information. To verify the proposed framework, multiple reconfigurable wireless nodes are used to monitor the dynamic condition of a multiple rooms during a period of 24 hours in order to emulate a smart home scenario.
Network Message Field Type Classification and Recognition for Unknown Binary Protocols
Venue: arXiv cs.CR 2022
Year: 2022

Reverse engineering of unknown network protocols based on recorded traffic traces enables security analyses and debugging of undocumented network services. In particular for binary protocols, existing approaches (1) lack comprehensive methods to classify or determine the data type of a discovered segment in a message, e.,g., a number, timestamp, or network address, that would allow for a semantic interpretation and (2) have strong assumptions that prevent analysis of lower-layer protocols often found in IoT or mobile systems. In this paper, we propose the first generic method for analyzing unknown messages from binary protocols to reveal the data types in message fields. To this end, we split messages into segments of bytes and use their vector interpretation to calculate similarities. These can be used to create clusters of segments with the same type and, moreover, to recognize specific data types based on the clusters' characteristics. Our extensive evaluation shows that our method provides precise classification in most cases and a data-type-recognition precision of up to 100% at reasonable recall, improving the state-of-the-art by a factor between 1.3 and 3.7 in realistic scenarios. We open-source our implementation to facilitate follow-up works.
Unsupervised Question Duplicate and Related Questions Detection in e-learning platforms
Venue: arXiv cs.CL 2022
Year: 2022

Online learning platforms provide diverse questions to gauge the learners' understanding of different concepts. The repository of questions has to be constantly updated to ensure a diverse pool of questions to conduct assessments for learners. However, it is impossible for the academician to manually skim through the large repository of questions to check for duplicates when onboarding new questions from external sources. Hence, we propose a tool QDup in this paper that can surface near-duplicate and semantically related questions without any supervised data. The proposed tool follows an unsupervised hybrid pipeline of statistical and neural approaches for incorporating different nuances in similarity for the task of question duplicate detection. We demonstrate that QDup can detect near-duplicate questions and also suggest related questions for practice with remarkable accuracy and speed from a large repository of questions. The demo video of the tool can be found at https://www.youtube.com/watch?v=loh0_-7XLW4.
MaNLP@SMM4H22: BERT for Classification of Twitter Posts
Venue: arXiv cs.CL 2022
Year: 2022

The reported work is our straightforward approach for the shared task Classification of tweets self-reporting age organized by the Social Media Mining for Health Applications (SMM4H) workshop. This literature describes the approach that was used to build a binary classification system, that classifies the tweets related to birthday posts into two classes namely, exact age(positive class) and non-exact age(negative class). We made two submissions with variations in the preprocessing of text which yielded F1 scores of 0.80 and 0.81 when evaluated by the organizers.
Maybe, Maybe Not: A Survey on Uncertainty in Visualization
Venue: arXiv cs.HC 2022
Year: 2022

Understanding and evaluating uncertainty play a key role in decision-making. When a viewer studies a visualization that demands inference, it is necessary that uncertainty is portrayed in it. This paper showcases the importance of representing uncertainty in visualizations. It provides an overview of uncertainty visualization and the challenges authors and viewers face when working with such charts. I divide the visualization pipeline into four parts, namely data collection, preprocessing, visualization, and inference, to evaluate how uncertainty impacts them. Next, I investigate the authors' methodologies to process and design uncertainty. Finally, I contribute by exploring future paths for uncertainty visualization.
Farm Environmental Data Analyzer using a Decentralised system and R
Venue: arXiv cs.DC 2022
Year: 2022

Data/Web Hosting is a service that lets enterprises or selves present their data on the internet that users can access. The firm providing such services are web/data host. Apart from that, such services require incessant support, and not everyone can afford a particular centralized data host service. The peer-to-peer(P2P) protocol, the Interplanetary file system(IPFS), is augmenting into a legitimate alternative to traditional data and web hosting. This paper put forward a decentralized blockchain IPFS-based interactive manageable model, and the work presents an application and schematic that serves as a Proof of Concept(PoC) of decentralized blockchain technology that can be wielded to create an immutable record of energy and resource usage for further analysis and estimation of yield at a scale. IPFS hosts an immutable record that would be independently verifiable and available in perpetuity. First, having the user connect to the service through an IPFS node, then requesting the user upload their data. Then the data is uploaded, and a CID(Content Identification) and a QR code are returned to the user, who can then compute and visualize the results through the application. This system enables the novel application of decentralized data storage to capture, add and visualize yield and environmental data and track it further down the supply chain.
Key Feature Replacement of In-Distribution Samples for Out-of-Distribution Detection
Venue: arXiv cs.CV 2022
Year: 2022

Out-of-distribution (OOD) detection can be used in deep learning-based applications to reject outlier samples from being unreliably classified by deep neural networks. Learning to classify between OOD and in-distribution samples is difficult because data comprising the former is extremely diverse. It has been observed that an auxiliary OOD dataset is most effective in training a "rejection" network when its samples are semantically similar to in-distribution images. We first deduce that OOD images are perceived by a deep neural network to be semantically similar to in-distribution samples when they share a common background, as deep networks are observed to incorrectly classify such images with high confidence. We then propose a simple yet effective Key In-distribution feature Replacement BY inpainting (KIRBY) procedure that constructs a surrogate OOD dataset by replacing class-discriminative features of in-distribution samples with marginal background features. The procedure can be implemented using off-the-shelf vision algorithms, where each step within the algorithm is shown to make the surrogate data increasingly similar to in-distribution data. Design choices in each step are studied extensively, and an exhaustive comparison with state-of-the-art algorithms demonstrates KIRBY's competitiveness on various benchmarks.
Orbital Angular Momentum: From State Disentanglement Towards the Secrecy Outage Probability
Venue: arXiv cs.IT 2022
Year: 2022

How are we able to fix it so as to theoretically go over it, if the optimality and efficiency of the orbital angular momentum (OAM) multiplexing technique in a multi-input multi-output (MIMO) system fails in practice -- something that technically causes a considerable reduction in the maximum achievable value of the transceiver's degree-of-freedom? Is the aforementioned challenging issue theoretically interpretable? This paper considers the above mentioned challenge in the reconfigurable intelligent surface based systems -- as an exemplified system model -- and consequently proposes a Mendelain randomaisation (MR) technique through which we can further overcome the aforementioned challenge. Towards such end and in this paper, we take into account a Markov chain $\mathcal{G}-\circ-\mathcal{X}-\circ-\mathcal{Y}-\circ-\mathcal{V}$ while $\mathcal{G}$, $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{V}$ respectively denote transmit design parameters, quality of goods, error floor in data detection and non-orthogonality set in the OAM implementation -- arisen from other non-optimalities, disturbances and inefficiencies such as the atmospheric Kolmogorov turbulence. Furthermore, we consider a not-necessarily-Gaussian randomisation method according to which the resultant probability distribution function (PDF) is 2-D in relation to a definable outage probability in the design problem in relation to $\mathcal{Y}$ -- that is, in terms of $β_{\mathcal{X}}θ$ while the randomisation is applied to $θ$ as the control input which should be optimally derived as the graph-theoretically associating parameter between $\mathcal{X}$ and $\mathcal{Y}$, and $β_{\mathcal{X}}$ is the the associating parameter between $\mathcal{G}$ and the exposure $\mathcal{X}$.
The expressive power of revised Datalog on problems with closure properties
Venue: arXiv cs.LO 2023
Year: 2023

In this paper, we study the expressive power of revised Datalog on the problems that are closed under substructures. We show that revised Datalog cannot define all the problems that are in PTIME and closed under substructures. As a corollary, LFP cannot define all the extension-closed problems that are in PTIME.
Graphs, Matrices, and the GraphBLAS: Seven Good Reasons
Venue: arXiv cs.DC 2023
Year: 2023

The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard (istc-bigdata.org/GraphBlas) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs.
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings
Venue: arXiv cs.LO 2023
Year: 2023

We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting instead of string rewriting and by generalizing to ordered semirings. In this way we obtain a framework which is inspired by the tropical and arctic type graphs of [5] and introduces a new variant of arithmetic type graphs. These type graphs can be used to assign weights to graphs and to show that these weights decrease in every rewriting step in order to prove termination. We present an example involving counters and discuss the implementation in the tool Grez.
Optimal quantizers for a nonuniform distribution on a Sierpinski carpet
Venue: arXiv cs.IT 2023
Year: 2023

The purpose of quantization for a probability distribution is to estimate the probability by a discrete probability with finite support. In this paper, a nonuniform probability measure $P$ on $\mathbb R^2$ which has support the Sierpiński carpet generated by a set of four contractive similarity mappings with equal similarity ratios has been considered. For this probability measure, the optimal sets of $n$-means and the $n$th quantization errors are investigated for all $n\geq 2$.
Efficient Algorithms for Scheduling Moldable Tasks
Venue: arXiv cs.DS 2023
Year: 2023

We study the problem of scheduling $n$ independent moldable tasks on $m$ processors that arises in large-scale parallel computations. When tasks are monotonic, the best known result is a $(\frac{3}{2}+ε)$-approximation algorithm for makespan minimization with a complexity linear in $n$ and polynomial in $\log{m}$ and $\frac{1}ε$ where $ε$ is arbitrarily small. We propose a new perspective of the existing speedup models: the speedup of a task $T_{j}$ is linear when the number $p$ of assigned processors is small (up to a threshold $δ_{j}$) while it presents monotonicity when $p$ ranges in $[δ_{j}, k_{j}]$; the bound $k_{j}$ indicates an unacceptable overhead when parallelizing on too many processors. The generality of this model is proved to be between the classic monotonic and linear-speedup models. For any given integer $δ\geq 5$, let $u=\left\lceil \sqrt[2]δ \right\rceil-1\geq 2$. In this paper, we propose a $\frac{1}{θ(δ)} (1+ε)$-approximation algorithm for makespan minimization where $θ(δ) = \frac{u+1}{u+2}\left( 1- \frac{k}{m} \right)$ ($m\gg k$). As a by-product, we also propose a $θ(δ)$-approximation algorithm for throughput maximization with a common deadline.
Multi-mesh multi-objective optimization with application to a model problem in urban design
Venue: arXiv cs.CE 2023
Year: 2023

We present an application of multi-mesh finite element methods as part of a methodology for optimizing settlement layouts. By formulating a multi-objective optimization problem, we demonstrate how a given number of buildings may be optimally placed on a given piece of land with respect to both wind conditions and the view experienced from the buildings. The wind flow is modeled by a multi-mesh (cut finite element) method. This allows each building to be embedded in a boundary-fitted mesh which can be moved freely on top of a fixed background mesh. This approach enables a multitude of settlement layouts to be evaluated without the need for costly mesh generation when changing the configuration of buildings. The view is modeled by a measure that takes into account the totality of unobstructed view from the collection of buildings, and is efficiently computed by rasterization.
Improving Covariance-Regularized Discriminant Analysis for EHR-based Predictive Analytics of Diseases
Venue: arXiv cs.LG 2023
Year: 2023

Linear Discriminant Analysis (LDA) is a well-known technique for feature extraction and dimension reduction. The performance of classical LDA, however, significantly degrades on the High Dimension Low Sample Size (HDLSS) data for the ill-posed inverse problem. Existing approaches for HDLSS data classification typically assume the data in question are with Gaussian distribution and deal the HDLSS classification problem with regularization. However, these assumptions are too strict to hold in many emerging real-life applications, such as enabling personalized predictive analysis using Electronic Health Records (EHRs) data collected from an extremely limited number of patients who have been diagnosed with or without the target disease for prediction. In this paper, we revised the problem of predictive analysis of disease using personal EHR data and LDA classifier. To fill the gap, in this paper, we first studied an analytical model that understands the accuracy of LDA for classifying data with arbitrary distribution. The model gives a theoretical upper bound of LDA error rate that is controlled by two factors: (1) the statistical convergence rate of (inverse) covariance matrix estimators and (2) the divergence of the training/testing datasets to fitted distributions. To this end, we could lower the error rate by balancing the two factors for better classification performance. Hereby, we further proposed a novel LDA classifier De-Sparse that leverages De-sparsified Graphical Lasso to improve the estimation of LDA, which outperforms state-of-the-art LDA approaches developed for HDLSS data. Such advances and effectiveness are further demonstrated by both theoretical analysis and extensive experiments on EHR datasets.
Accelerated Stochastic ADMM with Variance Reduction
Venue: arXiv cs.NA 2023
Year: 2023

Alternating Direction Method of Multipliers (ADMM) is a popular method for solving large-scale Machine Learning problems. Stochastic ADMM was proposed to reduce the per iteration computational complexity, which is more suitable for big data problems. Recently, variance reduction techniques have been integrated with stochastic ADMM in order to get a faster convergence rate, such as SAG-ADMM and SVRG-ADMM. However, their convergence rate is still suboptimal w.r.t the smoothness constant. In this paper, we propose an accelerated stochastic ADMM algorithm with variance reduction, which enjoys a faster convergence than all the existing stochastic ADMM algorithms. We theoretically analyse its convergence rate and show its dependence on the smoothness constant is optimal. We also empirically validate its effectiveness and show its priority over other stochastic ADMM algorithms.
It's Written All Over Your Face: Full-Face Appearance-Based Gaze Estimation
Venue: arXiv cs.CV 2023
Year: 2023

Eye gaze is an important non-verbal cue for human affect analysis. Recent gaze estimation work indicated that information from the full face region can benefit performance. Pushing this idea further, we propose an appearance-based method that, in contrast to a long-standing line of work in computer vision, only takes the full face image as input. Our method encodes the face image using a convolutional neural network with spatial weights applied on the feature maps to flexibly suppress or enhance information in different facial regions. Through extensive evaluation, we show that our full-face method significantly outperforms the state of the art for both 2D and 3D gaze estimation, achieving improvements of up to 14.3% on MPIIGaze and 27.7% on EYEDIAP for person-independent 3D gaze estimation. We further show that this improvement is consistent across different illumination conditions and gaze directions and particularly pronounced for the most challenging extreme head poses.
The paradigm-shift of social spambots: Evidence, theories, and tools for the arms race
Venue: arXiv cs.SI 2023
Year: 2023

Recent studies in social media spam and automation provide anecdotal argumentation of the rise of a new generation of spambots, so-called social spambots. Here, for the first time, we extensively study this novel phenomenon on Twitter and we provide quantitative evidence that a paradigm-shift exists in spambot design. First, we measure current Twitter's capabilities of detecting the new social spambots. Later, we assess the human performance in discriminating between genuine accounts, social spambots, and traditional spambots. Then, we benchmark several state-of-the-art techniques proposed by the academic literature. Results show that neither Twitter, nor humans, nor cutting-edge applications are currently capable of accurately detecting the new social spambots. Our results call for new approaches capable of turning the tide in the fight against this raising phenomenon. We conclude by reviewing the latest literature on spambots detection and we highlight an emerging common research trend based on the analysis of collective behaviors. Insights derived from both our extensive experimental campaign and survey shed light on the most promising directions of research and lay the foundations for the arms race against the novel social spambots. Finally, to foster research on this novel phenomenon, we make publicly available to the scientific community all the datasets used in this study.
Faster truncated integer multiplication
Venue: arXiv cs.SC 2023
Year: 2023

We present new algorithms for computing the low $n$ bits or the high $n$ bits of the product of two $n$-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full $2n$-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences.
An Improved Integrality Gap for Steiner Tree
Venue: arXiv cs.DS 2023
Year: 2023

A promising approach for obtaining improved approximation algorithms for Steiner tree is to use the bidirected cut relaxation (BCR). The integrality gap of this relaxation is at least $36/31$, and it has long been conjectured that its true value is very close to this lower bound. However, the best upper bound for general graphs was an almost trivial $2$. We improve this bound to $3/2$ by a combinatorial algorithm based on the primal-dual schema.
Iterative method for simultaneous sparse approximation
Venue: arXiv cs.IT 2023
Year: 2023

This paper studies the problem of Simultaneous Sparse Approximation (SSA). This problem arises in many applications which work with multiple signals maintaining some degree of dependency such as radar and sensor networks. In this paper, we introduce a new method towards joint recovery of several independent sparse signals with the same support. We provide an analytical discussion on the convergence of our method called Simultaneous Iterative Method with Adaptive Thresholding (SIMAT). Additionally, we compare our method with other group-sparse reconstruction techniques, i.e., Simultaneous Orthogonal Matching Pursuit (SOMP), and Block Iterative Method with Adaptive Thresholding (BIMAT) through numerical experiments. The simulation results demonstrate that SIMAT outperforms these algorithms in terms of the metrics Signal to Noise Ratio (SNR) and Success Rate (SR). Moreover, SIMAT is considerably less complicated than BIMAT, which makes it feasible for practical applications such as implementation in MIMO radar systems.
On the induced problem for fixed-template CSPs
Venue: arXiv cs.CC 2023
Year: 2023

The Constraint Satisfaction Problem (CSP) is a problem of computing a homomorphism $\mathbf{R}\to \mathbfΓ$ between two relational structures, where $\mathbf{R}$ is defined over a domain $V$ and $\mathbfΓ$ is defined over a domain $D$. In a fixed template CSP, denoted $\rm{CSP}(\mathbfΓ)$, the right side structure $\mathbfΓ$ is fixed and the left side structure $\mathbf{R}$ is unconstrained. In the last two decades it was discovered that the reasons that make fixed template CSPs polynomially solvable are of algebraic nature, namely, templates that are tractable should be preserved under certain polymorphisms. From this perspective the following problem looks natural: given a prespecified finite set of algebras ${\mathcal B}$ whose domain is $D$, is it possible to present the solution set of a given instance of $\rm{CSP}(\mathbfΓ)$ as a subalgebra of ${\mathbb A}_1\times ... \times {\mathbb A}_{|V|}$ where ${\mathbb A}_i\in {\mathcal B}$? We study this problem and show that it can be reformulated as an instance of a certain fixed-template CSP over another template $\mathbfΓ^{\mathcal B}$. We study conditions under which $\rm{CSP}(\mathbfΓ)$ can be reduced to $\rm{CSP}(\mathbfΓ^{\mathcal B})$. This issue is connected with the so-called CSP with an input prototype, formulated in the following way: given a homomorphism from $\mathbf{R}$ to $\mathbfΓ^{\mathcal B}$ find a homomorphism from $\mathbf{R}$ to $\mathbfΓ$. We prove that if ${\mathcal B}$ contains only tractable algebras, then the latter CSP with an input prototype is tractable. We also prove that $\rm{CSP}(\mathbfΓ^{\mathcal B})$ can be reduced to $\rm{CSP}(\mathbfΓ)$ if the set ${\mathcal B}$, treated as a relation over $D$, can be expressed as a primitive positive formula over $\mathbfΓ$.