Search

Bayesian inference is one of the main problems in statistics.It aims to update the prior knowledge of the probability distribution model based on the observation data.For the posterior probability that cannot be observed or is difficult to directly calculate,which is often encountered in real situations,Bayesian inference can obtain a good approximation.It is a kind of important method based on Bayesian theorem.Many machine learning problems involve the process of simulating and approximating the target distribution of various types of feature data,such as classification models,topic modeling,and data mining.Therefore,Bayesian inference has shown important and unique research value in the field of machine learning.With the beginning of the big data era,the experimental data collected by researchers through actual information is very large,resulting in the complex distribution of targets to be simulated and calculated.How to perform accurate and time-efficient approximation inferences on target distributions under complex data has become a major and difficult point in Bayesian inference problems today.Aiming at the infe-rence problem under this complex distribution model,this paper systematically introduces and summarizes the two main methods for solving Bayesian inference problems in recent years,which are variational inference and sampling methods.Firsly,this paper gives the problem definition and theoretical knowledge of variational inference,introduces in detail the variational inference algorithm based on coordinate ascent,and gives the existing applications and future prospects of this method.Next,it reviews the research results of existing sampling methods at home and abroad,gives the specific algorithm procedure of various main sampling methods,as well as summarizes and compares the characteristics,advantages and disadvantages of these methods.Finally,this paper introduces parallel tempering technique,outlines its basic theories and methods,discusses the combination and application of parallel tempering and sampling methods,and explores new research directions for the future development of Bayesian inference problems.

In this work, we propose AirNN, a novel framework which enables dynamic approximation of an already-trained convolutional neural network (CNN) in hardware during inference. AirNN enables input-dependent approximation of the CNN to achieve energy saving without much degradation in its classification accuracy at runtime. For each input, AirNN uses only a fraction of the CNN’s weights based on that input (with the rest remaining 0) to conduct the inference. Consequently, energy saving is possible due to fewer number of fetches from off-chip memory as well as fewer multiplications for majority of the inputs. To achieve per-input approximation, we propose a clustering algorithm that groups similar weights in the CNN based on their importance, and design an iterative framework that decides dynamically how many clusters of weights should be fetched from off-chip memory for each individual input. We also propose new hardware structures to implement our framework on top of a recently proposed FPGA-based CNN accelerator. In our experiments with popular CNNs, we, on average, show 49% energy saving with less than 3% degradation in classification accuracy due to doing inference with only a fraction of the weights for the majority of the inputs. We also propose a greedy interleaving scheme, implemented in hardware, in order to improve the performance of the iterative procedure and compensate for its latency overhead. [ABSTRACT FROM AUTHOR]

Conventionally, decimation-in-time (DIT) data-flow-graph (DFG) is used to obtain computing structures for discrete Hadamard transform (DHT). The fixed-width structures based on conventional approach, however, offers a marginal bit-saving and introduces relatively more truncation error. In this paper, we have derived decimation-in-frequency (DIF) DFG for DHT which is more convenient for approximation using truncation than the DIT-DFG. To achieve higher bit-saving with relatively less truncation error, we propose an efficient truncation model comprising of pre-truncation ($\delta $) and post-truncation ($\gamma $). Also, we present a logic optimized adder-subtractor design customized for DHT structure. Using the proposed truncation model, we have three variants of proposed structures for parallel computation of 2D DHT. The proposed structure-2 for DHT size $N=8$ , word-size $w=8$ , and approximation $(\delta _{1}=2, \gamma _{1}=1, \delta _{2}=2, \gamma _{2}=1)$ involves nearly 38% less area-delay-product (ADP) and 46% less energy per sample (EPS), and calculates outputs with almost the same accuracy as the existing fixed-width structure based on post-truncation. For the same word-size and $N=16$ , the proposed structure-2 for approximation $(\delta _{1}=2, \gamma _{1}=2, \delta _{2}=2, \gamma _{2}=2)$ involves nearly 36% less ADP and 44% less EPS than the existing structure and calculates outputs with the same accuracy. We have observed that reconstructed images obtained using the proposed structure-2 are less by 7 dB and 2 dB PSNR than those obtained using the existing fixed-width structures for $N=8$ and 16, respectively. [ABSTRACT FROM AUTHOR]

Coding schemes are presented that provide the ability to locate computational errors above a prescribed threshold while using analog resistive devices for approximate real vector–matrix multiplication. In such devices, the matrix is programmed into the device by setting an array of resistors to have conductances proportional to the respective entries in the matrix. In the coding scheme that is considered in this work, redundancy columns are appended so that each row in the programmed matrix forms a codeword of a prescribed linear code ${\mathcal {C}}$ over the real field; the result of the multiplication of any input real row vector by the matrix is then also a codeword of ${\mathcal {C}}$. While error values within $\pm \delta $ in the entries of the result are tolerable (for some prescribed $\delta > 0$), outlying errors, with values outside the range $\pm \Delta $ (for a prescribed $\Delta \ge \delta $) should be located and corrected. As a design and analysis tool for such a setting, a certain functional is defined for the code ${\mathcal {C}}$ , through which a characterization is obtained for the number of outlying errors that can be handled, as a function of the ratio $\Delta /\delta $. Several code constructions are then presented, primarily for the case of single outlying error handling. For this case, the coding problem is shown to be related to certain extremal problems on convex polygons. [ABSTRACT FROM AUTHOR]

Parallel distributed arithmetic (PDA)-based structures are widely used for high-speed computation of inner product in digital signal processing (DSP) applications. In this article, we have proposed novel PDA-based structures based on an efficient truncation model. To achieve higher bit saving with relatively less truncation error, we present here a novel approach using approximate look-up tables (LUTs), adder trees (ATs), and Wallace-like shift-AT (SAT) with truncated operands to obtain hardware-efficient fixed-width PDA-based inner-product structures. We have three variants of proposed structures based on the proposed truncation approach. We find that the proposed inner-product structure-1 using approximate LUT (ALUT) and approximate AT offers nearly 20% higher bit saving, 20% saving in area-delay product (ADP) and offers relatively less truncation error than the existing structures. The proposed structure-2 using ALUT, ATs, and proposed SAT offers nearly 50% higher bit-saving, 61% ADP saving and offers nearly the same accuracy compared to the existing approximate DA-based structures. Proposed structure-3 offers nearly 60% higher bit saving and calculates outputs with almost the same or marginally less accuracy than the existing structures for higher coefficient word lengths. [ABSTRACT FROM AUTHOR]

In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library. [ABSTRACT FROM AUTHOR]

Highlights • A differential-relation-based rough set model on relational databases is proposed. • Using this model, the measures for differential dependencies (DDs) are expressed. • An efficient method to compute the approximate error measure of g 3 for DDs is developed. • The rough sets on the differential decision systems (DDSs) are introduced. • A bridge between DDs in databases and attribute dependencies in DDSs is formed. Abstract Data dependencies in databases and attribute dependencies in decision systems are important when addressing problems concerning data quality and attribute reduction, in which measures play a significant role in approximating these dependencies to achieve better adaptation to uncertain data. This paper proposes a differential-relation-based rough set model from the perspective of relational databases to express the dependency degree, error measures, confidence, information granulation and differential class distance for differential dependencies (DDs) and the relationships among them in a unified framework. Moreover, the error measure g 3 has been widely studied and applied for data dependencies. However, the computation of g 3 for DDs is NP-complete. Therefore, based on the proposed rough set, we introduce a new method that can compute the approximate error measure g 3 ˜ of g 3 in polynomial time. This study demonstrates that our approach can provide a substantially better approximation, that is, an approximation closer to the optimal solution g 3 , compared to the existing greedy method. We also introduce the differential-relation-based rough set from the perspective of information systems and make a connection to the rough sets induced by non-equivalence relations. The two views of the differential-relation-based rough sets form an essential bridge between the DDs in databases and attribute dependencies in differential decision systems (DDSs) that allows sharing measures for approximating the dependencies. These results are meaningful for approximate computations, the development of algorithms for attribute reduction in decision systems and the discovery of approximate differential dependencies (ADDs) in databases. [ABSTRACT FROM AUTHOR]

Internet of Things devices, such as video-based detectors or road side units are being deployed in emerging applications like sustainable and intelligent transportation systems. Oftentimes, stringent operation and energy cost constraints are exerted on this type of applications, necessitating a hybrid supply of renewable and grid energy. The key issue of a cost-constrained hybrid of renewable and grid power is its uncertainty in energy availability. The characteristic of approximate computation that accepts an approximate result when energy is limited and executes more computations yielding better results if more energy is available, can be exploited to intelligently handle the uncertainty. In this paper, we first propose an energy-adaptive task allocation scheme that optimally assigns real-time approximate-computation tasks to individual processors and subsequently enables a matching of the cost-constrained hybrid supply of energy with the energy demand of the resultant task schedule. We then present a quality of service (QoS)-driven task scheduling scheme that determines the optional execution cycles of tasks on individual processors for optimization of system QoS. A dynamic task scheduling scheme is also designed to adapt at runtime the task execution to the varying amount of the available energy. Simulation results show that our schemes can reduce system energy consumption by up to 29% and improve system QoS by up to 108% as compared to benchmarking algorithms. [ABSTRACT FROM AUTHOR]

This paper presents a heterogeneous microprocessor for low-energy sensor-inference applications. Hardware acceleration has shown to enable substantial energy-efficiency and throughput gains, but raises significant challenges where programmable computations are required, as in the case of feature extraction. To overcome this, a programmable feature-extraction accelerator (FEA) is presented that exploits genetic programming for automatic program synthesis. This leads to approximate, but highly structured, computations, enabling: 1) a high degree of specialization; 2) systematic mapping of programs to the accelerator; and 3) energy scalability via user-controllable approximation knobs. A microprocessor integrating a CPU with feature-extraction and classification accelerators is prototyped in 130-nm CMOS. Two medical-sensor applications (electroencephalogram-based seizure detection and electrocardiogram-based arrhythmia detection) demonstrate 325 $\times $ and 156 $\times $ energy reduction, respectively, for programmable feature extraction implemented on the accelerator versus a CPU-only architecture, and 7.6 $\times $ and 6.5 $\times $ energy reduction, respectively, versus a CPU-with-coprocessor architecture. Furthermore, 20 $\times $ and 9 $\times $ energy scalability, respectively, is demonstrated via the approximation knobs. The energy-efficiency of the programmable FEA is 220 GOPS/W, near that of fixed-function accelerators in the same technology, exceeding typical programmable accelerators. [ABSTRACT FROM AUTHOR]

Fixed-width multipliers are intensively used in many DSP applications whose accuracy and energy efficiency affect the whole digital system to a large extent. To improve the computation accuracy, a Booth-encoded sign-digit-based conditional probability estimation approach is proposed. A symmetric error distribution is obtained by taking the sign bit of the Booth-encoded multiplier into consideration when applying the conditional probability. In addition, a more generalized mux-based estimation method is formulated for the circuit implementation, which reduces the delay time and power dissipation. Simulation results show that the proposed multiplier exhibits the best computation accuracy with the least energy per operation. It performs even better for those operand lengths that are not multiples of 4. The maximum reduction on energy-delay-error product can reach 14.8% compared with all its contenders among various operand lengths. [ABSTRACT FROM AUTHOR]

Progressive Visual Analytics aims at improving the interactivity in existing analytics techniques by means of visualization as well as interaction with intermediate results. One key method for data analysis is dimensionality reduction, for example, to produce 2D embeddings that can be visualized and analyzed efficiently. t-Distributed Stochastic Neighbor Embedding (tSNE) is a well-suited technique for the visualization of high-dimensional data. tSNE can create meaningful intermediate results but suffers from a slow initialization that constrains its application in Progressive Visual Analytics. We introduce a controllable tSNE approximation (A-tSNE), which trades off speed and accuracy, to enable interactive data exploration. We offer real-time visualization techniques, including a density-based solution and a Magic Lens to inspect the degree of approximation. With this feedback, the user can decide on local refinements and steer the approximation level during the analysis. We demonstrate our technique with several datasets, in a real-world research scenario and for the real-time analysis of high-dimensional streams to illustrate its effectiveness for interactive data analysis. [ABSTRACT FROM AUTHOR]

With the rapid development of the Internet of Things (IoTs), wireless sensor networks (WSNs) and related techniques, the amount of sensory data manifests an explosive growth. In some applications of IoTs and WSNs, the size of sensory data has already exceeded several petabytes annually, which brings too many troubles and challenges for the data collection, which is a primary operation in IoTs and WSNs. Since the exact data collection is not affordable for many WSN and IoT systems due to the limitations on bandwidth and energy, many approximate data collection algorithms have been proposed in the last decade. This survey reviews the state of the art of approximate data collection algorithms. We classify them into three categories: the model-based ones, the compressive sensing based ones, and the query-driven ones. For each category of algorithms, the advantages and disadvantages are elaborated, some challenges and unsolved problems are pointed out, and the research prospects are forecasted. [ABSTRACT FROM AUTHOR]

The main goal of the present paper is to furnish practical procedures for the approximate computation (with preassigned precision) of the Sugeno integral of a general positive measurable function with respect to a general monotone measure. To this end, we use our two-steps methods (the simple two-steps method and the topologic method using the iterated convergence theorem). The aforementioned methods reduce the general computation to the well-known computation in the finite discrete case, which can be done with computer-aided methods. [ABSTRACT FROM AUTHOR]

In this paper, an approximate 16-bit non-linear Tanh function circuit design is proposed for activation function in neural networks and digital signal processing, which is based on piecewise linear calculation. By sacrificing acceptable accuracy in computation, the proposed logic circuit structure can furtherly improve the overall performance of the design, with marked reduction in delay, area and power consumption. Linear calculation segments with simple shift-and-add logic architectures are adopted for easy hardware implementation. Additionally, tailored bias tuning and approximate accumulator design make a fine balance between complexity and error distribution. The mean absolute error (MAE) of the entire design is 0.0049. Compared with other state-of-art works in 90 nm CMOS process, the area of the circuit is 582 μ m 2 , and the energy is 0.0996 mW/GHz at 0.71 GHz. Moreover, the area-delay product is reduced by over 79.7% and the energy-delay product is reduced by over 42.4%. In the evaluation of its suitability in large applications, the accurate Tanh circuit and the proposed Tanh circuit are adopted in two neural networks to classify the Fashion-MNIST data and emotional EEG data. When the model converges, the accuracies of the test set only differs with a maximum of 0.2% and 0.3%. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of the problem of counting the locally maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain { 0 , 1 } . A satisfying assignment is locally maximal if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Γ, # LocalMaxCSP ( Γ ) denotes the problem of counting the locally maximal satisfying assignments, given an input CSP with constraints in Γ. We give a complexity dichotomy for the problem of exactly counting the locally maximal satisfying assignments and a complexity trichotomy for the problem of approximately counting them. Relative to the problem # CSP ( Γ ) , which is the problem of counting all satisfying assignments, the locally maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting locally maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets. [ABSTRACT FROM AUTHOR]

Approximate computing is an emerging technique that can be used for developing power, area and delay efficient circuits at the cost of loss of accuracy. This paper investigates the possibility of efficient exact multipliers through the use of improved compressors and counters and thereafter deriving approximate multiplier structures to achieve a higher percentage of logic optimization at the expense of the lowest possible error. NAND gate based array structure with reduced complexity is used for generating the partial products for both the exact and approximate multipliers. Two variants of the efficient exact multiplier are proposed. The proposed exact multiplier EM-1 is area and power efficient, whereas EM-2 is delay and energy efficient. Two variants of 4:2 compressors are introduced for developing approximate multipliers. The proposed multipliers excel most of the state-of-the-art existing multipliers in terms of the important performance metrics. The proposed exact and approximate multiplier designs are employed for developing ECG denoising FIR filter for the elimination of power line interference and the corresponding performance improvement is illustrated. Cadence RTL compiler v11.10 with GPDK 45 nm standard cell library is used for the synthesis. The simulation of all the multipliers is done by running a test bench program using modelsim. [ABSTRACT FROM AUTHOR]

This paper proposes the use of binary trees for representing and managing the potentials involved in Influence Diagrams. This kind of tree allows representing context-specific independencies that are finer-grained compared to those encoded using other representations. This enhanced capability can be used to improve the efficiency of the inference algorithms used for Influence Diagrams. Moreover, binary trees allow computing approximate solutions when exact inference is not feasible. In this work we describe how binary trees can be used to perform this approximate evaluation and we compare them with other structures present in the literature. [ABSTRACT FROM AUTHOR]

Nowadays, graph analytics are widely used in many research fields and applications. One important analytic that measures the influence of each vertex on flows through the network, is the betweenness centrality. It is used to analyze real-world networks like for example social networks and networks in computational biology. Unfortunately this centrality metric is rather expensive to compute and there is a number of studies devoted to approximate it. Here we focus on approximating the computation of betweenness centrality for dynamically changing graphs. We present a novel approach based on graph coarsening for approximating values of betweenness centrality, when new edges are inserted. Unlike other approaches, we reduce the cost (but not complexity) of the betweenness centrality computation step by working on a coarser graph. Our approach demonstrates more than 60% speedup compared to the exact recalculation of the betweenness centrality for dynamically changing graphs. [ABSTRACT FROM AUTHOR]

An approximate method for calculating Nash equilibrium points in a two-person game is developed. [ABSTRACT FROM AUTHOR]

Convolution and cross-correlation are the basis of filtering and pattern or template matching in multimedia signal processing. We propose two throughput scaling options for any one-dimensional convolution kernel in programmable processors by adjusting the imprecision (distortion) of computation. Our approach is based on scalar quantization, followed by two forms of tight packing in floating-point (one of which is proposed in this paper) that allow for concurrent calculation of multiple results. We illustrate how our approach can operate as an optional pre- and post-processing layer for off-the-shelf optimized convolution routines. This is useful for multimedia applications that are tolerant to processing imprecision and for cases where the input signals are inherently noisy (error tolerant multimedia applications). Indicative experimental results with a digital music matching system and an MPEG-7 audio descriptor system demonstrate that the proposed approach offers up to 175% increase in processing throughput against optimized (full-precision) convolution with virtually no effect in the accuracy of the results. Based on marginal statistics of the input data, it is also shown how the throughput and distortion can be adjusted per input block of samples under constraints on the signal-to-noise ratio against the full-precision convolution. [ABSTRACT FROM PUBLISHER]

Abstract: We consider the following computational problem: given a family of generic univariate polynomials , construct an algorithm to find polynomial perturbations with “small” degrees such that the greater common divisor of the family of polynomials has a “large” degree. In this paper, we propose an algorithm which solves this problem in polynomial time under a generic condition generalizing the normal degree sequence for the case . [Copyright &y& Elsevier]

Abstract: We consider the following computational problem: we are given two coprime univariate polynomials and over a ring and want to find whether after a small perturbation we can achieve a large . We solve this problem in polynomial time for two notions of “large” (and “small”): large degree (when is an arbitrary field, in the generic case when and have a so-called normal degree sequence), and large height (when ). Our work adds to the existing notions of “approximate gcd”. [Copyright &y& Elsevier]

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves solving the single-source shortest-paths (SSSP) problem from every node. Therefore, exact computation is infeasible for many large networks of interest today. Centrality scores can be estimated, however, from a limited number of SSSP computations. We present results from an experimental study of the quality of such estimates under various selection strategies for the source vertices. [ABSTRACT FROM AUTHOR]

Computation of the sign of the determinant of a matrix and the determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these problems when the input is an n×n matrix A with integer entries. We study the bit-complexities of the algorithms asymptotically in n and the norm of A. Existing approaches rely on numerical approximate computations, on exact computations, or on both types of arithmetic in combination. [Copyright &y& Elsevier]