OpenRaiser/Intern-Atlas huggingface dataset:
Energetics of Feedback: Application to Memory Erasure
Venue: arXiv cs.IT 2021
Year: 2021

Landauer's erasure principle states that any irreversible erasure protocol of a single bit memory needs work of at least $k_B T ln2.$ Recent proof of concept experiments has demonstrated that the erasure protocols with work close to the Landauer limit can be devised. Under feedback, where the state of the bit can be measured, the work needed for bit erasure can be lower than $k_B T ln2.$ In this article, we analyze the energetics of feedback enabled erasure, while incorporating the imperfections of experimentally realized memory and bit erasure protocols that admit failure probabilities. We delineate the role of uncertainty in measurements and its effects on the work and entropy changes for a feedback-based erasure. We quantitatively demonstrate that the deficit between the Landauer limit and the minimum average work needed in a feedback-based erasure is accounted for by the mutual information between the measurement and the state of the memory, while incorporating the imperfections inherent in any realization. We experimentally demonstrate analysis results on a memory and erasure protocol realized using optical fields.
Self-adjusting Advertisement of Cache Indicators with Bandwidth Constraints
Venue: arXiv cs.NI 2021
Year: 2021

Cache advertisements reduce the access cost by allowing users to skip the cache when it does not contain their datum. Such advertisements are used in multiple networked domains such as 5G networks, wide area networks, and information-centric networking. The selection of an advertisement strategy exposes a trade-off between the access cost and bandwidth consumption. Still, existing works mostly apply a trial-and-error approach for selecting the best strategy, as the rigorous foundations required for optimizing such decisions is lacking. Our work shows that the desired advertisement policy depends on numerous parameters such as the cache policy, the workload, the cache size, and the available bandwidth. In particular, we show that there is no ideal single configuration. Therefore, we design an adaptive, self-adjusting algorithm that periodically selects an advertisement policy. Our algorithm does not require any prior information about the cache policy, cache size, or workload, and does not require any apriori configuration. Through extensive simulations, using several state-of-the-art cache policies, and real workloads, we show that our approach attains a similar cost to that of the best static configuration (which is only identified in retrospect) in each case.
The Internet Protocol -- Past, some current limitations and a glimpse of a possible future
Venue: arXiv cs.NI 2021
Year: 2021

The network layer is central to the networking scientific area. It is around the network layer that all the data communications develop, and one of its main tasks is to allow the identification of each single interface/machine between the potentially many interfaces in a network. This seminar addresses some of the issues that are usually presented to young Computer Science Engineering students in the course of several classes, but also presents some topics that are not address in networking courses. It is mostly focused on using Internet Protocol addresses in Local Area Networks, also considering issues that belong to the Wide Area Networks, such as data aggregation. This document summarizes the content of a seminar, therefore it comprehends both teaching and researching subject. The seminar starts with a history of the evolution of the communication protocols from the early days of networks up until IPv6. It describes a new approach to define the addresses of network interfaces using Variable Length Subnet Masks, as usually this is a not an easy task for Computer Science Engineering undergraduate students. This summary also describes some of the limitations of the data communication in todays' networks, proposing some solutions, where possible, including a novel mean of connectionless data transmission by using IPv6 addresses, by extension of previously published research. The way the seminar is organized provides a history to the past of the Internet Protocol, a view of some of its well-known current limitations, and a glimpse into a possible future regarding an improved connectionless layer 3 data transfer protocol.
A Design Process of Visual Analytics Applications using Conceptual Graph
Venue: arXiv cs.HC 2021
Year: 2021

State-of-the-art visual analytics techniques in application domains are often designed by VA professionals over qualitative requirement collected from end users. These VA techniques may not leverage users' domain knowledge about how to achieve their analytical goals. In this position paper, we propose a user-driven design process of VA applications centered around a new concept called analytical representation (AR). AR features a formal abstraction of user requirement and their desired analytical trails for certain VA application, and is independent of the actual visualization design. A conceptual graph schema is introduced to define the AR abstraction, which can be created manually or constructed by semi-automated tools. Designing VA applications with AR provides a shared opportunity for both optimal analysis blueprint from the perspective of end users and optimal visualization/algorithm from the perspective of VA designers. We demonstrate the usage of the design process in two case studies.
A Large-scale Study on Unsupervised Outlier Model Selection: Do Internal Strategies Suffice?
Venue: arXiv cs.LG 2021
Year: 2021

Given an unsupervised outlier detection task, how should one select a detection algorithm as well as its hyperparameters (jointly called a model)? Unsupervised model selection is notoriously difficult, in the absence of hold-out validation data with ground-truth labels. Therefore, the problem is vastly understudied. In this work, we study the feasibility of employing internal model evaluation strategies for selecting a model for outlier detection. These so-called internal strategies solely rely on the input data (without labels) and the output (outlier scores) of the candidate models. We setup (and open-source) a large testbed with 39 detection tasks and 297 candidate models comprised of 8 detectors and various hyperparameter configurations. We evaluate 7 different strategies on their ability to discriminate between models w.r.t. detection performance, without using any labels. Our study reveals room for progress -- we find that none would be practically useful, as they select models only comparable to a state-of-the-art detector (with random configuration).
Input Validation with Symbolic Execution
Venue: arXiv cs.PL 2021
Year: 2021

Symbolic execution has always been plagued by the inability to handle programs that require highly structured inputs. Most often, the symbolic execution engine gets overwhelmed by the sheer number of infeasible paths and fails to explore enough feasible paths to gain any respectable coverage. In this paper, we propose a system, InVaSion, that attempts to solve this problem for forking-based symbolic execution engines. We propose an input specification language (ISL) that is based on a finite-state automaton but includes guarded transitions, a set of registers and a set of commands to update the register states. We demonstrate that our language is expressive enough to handle complex input specifications, like the Tiff image format, while not requiring substantial human effort; even the Tiff image specification could be specified in our language with an automaton of about 35 states. InVaSion translates the given program and the input specification into a non-deterministic program and uses symbolic execution to instantiate the non-determinism. This allows our tool to work with any forking-based symbolic execution engine and with no requirement of any special theory solver. Over our set of benchmarks, on an average, InVaSion was able to increase branch coverage from 24.97% to 67.84% over baseline KLEE.
Sexism detection: The first corpus in Algerian dialect with a code-switching in Arabic/ French and English
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, an approach for hate speech detection against women in Arabic community on social media (e.g. Youtube) is proposed. In the literature, similar works have been presented for other languages such as English. However, to the best of our knowledge, not much work has been conducted in the Arabic language. A new hate speech corpus (Arabic\_fr\_en) is developed using three different annotators. For corpus validation, three different machine learning algorithms are used, including deep Convolutional Neural Network (CNN), long short-term memory (LSTM) network and Bi-directional LSTM (Bi-LSTM) network. Simulation results demonstrate the best performance of the CNN model, which achieved F1-score up to 86\% for the unbalanced corpus as compared to LSTM and Bi-LSTM.
High-Level Synthesis of Security Properties via Software-Level Abstractions
Venue: arXiv cs.CR 2021
Year: 2021

High-level synthesis (HLS) is a key component for the hardware acceleration of applications, especially thanks to the diffusion of reconfigurable devices in many domains, from data centers to edge devices. HLS reduces development times by allowing designers to raise the abstraction level and use automated methods for hardware generation. Since security concerns are becoming more and more relevant for data-intensive applications, we investigate how to abstract security properties and use HLS for their integration with the accelerator functionality. We use the case of dynamic information flow tracking, showing how classic software-level abstractions can be efficiently used to hide implementation details to the designers.
Training Deep Normalizing Flow Models in Highly Incomplete Data Scenarios with Prior Regularization
Venue: arXiv cs.LG 2021
Year: 2021

Deep generative frameworks including GANs and normalizing flow models have proven successful at filling in missing values in partially observed data samples by effectively learning -- either explicitly or implicitly -- complex, high-dimensional statistical distributions. In tasks where the data available for learning is only partially observed, however, their performance decays monotonically as a function of the data missingness rate. In high missing data rate regimes (e.g., 60% and above), it has been observed that state-of-the-art models tend to break down and produce unrealistic and/or semantically inaccurate data. We propose a novel framework to facilitate the learning of data distributions in high paucity scenarios that is inspired by traditional formulations of solutions to ill-posed problems. The proposed framework naturally stems from posing the process of learning from incomplete data as a joint optimization task of the parameters of the model being learned and the missing data values. The method involves enforcing a prior regularization term that seamlessly integrates with objectives used to train explicit and tractable deep generative frameworks such as deep normalizing flow models. We demonstrate via extensive experimental validation that the proposed framework outperforms competing techniques, particularly as the rate of data paucity approaches unity.
Adaptive Self-Interference Cancellation for Full-Duplex Wireless Communication Systems
Venue: arXiv cs.IT 2021
Year: 2021

In this letter, we consider single-cell, single-user systems wherein uplink and downlink user equipment communicate with a full-duplex relay. Due to the near-far problem, the self-interference (SI) can be 100-1000x the received signal power. In this context, we consider the adaptive Least Mean Squares (LMS) algorithm to estimate the SI channel and then subtract the SI from the desired received signal before the analog-to-digital converter (ADC). We measure the robustness of this technique in terms of bit error rate (BER) and spectral efficiency.
Distributed Reinforcement Learning for Age of Information Minimization in Real-Time IoT Systems
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, the problem of minimizing the weighted sum of age of information (AoI) and total energy consumption of Internet of Things (IoT) devices is studied. In the considered model, each IoT device monitors a physical process that follows nonlinear dynamics. As the dynamics of the physical process vary over time, each device must find an optimal sampling frequency to sample the real-time dynamics of the physical system and send sampled information to a base station (BS). Due to limited wireless resources, the BS can only select a subset of devices to transmit their sampled information. Thus, edge devices must cooperatively sample their monitored dynamics based on the local observations and the BS must collect the sampled information from the devices immediately, hence avoiding the additional time and energy used for sampling and information transmission. To this end, it is necessary to jointly optimize the sampling policy of each device and the device selection scheme of the BS so as to accurately monitor the dynamics of the physical process using minimum energy. This problem is formulated as an optimization problem whose goal is to minimize the weighted sum of AoI cost and energy consumption. To solve this problem, we propose a novel distributed reinforcement learning (RL) approach for the sampling policy optimization. The proposed algorithm enables edge devices to cooperatively find the global optimal sampling policy using their own local observations. Given the sampling policy, the device selection scheme can be optimized thus minimizing the weighted sum of AoI and energy consumption of all devices. Simulations with real data of PM 2.5 pollution show that the proposed algorithm can reduce the sum of AoI by up to 17.8% and 33.9% and the total energy consumption by up to 13.2% and 35.1%, compared to a conventional deep Q network method and a uniform sampling policy.
Decentralized Statistical Inference with Unrolled Graph Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we investigate the decentralized statistical inference problem, where a network of agents cooperatively recover a (structured) vector from private noisy samples without centralized coordination. Existing optimization-based algorithms suffer from issues of model mismatch and poor convergence speed, and thus their performance would be degraded, provided that the number of communication rounds is limited. This motivates us to propose a learning-based framework, which unrolls well-noted decentralized optimization algorithms (e.g., Prox-DGD and PG-EXTRA) into graph neural networks (GNNs). By minimizing the recovery error via end-to-end training, this learning-based framework resolves the model mismatch issue. Our convergence analysis (with PG-EXTRA as the base algorithm) reveals that the learned model parameters may accelerate the convergence and reduce the recovery error to a large extent. The simulation results demonstrate that the proposed GNN-based learning methods prominently outperform several state-of-the-art optimization-based algorithms in convergence speed and recovery error.
A strongly universal cellular automaton in the dodecagrid with five states
Venue: arXiv cs.DM 2021
Year: 2021

In this paper, we prove that there is a strongly universal cellular automaton in the dodecagrid, the tessellation {5,3,4} of the hyperbolic 3D-space, with five states which is rotation invariant. This improves a previous paper of the author where the automaton required ten states.
Revisiting Indirect Ontology Alignment : New Challenging Issues in Cross-Lingual Context
Venue: arXiv cs.AI 2021
Year: 2021

Ontology alignment process is overwhelmingly cited in Knowledge Engineering as a key mechanism aimed at bypassing heterogeneity and reconciling various data sources, represented by ontologies, i.e., the the Semantic Web cornerstone. In such infrastructures and environments, it is inconceivable to assume that all ontologies covering a particular domain of knowledge are aligned in pairs. Moreover, the high performance of alignment approaches is closely related to two factors, i.e., time consumption and machine resource limitations. Thus, good quality alignments are valuable and it would be appropriate to exploit them. Based on this observation, this article introduces a new method of indirect alignment of ontologies in a cross-lingual context. Indeed, the proposed method deals with alignments of multilingual ontologies and implements an indirect ontology alignment strategy based on a composition and reuse of effective direct alignments. The trigger of the proposed method process is based on alignment algebra which governs the semantics composition of relationships and confidence values. The obtained results, after a thorough and detailed experiment are very encouraging and highlight many positive aspects about the new proposed method.
Curating China's Cultural Revolution (1966-1976): CR/10 as a Warburgian Memory Atlas and Digital Humanities Interface
Venue: arXiv cs.DL 2021
Year: 2021

CR/10 is a digital oral history platform that aims to collect and preserve the cultural memories of China's Cultural Revolution (1966-1976). This paper discusses how CR/10 functions as a Warburgian memory atlas and shapes multifaceted narratives of the historical incident. Through ethnographic research and semi-structured interviews with users within and outside academia, I examined the usability of CR/10 among various user groups and proposed design opportunities to further empower the interface. This paper offered a strong case on the datafication of cultural memories among cultural heritage institutions and contributed to digital archiving scholarship with an innovative methodological lens.
Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problems
Venue: arXiv cs.AI 2021
Year: 2021

The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.
GSECnet: Ground Segmentation of Point Clouds for Edge Computing
Venue: arXiv cs.CV 2021
Year: 2021

Ground segmentation of point clouds remains challenging because of the sparse and unordered data structure. This paper proposes the GSECnet - Ground Segmentation network for Edge Computing, an efficient ground segmentation framework of point clouds specifically designed to be deployable on a low-power edge computing unit. First, raw point clouds are converted into a discretization representation by pillarization. Afterward, features of points within pillars are fed into PointNet to get the corresponding pillars feature map. Then, a depthwise-separable U-Net with the attention module learns the classification from the pillars feature map with an enormously diminished model parameter size. Our proposed framework is evaluated on SemanticKITTI against both point-based and discretization-based state-of-the-art learning approaches, and achieves an excellent balance between high accuracy and low computing complexity. Remarkably, our framework achieves the inference runtime of 135.2 Hz on a desktop platform. Moreover, experiments verify that it is deployable on a low-power edge computing unit powered 10 watts only.
Matrix Chain Multiplication and Polygon Triangulation Revisited and Generalized
Venue: arXiv cs.DM 2021
Year: 2021

The {\it matrix-chain multiplication} problem is a classic problem that is widely taught to illustrate dynamic programming. The textbook solution runs in $θ(n^3)$ time. However, there is a complex $O(n \log n)$-time method \cite{HU82}, based on triangulating convex polygons, and a description without proofs or implementation detail, of a much simpler $O(n^2)$-time method \cite{YAO82}. There is also a linear-time approximation algorithm with a small worst-case error bound \cite{HU-SHING1981}. In this paper, we make five contributions both to theory and pedagogy: 1) We simplify the approach in \cite{YAO82}, and provide complete, correct proofs and implementation details, to establish the $O(n^2)$-time bound. We believe that this exposition is simple enough for classroom use. 2) We extend the $O(n^2)$-time bound to a natural class of polygon-triangulation problems that generalizes the original polygon-triangulation problem in \cite{HU82}. 3) We show that the worst-case running time of the method in \cite{YAO82}, and of our version, is $Θ(n^2)$. 4) We show that in a natural variant of the original polygon-triangulation problem, the approximation method of \cite{HU-SHING1981} does not achieve the same error bound, but does achieve an error bound about twice the original bound. 5) We detail empirical testing, showing that on random data our variant runs in $Θ(n \log n)$ time, while the approach in \cite{YAO82} empirically takes $Θ(n^2)$ time. Software for these tests is posted on the web.
Reducing Racial Bias in Facial Age Prediction using Unsupervised Domain Adaptation in Regression
Venue: arXiv cs.CV 2021
Year: 2021

We propose an approach for unsupervised domain adaptation for the task of estimating someone's age from a given face image. In order to avoid the propagation of racial bias in most publicly available face image datasets into the inefficacy of models trained on them, we perform domain adaptation to motivate the predictor to learn features that are invariant to ethnicity, enhancing the generalization performance across faces of people from different ethnic backgrounds. Exploiting the ordinality of age, we also impose ranking constraints on the prediction of the model and design our model such that it takes as input a pair of images, and outputs both the relative age difference and the rank of the first identity with respect to the other in terms of their ages. Furthermore, we implement Multi-Dimensional Scaling to retrieve absolute ages from the predicted age differences from as few as two labeled images from the domain to be adapted to. We experiment with a publicly available dataset with age labels, dividing it into subsets based on the ethnicity labels, and evaluating the performance of our approach on the data from an ethnicity different from the one that the model is trained on. Additionally, we impose a constraint to preserve the sanity of the predictions with respect to relative and absolute ages, and another to ensure the smoothness of the predictions with respect to the input. We experiment extensively and compare various domain adaptation approaches for the task of regression.
Deep Neural Networks for Relation Extraction
Venue: arXiv cs.CL 2021
Year: 2021

Relation extraction from text is an important task for automatic knowledge base population. In this thesis, we first propose a syntax-focused multi-factor attention network model for finding the relation between two entities. Next, we propose two joint entity and relation extraction frameworks based on encoder-decoder architecture. Finally, we propose a hierarchical entity graph convolutional network for relation extraction across documents.