In machine learning applications, mapping math knowledge from the series of tokens in a formula or expression to their linguistic semantic meaning remains an open area of research. One fundamental task towards that end is the chunking of a math equation/expression into meaningful math entities. It is the equivalent of sentence segmentation or chunking in natural language processing. Math chunking is quite broad and in a nascent stage in math linguistics. In this paper, we begin an exploration into this task using deep learning on a focused part of chunking, namely, recognition of functions (along with their arguments and parameters), in input equations. Specifically, we propose math-chunking models to identify a list of standard functions. We further develop an annotated dataset to train and evaluate our models. Our experimental results show that one of our proposed deep learning models, namely BiLSTM-CRF, can achieve rather high state-of-the-art performance on the mathematical formula chunking task.

Digital mathematical libraries assemble the knowledge of years of mathematical research. Numerous disciplines (e.g., physics, engineering, pure and applied mathematics) rely heavily on compendia gathered findings. Likewise, modern research applications rely more and more on computational solutions, which are often calculated and verified by computer algebra systems. Hence, the correctness, accuracy, and reliability of both digital mathematical libraries and computer algebra systems is a crucial attribute for modern research. In this paper, we present a novel approach to verify a digital mathematical library and two computer algebra systems with one another by converting mathematical expressions from one system to the other. We use our previously eveloped conversion tool (referred to as LaCASt) to translate formulae from the NIST Digital Library of Mathematical Functions to the computer algebra systems Maple and Mathematica. The contributions of our presented work are as follows: (1) we present the most comprehensive verification of computer algebra systems and digital mathematical libraries with one another; (2) we significantly enhance the performance of the underlying translator in terms of coverage and accuracy; and (3) we provide open access to translations for Maple and Mathematica of the formulae in the NIST Digital Library of Mathematical Functions.

Clear and efficient communication requires more than grammatical correctness to ensure fluency and semantic correctness, especially for non-native speakers. Thus, we propose a new task – Sentence Denoising, to go beyond Grammatical Error Correction (GEC). We define a rich and linguistics-inspired noise taxonomy consisting of 13 types of noise, and categorize them into vagueness, redundancy, and incoherence. We then generate and study 4 types of noise out of the 13 because they serve as building blocks. Methods are proposed to inject targeted noise into sentences for building datasets. We publish them and give benchmarks for denoising both individual noise and compound noise. Finally, an efficient training approach is designed for denoising combinations of noise.

In this paper we present our results from mining text to identify syntactic patterns to help discriminate between creative metaphorical expressions and non-metaphorical expressions, and we also present an application of our findings to the generation of novel metaphors. We trained an unsupervised LSTM model and use it in an inference engine to generate novel metaphors, where novelty is ensured in multiple ways. First, we use a weighted random choice with a "constraining factor" to select each word in our metaphor generation. Next, the inference engine checks for originality by ensuring that none of the generated sentence fragments match original fragments from the training data. Finally, the inference engine provides assurance that a metaphorical expression was generated, by checking against the identified syntactic patterns of metaphors that did not show up in the non-metaphorical language. We found that there are 611 repeated sentence patterns for metaphorical expressions that never appeared as the sentence pattern of non-metaphorical expressions. Furthermore, in a test set of 360 automatically generated metaphors, we observed 123 different syntactic patterns. This is a great deal more than the number of patterns used in the current state-of-the-art metaphor generators that rely on templates to generate the metaphors.

Misunderstanding happens all the time, especially when a non-native speaker is involved. To help recover the original meaning, we define categories of noise in an English sentence and differentiate our problem from Grammatical Error Correction (GEC). Methods are proposed to inject targeted noise into sentences for building training sets. Finally, a system comprised of two parts is designed for sentence correction (aka denoising) - One being fine-tuned BERT models for noise classification, and the other being Transformer models for "translating" noisy sentences into correct ones.

This paper addresses the effect of data reduction on speeding up training while keeping or improving the accuracy performance of classification. Since many studies have focused on feature selection, but did not adequately consider instance selection, our work focuses on both instance reduction and feature reduction, integrated into a whole reduction method. We examined in prior work Simple Random Sample Selection without Replacement, integrated with the Information Gain-based Feature Selection method, and compared its performance with the unintegrated instance selection and feature selection alone, using a single reduction rate. Our results proved that the integration of instance and feature selection performed much better than instance or feature selection alone. In this paper, we examine our approach in more depth, trying different reduction rates and different distributions of reduction rates between instance reduction and feature reduction. Our results show that for nearly all common classifiers, our integrated data reduction speeds up training significantly while keeping the accuracy unchanged (and sometimes even improved) at even high reduction rates. We also present the optimal feature-instance reduction-rates tradeoff.

The dramatic increase in dataset volumes available to train learning models has led to great advances in machine learning, but at the cost of slowing down training. This paper addresses the effect of data reduction on speeding up training while keeping or improving the accuracy performance of classification. Since many studies have focused on feature selection, but did not adequately consider instance selection, our work focuses on both instance reduction and feature reduction, integrated into a holistic reduction approach. We examined in prior work Simple Random Sample Selection without Replacement, integrated with the Information Gain-based Feature Selection method, and compared its performance with the unintegrated instance selection and feature selection individually, applied at various reduction rates. Our results proved that the integration of instance and feature selection performed much better than instance or feature selection alone, in terms of both training speedup and even accuracy improvement. In this paper, a novel transpose-based instance selection approach is introduced and integrated with feature selection, and its performance is investigated on classification and compared with the top-performing results of our prior work. Our results show that our new integrated method leads to significant increase in training speedup without impacting classification accuracy, and in fact, for some classifiers like Naive Bayes, the accuracy goes up considerably.

Restaurant servers are an example of an insider threat to the security of restaurant financial data. This paper applies machine learning to detect the digital representation of malevolent behavior of restaurant employees. The results of this research could be used to notify restaurant owners in real time when fraud is being committed. This paper applies machine learning (ML) techniques including neural networks, support vector machines, Random Forest, and Adaboost, to detecting insider fraud in restaurant point-of-sales data. By applying undersampling and oversampling class balancing techniques we show that ML techniques can improve fraud detection performance. In particular, detection with a Random Forest model using cross validation can be increased 55% by oversampling the minority class to the same size as the majority class. And results with a Neural Net model trained to detect fraud on the first year the restaurant opened, and tested on data from the following year can be improved by 50% by decreasing the majority class to be the same size as the minority class.

In a typical text mining problem, the distribution of the domain-specific repository data does not fully capture all the problem's concepts in the real-world. This issue, termed inadequacy of knowledge, decreases the accuracy of generated models. One aspect of inadequacy of knowledge is the out-of-vocabulary problem, i.e. when a word does not appear in the repository data. In this paper, the out-of-vocabulary issue in GloVe is addressed by changing the form of fed training data, i.e. the n-grams of each word are substituted for the word. This version of GloVe is called here C-GloVe. It is shown that the accuracy of the generated models by C-GloVe is mostly higher than when GloVe or FastText is used, especially for smaller training sets. Also, the issue of inadequacy of knowledge is addressed by proposing a method to integrate local (i.e. domain specific) and universal sources of knowledge and to combine different word embedding algorithms. Our experimental results on three different tasks show that the proposed methods yield higher performance than a standalone source of knowledge and a standalone word embedding algorithm, especially if one algorithm of the combination is trained on the local source and another on the universal source of knowledge. Also, experimental results on the classification task show that the proposed method obtained the same or higher F1-score than BERT in four out of five classification problems.

This paper addresses the effect of data reduction on speeding up training while keeping or improving the accuracy performance of classification. Since many studies have focused on feature selection, but did not adequately consider instance selection, our work focuses on both instance reduction and feature reduction, integrated into a whole reduction method. We examined in prior work Simple Random Sample Selection without Replacement, integrated with the Information Gain-based Feature Selection method, and compared its performance with the unintegrated instance selection and feature selection alone, using a single reduction rate. Our results proved that the integration of instance and feature selection performed much better than instance or feature selection alone. In this paper, we examine our approach in more depth, trying different reduction rates and different distributions of reduction rates between instance reduction and feature reduction. Our results show that for nearly all common classifiers, our integrated data reduction speeds up training significantly while keeping the accuracy unchanged (and sometimes even improved) at even high reduction rates. We also present the optimal feature-instance reduction-rates tradeoff.

Mathematical formulae are essential in science, but face challenges of ambiguity, due to the use of a small number of identifiers to represent an immense number of concepts. Corresponding to word sense disambiguation in Natural Language Processing, we disambiguate mathematical identifiers. By regarding formulae and natural text as one monolithic information source, we are able to extract the semantics of identifiers in a process we term Mathematical Language Processing (MLP). As scientific communities tend to establish standard (identifier) notations, we use the document domain to infer the actual meaning of an identifier. Therefore, we adapt the software development concept of namespaces to mathematical notation. Thus, we learn namespace definitions by clustering the MLP results and mapping those clusters to subject classification schemata. In addition, this gives fundamental insights into the usage of mathematical notations in science, technology, engineering and mathematics. Our gold standard based evaluation shows that MLP extracts relevant identifier-definitions. Moreover, we discover that identifier namespaces improve the performance of automated identifier-definition extraction, and elevate it to a level that cannot be achieved within the document context alone.

Mathematical Information Retrieval concerns retrieving information related to a particular mathematical concept. The NTCIR-11 Math Task develops an evaluation test collection for document sections retrieval of scientific articles based on human generated topics. Those topics involve a combination of formula patterns and keywords. In addition, the optional Wikipedia Task provides a test collection for retrieval of individual mathematical formula from Wikipedia based on search topics that contain exactly one formula pattern. We developed a framework for automatic query generation and immediate evaluation. This paper discusses our dataset preparation, topic generation and evaluation methods, and summarizes the results of the participants, with a special focus on the Wikipedia Task.

In this paper, we present a novel audio watermarking technique that utilizes the low frequency components (LFCs) of an audio signal to identify the location of the embedded watermarks. The embedding takes place by modifying the amplitude of selected samples determined by the LFCs of the audio signal. The amount of modification to the amplitude is determined by the amount of distortion detected by the human ear. This technique is blind where the decoder does not need the original audio file to extract the watermarks. In this technique, we use a novel data recovery scheme to recover any watermarks that were lost because of an intentional or unintentional attempt of watermark removal (attack). Experimental results show that this technique is highly robust against single and double attacks with watermark recovery rates greater than 90%.

This paper proposes a bit error recovery method for extended 2 dimensional MMR coded bitstreams. When an error occurs in an MMR coded bitstream, the bitstream cannot be decoded correctly after the error point. To prevent losing valid information after an error, we developed an error recovery system that detects bit errors and applies bit-inversion to correct the errors. In case the bit-inversion cannot correct the error, the system applies new algorithms that utilize syntactical structure information of the coded bitstream to recover nearly all the data.

Summary form only given. The goal is to gain a better understanding of the behavior of the image down/upsampling combinations, and find better down/upsampling methods. We examined existing down/upsampling methods and proposed new ones. We formulated a frequency response approach for understanding and evaluating down/upsampling combinations. The approach was validated experimentally by running the methods on various images and computing the signal to noise ratio (SNR) between the original and the down-then-upsampled images. The frequency response based evaluation correlates well with the experimental evaluation. Down/upsampling combinations were studied in a unified framework. Signals are pre-filtered then decimated by two, resulting in downsampling by two. Afterwards, signals are zero-upsampled by 2, i.e., inserting 0s between successive samples, and then post-filtering. Our analysis showed that for optimal performance, the pre-filter and the post-filter should both be low-pass filters with cutoff at /spl pi//2. We considered five classes of filters. The first corresponds to the simplest down/upsampling combination, decimation/duplication, where decimation is simply the skipping of every other row and every other column, and duplication (for upsampling) involves duplicating every row and every column. The second class corresponds to bilinear interpolation, for both upsampling and downsampling. The third class comprises the biorthogonal and orthogonal wavelets. The fourth class we termed binomial filters. The fifth class consists of least-square FIR filters.

Summary form only given. DPCM decoding is essentially the computation of a 2-indexed scalar recurrence relation; the two indices are: the row and column positions of the pixels. Although several logarithmic-time parallel algorithms for solving 1-indexed recurrence relations have been designed, no work has been reported on multi-indexed recurrence relations. Considering the importance of fast DPCM decoding of imagery, parallel algorithms for solving multi-indexed recurrence relations merit serious study. We designed novel parallel algorithms for solving 2-indexed recurrence relations, and identified the parallel architectures best suited for them. We developed three approaches: index sequencing, index decoupling, and dimension shifting. To solve a 2-indexed relation in DPCM decoding of an n/spl times/n image, index sequencing breaks down the relation into a sequence of n 1-indexed scalar recurrence relations that must be solved one after another. Each relation is then solved by a parallel O(nlogn) time algorithm on an n-processor hypercube or partitionable bus. Thus, the n equations take O(nlogn) time on n processors. Index decoupling, applicable in a common case of DPCM, breaks the 2-indexed relation into n independent 1-indexed recurrence relations, which are then solved simultaneously in O(logn) parallel time, using n/sup 2/ processors configured as a hypercube or a mesh of partitionable buses.

Benes networks have the potential for balanced traffic, fewer conflicts, and can route any permutation in one pass due to their multiplicity of paths. Omega networks, on the other hand, have fast set-up and low hardware cost, but could take more than one pass to route a permutation. This paper introduces a new class of networks referred to as r-truncated Benes, which is a Benes network with r randomization stages eliminated. Using randomized routing, we will show that r-truncated Benes networks is an excellent trade-off between Omega and Benes networks. In particular, it will be shown that the I-truncated Benes network out performs Omega and is also superior to Benes and other truncated Benes networks in cost and performance.

The banyan-hypercube (BH) is one of the recently introduced hypercube-based interconnection networks. Due to the importance of communication in the overall system performance in a multiprocessing environment, this paper presents a near-optimal personalized broadcasting algorithm on the BHs. The analysis of this algorithm for both BHs and hypercubes is conducted for both single-port communication and multiple-port communication. We show that personalized broadcasting for both networks have the same communication time in the single-port mode. In multiple-port mode, the performance of the BH depends on its number of levels. When the number of levels is less than 4, the BHs outperform the hypercubes. However, the hypercubes have better performance than the BHs with large number of levels (>4). When the number of levels is equal to 4, both networks have the same performance.

Abstract Circuit‐switched fixed routing (CSFR) is an increasingly popular communication model wherein there is between every source—destination pair a single path that is system‐determined by a fixed‐routing rule. This paper studies the new problem of off‐line permutation scheduling on linear arrays, rings, hypercubes, and 2‐dimensional arrays, assuming the CSFR model. Optimal permutation scheduling involves finding a minimum number of subsets of nonconflicting source—destination paths. Every subset of paths can be established to run in one pass. In this paper, optimal permutation scheduling on linear arrays is shown to be linear, and on rings, NP‐complete. On hypercubes, the problem is NP‐complete. However, we will give an O(N log N) algorithm that routes any permutation in two passes if the model is relaxed to allow for two routing rules, namely, the so‐called e‐cube rule and the e−1‐cube rule. This complexity is reduced to O(N) hypercube‐parallel time. Finally, an O(N log2 N) bipartite‐matching‐based algorithm will be designed to schedule any permutation on p × q meshes/tori in q passes. © 1993 by John Wiley & Sons, Inc.

Random walks are widely applicable in statistical and scientific computations. In particular, they are used in the Monte Carlo method to solve elliptic and parabolic partial differential equations (PDEs). This method holds several advantages over other methods for PDEs as it solves problems with irregular boundaries and/or discontinuities, gives solutions at individual points, and exhibits great parallelism. However, the generation of each random walk in the Monte Carlo method has been done sequentially because each point in the walk is derived from the preceding point by moving one grid step along a randomly selected direction. A parallel algorithm for random walk generation in regular as well as irregular regions is presented. The algorithm is based on parallel prefix computations. The communication structure of the algorithm is shown to ideally fit on a hypercube of n nodes, where n is the number of processors.>

Relations among banyan multistage interconnection networks (MINs) of differing switch sizes are studied. If two N*N networks W and W' have switch sizes r and s, respectively, and if r>s, then W realizes a larger number of permutations than W'. Consequently, the two networks can never be equivalent. However, W may realize all the permutations of W', in which case W is said to functionally cover W' in the strict sense. More generally, W is said to functionally cover W' in the wide sense if the terminals of W can be relabeled so that W realizes all the permutations of W'. Functional covering is topologically characterized, and an optimal algorithm to decide strict functional covering is developed.>

A theoretical study of the connectivity and fault tolerance of Cartesian product networks is presented. The theoretical results are used to synthesize provably correct adaptive fault-tolerant algorithms from ones written for the component networks. The theoretical foundations that relate the connectivity of a Cartesian product network, the connectivity of the component networks, and the number of faulty components are established. It is shown that the connectivity of a product network is at least the sum of the connectivities of its factor networks. Based on the constructive connectivity proof, an adaptive, generic, distributed algorithm that can perform successful point-to-point routing in product networks, in the presence of faults, is devised. A proof of correctness of the algorithm is provided.>

The routing control of Benes networks has proven to be costly. This paper introduces a new approach to fast control of N × N 3-stage Benes networks of r × r crossbar switches as building blocks, where N = r2 and r ≥ 2. The new approach consists of setting the leftmost column of switches to an appropriately chosen configuration so that the network becomes self-routed while still able to realize a given family of permutations. This approach requires that, for any given family of permutations, a configuration for the leftmost column be found. Such a family is called compatible and the configuration of the leftmost column is called the compatibility factor. In this paper, compatibility is characterized and a technique to determine compatibility and the compatibility factor is developed. The technique is used to show the compatibility and find the compatibility factor of Ω-realizable permutations, the permutations needed to emulate a hypercube, and the families of permutations required by FFT, bitonic sorting, tree computations, multidimensional mesh and torus computations, and multigrid computations. An O(log2 N) time routing algorithm for the 3-stage Benes will also be developed. Finally, as only 3 compatibility factors are required by the above families of permutations, it will be proposed to replace the first column by 3 multiplexed connections yielding a self-routing network with strong communication capabilities.

Existing procedures to decide network equivalence in log N-stage banyan networks are based on analysis of permutations, take polynomial but costly time, and do not shed light on or take advantage of the relationship between functionality and topology. This relationship is addressed and it is shown that two log N-stage banyan networks of the same switch size are functionally equivalent if and only if they have the same underlying topology. An O(N log N) algorithm is derived which decides if two N-stage banyan networks of N inputs, N outputs, and r*r crossbar switches as building blocks realize the same permutations. The algorithm works by comparing the underlying topologies of the two networks. The algorithm is optimal because the size of the networks is O(N log N).>

The authors introduce a family of networks that are a synthesis of banyans and hypercubes and are called the banyan-hypercubes (BH). They combine the advantageous features of banyans and hypercubes and thus have better communication capabilities. The networks can be viewed as consisting of interconnecting hypercubes. It is shown that many hypercube features can be incorporated into BHs with regard to routing, embedding of rings and meshes, and partitioning, and that improvements over the hypercube result are made. In particular, it is shown that BHs have better diameters and average distances than hypercubes, and they embed pyramids and multiple pyramids with dilation cost 1. An optimal routing algorithm for BHs and an efficient partitioning strategy are presented.>