OpenRaiser/Intern-Atlas huggingface dataset:
Breaking Character: Are Subwords Good Enough for MRLs After All?
Venue: arXiv cs.CL 2022
Year: 2022

Large pretrained language models (PLMs) typically tokenize the input string into contiguous subwords before any pretraining or inference. However, previous studies have claimed that this form of subword tokenization is inadequate for processing morphologically-rich languages (MRLs). We revisit this hypothesis by pretraining a BERT-style masked language model over character sequences instead of word-pieces. We compare the resulting model, dubbed TavBERT, against contemporary PLMs based on subwords for three highly complex and ambiguous MRLs (Hebrew, Turkish, and Arabic), testing them on both morphological and semantic tasks. Our results show, for all tested languages, that while TavBERT obtains mild improvements on surface-level tasks à la POS tagging and full morphological disambiguation, subword-based PLMs achieve significantly higher performance on semantic tasks, such as named entity recognition and extractive question answering. These results showcase and (re)confirm the potential of subword tokenization as a reasonable modeling assumption for many languages, including MRLs.
Minimal Roman Dominating Functions: Extensions and Enumeration
Venue: arXiv cs.DS 2022
Year: 2022

Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman domination functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination: Given a graph $G = (V,E)$ and a function $f:V\to\{0,1,2\}$, is there a minimal Roman domination function $\Tilde{f}$ with $f\leq \Tilde{f}$? Here, $\leq$ lifts $0< 1< 2$ pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $\Oh(\RomanUpperbound^n)$ for graphs of order n; this is complemented by a lower bound example of $Ω(\RomanLowerbound^n)$.
OutfitTransformer: Learning Outfit Representations for Fashion Recommendation
Venue: arXiv cs.CV 2022
Year: 2022

Learning an effective outfit-level representation is critical for predicting the compatibility of items in an outfit, and retrieving complementary items for a partial outfit. We present a framework, OutfitTransformer, that uses the proposed task-specific tokens and leverages the self-attention mechanism to learn effective outfit-level representations encoding the compatibility relationships between all items in the entire outfit for addressing both compatibility prediction and complementary item retrieval tasks. For compatibility prediction, we design an outfit token to capture a global outfit representation and train the framework using a classification loss. For complementary item retrieval, we design a target item token that additionally takes the target item specification (in the form of a category or text description) into consideration. We train our framework using a proposed set-wise outfit ranking loss to generate a target item embedding given an outfit, and a target item specification as inputs. The generated target item embedding is then used to retrieve compatible items that match the rest of the outfit. Additionally, we adopt a pre-training approach and a curriculum learning strategy to improve retrieval performance. Since our framework learns at an outfit-level, it allows us to learn a single embedding capturing higher-order relations among multiple items in the outfit more effectively than pairwise methods. Experiments demonstrate that our approach outperforms state-of-the-art methods on compatibility prediction, fill-in-the-blank, and complementary item retrieval tasks. We further validate the quality of our retrieval results with a user study.
Cello: Efficient Computer Systems Optimization with Predictive Early Termination and Censored Regression
Venue: arXiv cs.LG 2022
Year: 2022

Sample-efficient machine learning (SEML) has been widely applied to find optimal latency and power tradeoffs for configurable computer systems. Instead of randomly sampling from the configuration space, SEML reduces the search cost by dramatically reducing the number of configurations that must be sampled to optimize system goals (e.g., low latency or energy). Nevertheless, SEML only reduces one component of cost -- the total number of samples collected -- but does not decrease the cost of collecting each sample. Critically, not all samples are equal; some take much longer to collect because they correspond to slow system configurations. This paper present Cello, a computer systems optimization framework that reduces sample collection costs -- especially those that come from the slowest configurations. The key insight is to predict ahead of time whether samples will have poor system behavior (e.g., long latency or high energy) and terminate these samples early before their measured system behavior surpasses the termination threshold, which we call it predictive early termination. To predict the future system behavior accurately before it manifests as high runtime or energy, Cello uses censored regression to produces accurate predictions for running samples. We evaluate Cello by optimizing latency and energy for Apache Spark workloads. We give Cello a fixed amount of time to search a combined space of hardware and software configuration parameters. Our evaluation shows that compared to the state-of-the-art SEML approach in computer systems optimization, Cello improves latency by 1.19X for minimizing latency under a power constraint, and improves energy by 1.18X for minimizing energy under a latency constraint.
On complex roots of the independence polynomial
Venue: arXiv cs.DM 2022
Year: 2022

It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial $Z_G(λ)$ of a graph $G$ of maximum degree at most $d+1$ does not vanish provided that $\vertλ\vert \leq \frac{d^d}{(d+1)^{d+1}}$. Significant extensions of this result have recently been given in the case $\Re λ\geq 0$ by Peters and Regts (2019) and Bencs and Csikvári (arxiv:1807.08963). In this paper, our motivation is to further extend these results and find zero free regions when $\Re λ\leq 0$. We begin by giving new geometric criteria for establishing zero-free regions as well as for carrying out semi-rigorous numerical explorations. We then provide two examples of the (rigorous) use of these criteria, by establishing two new zero-free regions in the left-half plane. We also improve upon the results of Bencs and Csikvári (arxiv:1807.08963) for the right half-plane using our framework. By a direct application of the interpolation method of Barvinok, combined with extensions due to Patel and Regts, these results also imply deterministic polynomial time approximation algorithms for the independence polynomial of bounded degree graphs in the new zero-free regions.
Evaluation of Automatic Text Summarization using Synthetic Facts
Venue: arXiv cs.CL 2022
Year: 2022

Despite some recent advances, automatic text summarization remains unreliable, elusive, and of limited practical use in applications. Two main problems with current summarization methods are well known: evaluation and factual consistency. To address these issues, we propose a new automatic reference-less text summarization evaluation system that can measure the quality of any text summarization model with a set of generated facts based on factual consistency, comprehensiveness, and compression rate. As far as we know, our evaluation system is the first system that measures the overarching quality of the text summarization models based on factuality, information coverage, and compression rate.
Low-Complexity Sum-Capacity Maximization for Intelligent Reflecting Surface-Aided MIMO Systems
Venue: arXiv cs.IT 2022
Year: 2022

Reducing computational complexity is crucial in optimizing the phase shifts of Intelligent Reflecting Surface (IRS) systems since IRS-assisted communication systems are generally deployed with a large number of reflecting elements (REs). This letter proposes a low-complexity algorithm, designated as Dimension-wise Sinusoidal Maximization (DSM), to obtain the optimal IRS phase shifts that maximize the sum capacity of a MIMO network. The algorithm exploits the fact that the objective function for the optimization problem is sinusoidal w.r.t. the phase shift of each RE. The numerical results show that DSM achieves a near-maximal sum rate and faster convergence speed than two other benchmark methods.
Multi-User Wireless Communications with Holographic MIMO Surfaces: A Convenient Channel Model and Spectral Efficiency Analysis
Venue: arXiv cs.IT 2022
Year: 2022

The multi-user Holographic Multiple-Input and Multiple-Output Surface (MU-HMIMOS) paradigm, which is capable of realizing large continuous apertures with minimal power consumption and of shaping radio wave propagation at will, has been recently considered as an energy-efficient solution for future wireless networks. The tractable channel modeling of MU-HMIMOS signal propagation is one of the most critical challenges, mainly due to the coupling effect induced by the excessively large number of closely spaced patch antennas. In this paper, we focus on this challenge for downlink communications and model the electromagnetic channel in the wavenumber domain using the Fourier plane wave representation. Based on the proposed model, we devise a Zero-Forcing (ZF) precoding scheme, capitalizing on the sampled channel variance that depends on the number and spacing of the HMIMOS patch antennas, and perform a spectral efficiency analysis. Our simulation results showcase that the more patch antennas and the larger their spacing is, the performance of the considered MU-HMIMOS system improves. In addition, it is demonstrated that our theoretical performance expressions approximate sufficiently well the simulated spectral efficiency, even for the highly correlated cases, thus verifying the effectiveness and robustness of the presented analytical framework.
Constrained Shortest Path and Hierarchical Structures
Venue: arXiv cs.DS 2022
Year: 2022

The Constraint Shortest Path (CSP) problem is as follows. An $n$-vertex graph is given, each edge/arc assigned two weights. Let us call them "cost" and "length" for definiteness. Finding a min-cost upper-bounded length path between a given pair of vertices is required. The problem is NP-hard even when the lengths of all edges are the same. Therefore, various approximation algorithms have been proposed in the literature for it. The constraint on path length can be accounted for by considering one edge weight equals to a linear combination of cost and length. By varying the multiplier value in a linear combination, a feasible solution delivers a minimum to the function with new weights. At the same time, Dijkstra's algorithm or its modifications are used to construct the shortest path with the current weights of the edges. However, with insufficiently large graphs, this approach may turn out to be time-consuming. In this article, we propose to look for a solution, not in the original graph but specially constructed hierarchical structures (HS). We show that the shortest path in the HS is constructed with $O(m)$-time complexity, where $m$ is the number of edges/arcs of the graph, and the approximate solution in the case of integer costs and lengths of the edges is found with $O(m\log n)$-time complexity. The a priori estimate of the algorithm's accuracy turned out to depend on the parameters of the problem and can be significant. Therefore, to evaluate the algorithm's effectiveness, we conducted a numerical experiment on the graphs of roads of megalopolis and randomly constructed unit-disk graphs (UDGs). The numerical experiment results show that in the HS, a solution close to optimal one is built 10--100 times faster than in the methods which use Dijkstra's algorithm to build a min-weight path in the original graph.
Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares
Venue: arXiv cs.LG 2022
Year: 2022

We consider potentially non-convex optimization problems, for which optimal rates of approximation depend on the dimension of the parameter space and the smoothness of the function to be optimized. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees, while also providing a posteriori certificates of optimality. Our general formulation builds on infinite-dimensional sums-of-squares and Fourier analysis, and is instantiated on the minimization of multivariate periodic functions.
A Comparative Study of Pre-trained Encoders for Low-Resource Named Entity Recognition
Venue: arXiv cs.CL 2022
Year: 2022

Pre-trained language models (PLM) are effective components of few-shot named entity recognition (NER) approaches when augmented with continued pre-training on task-specific out-of-domain data or fine-tuning on in-domain data. However, their performance in low-resource scenarios, where such data is not available, remains an open question. We introduce an encoder evaluation framework, and use it to systematically compare the performance of state-of-the-art pre-trained representations on the task of low-resource NER. We analyze a wide range of encoders pre-trained with different strategies, model architectures, intermediate-task fine-tuning, and contrastive learning. Our experimental results across ten benchmark NER datasets in English and German show that encoder performance varies significantly, suggesting that the choice of encoder for a specific low-resource scenario needs to be carefully evaluated.
Multi-Objective Yield Optimization for Electrical Machines using Machine Learning
Venue: arXiv cs.CE 2022
Year: 2022

This work deals with the design optimization of electrical machines under the consideration of manufacturing uncertainties. In order to efficiently quantify the uncertainty, blackbox machine learning methods are employed. A multi-objective optimization problem is formulated, maximizing simultaneously the reliability, i.e., the yield, and further performance objectives, e.g., the costs. A permanent magnet synchronous machine is modeled and simulated in commercial finite element simulation software. Four approaches for solving the multi-objective optimization problem are described and numerically compared, namely: epsilon-constraint scalarization, weighted sum scalarization, a multi-start weighted sum approach and a genetic algorithm.
VWR2A: A Very-Wide-Register Reconfigurable-Array Architecture for Low-Power Embedded Devices
Venue: arXiv cs.AR 2022
Year: 2022

Edge-computing requires high-performance energy-efficient embedded systems. Fixed-function or custom accelerators, such as FFT or FIR filter engines, are very efficient at implementing a particular functionality for a given set of constraints. However, they are inflexible when facing application-wide optimizations or functionality upgrades. Conversely, programmable cores offer higher flexibility, but often with a penalty in area, performance, and, above all, energy consumption. In this paper, we propose VWR2A, an architecture that integrates high computational density and low power memory structures (i.e., very-wide registers and scratchpad memories). VWR2A narrows the energy gap with similar or better performance on FFT kernels with respect to an FFT accelerator. Moreover, VWR2A flexibility allows to accelerate multiple kernels, resulting in significant energy savings at the application level.
Landmarks and Regions: A Robust Approach to Data Extraction
Venue: arXiv cs.SE 2022
Year: 2022

We propose a new approach to extracting data items or field values from semi-structured documents. Examples of such problems include extracting passenger name, departure time and departure airport from a travel itinerary, or extracting price of an item from a purchase receipt. Traditional approaches to data extraction use machine learning or program synthesis to process the whole document to extract the desired fields. Such approaches are not robust to format changes in the document, and the extraction process typically fails even if changes are made to parts of the document that are unrelated to the desired fields of interest. We propose a new approach to data extraction based on the concepts of landmarks and regions. Humans routinely use landmarks in manual processing of documents to zoom in and focus their attention on small regions of interest in the document. Inspired by this human intuition, we use the notion of landmarks in program synthesis to automatically synthesize extraction programs that first extract a small region of interest, and then automatically extract the desired value from the region in a subsequent step. We have implemented our landmark-based extraction approach in a tool LRSyn, and show extensive evaluation on documents in HTML as well as scanned images of invoices and receipts. Our results show that our approach is robust to various types of format changes that routinely happen in real-world settings.
Convolutional autoencoders for spatially-informed ensemble post-processing
Venue: arXiv cs.LG 2022
Year: 2022

Ensemble weather predictions typically show systematic errors that have to be corrected via post-processing. Even state-of-the-art post-processing methods based on neural networks often solely rely on location-specific predictors that require an interpolation of the physical weather model's spatial forecast fields to the target locations. However, potentially useful predictability information contained in large-scale spatial structures within the input fields is potentially lost in this interpolation step. Therefore, we propose the use of convolutional autoencoders to learn compact representations of spatial input fields which can then be used to augment location-specific information as additional inputs to post-processing models. The benefits of including this spatial information is demonstrated in a case study of 2-m temperature forecasts at surface stations in Germany.
Challenges in implementing DDR3 memory interface on PCB systems: a methodology for interfacing DDR3 SDRAM DIMM to an FPGA
Venue: arXiv cs.AR 2022
Year: 2022

Undoubtedly faster, larger and lower power per bit, but just how do you go about interfacing a DDR3 SDRAM DIMM to an FPGA? The DDR3 standard addresses the faster, more bandwidth and lower power per bit need, but it introduces new design challenges in addition to challenges introduced by DDR2 ODT, slew rate derating, etc. The DDR3 fly-by topology requirement means customers designing DDR3 memories must now account for write leveling and read de-skew on the PCB. This paper will cover modeling, simulation, and physical layout approaches required to meet JEDEC-defined termination and tight timing requirements for designing DDR3 memory interfaces on PCB systems.
FastMapSVM: Classifying Complex Objects Using the FastMap Algorithm and Support-Vector Machines
Venue: arXiv cs.CV 2022
Year: 2022

Neural Networks and related Deep Learning methods are currently at the leading edge of technologies used for classifying objects. However, they generally demand large amounts of time and data for model training; and their learned models can sometimes be difficult to interpret. In this paper, we advance FastMapSVM -- an interpretable Machine Learning framework for classifying complex objects -- as an advantageous alternative to Neural Networks for general classification tasks. FastMapSVM extends the applicability of Support-Vector Machines (SVMs) to domains with complex objects by combining the complementary strengths of FastMap and SVMs. FastMap is an efficient linear-time algorithm that maps complex objects to points in a Euclidean space while preserving pairwise domain-specific distances between them. We demonstrate the efficiency and effectiveness of FastMapSVM in the context of classifying seismograms. We show that its performance, in terms of precision, recall, and accuracy, is comparable to that of other state-of-the-art methods. However, compared to other methods, FastMapSVM uses significantly smaller amounts of time and data for model training. It also provides a perspicuous visualization of the objects and the classification boundaries between them. We expect FastMapSVM to be viable for classification tasks in many other real-world domains.
SoK: Privacy Preserving Machine Learning using Functional Encryption: Opportunities and Challenges
Venue: arXiv cs.CR 2022
Year: 2022

With the advent of functional encryption, new possibilities for computation on encrypted data have arisen. Functional Encryption enables data owners to grant third-party access to perform specified computations without disclosing their inputs. It also provides computation results in plain, unlike Fully Homomorphic Encryption. The ubiquitousness of machine learning has led to the collection of massive private data in the cloud computing environment. This raises potential privacy issues and the need for more private and secure computing solutions. Numerous efforts have been made in privacy-preserving machine learning (PPML) to address security and privacy concerns. There are approaches based on fully homomorphic encryption (FHE), secure multiparty computation (SMC), and, more recently, functional encryption (FE). However, FE-based PPML is still in its infancy and has not yet gotten much attention compared to FHE-based PPML approaches. In this paper, we provide a systematization of PPML works based on FE summarizing state-of-the-art in the literature. We focus on Inner-product-FE and Quadratic-FE-based machine learning models for the PPML applications. We analyze the performance and usability of the available FE libraries and their applications to PPML. We also discuss potential directions for FE-based PPML approaches. To the best of our knowledge, this is the first work to systematize FE-based PPML approaches.
Submodular Maximization Subject to Matroid Intersection on the Fly
Venue: arXiv cs.DS 2022
Year: 2022

Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especially when dealing with multiple constraints. In this work, we nearly close several basic gaps in submodular maximization subject to $k$ matroid constraints in the data stream model. We present a new hardness result showing that super polynomial memory in $k$ is needed to obtain an $o(k / \log k)$-approximation. This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation by maintaining a set of elements whose size is independent of the stream size. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a $2$-approximation may exist in this setting, and only a complexity-theoretic hardness of $1.91$ was known. We prove an unconditional hardness of $2.69$.
The Principle of Least Sensing: A Privacy-Friendly Sensing Paradigm for Urban Big Data Analytics
Venue: arXiv cs.AI 2022
Year: 2022

With the worldwide emergence of data protection regulations, how to conduct law-regulated big data analytics becomes a challenging and fundamental problem. This article introduces the principle of least sensing, a promising sensing paradigm toward law-regulated big data analytics.