Wyniki wyszukiwania - BazTech

1

FPGA implementation of logarithmic versions of Baum-Welch and Viterbi algorithms for reduced precision hidden Markov models

Pietras M., Klęsk P.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2017

|

Vol. 65, nr 6

935--946

EN

This paper presents a programmable system-on-chip implementation to be used for acceleration of computations within hidden Markov models. The high level synthesis (HLS) and “divide-and-conquer” approaches are presented for parallelization of Baum-Welch and Viterbi algorithms. To avoid arithmetic underflows, all computations are performed within the logarithmic space. Additionally, in order to carry out computations efficiently – i.e. directly in an FPGA system or a processor cache – we postulate to reduce the floating-point representations of HMMs. We state and prove a lemma about the length of numerically unsafe sequences for such reduced precision models. Finally, special attention is devoted to the design of a multiple logarithm and exponent approximation unit (MLEAU). Using associative mapping, this unit allows for simultaneous conversions of multiple values and thereby compensates for computational efforts of logarithmic-space operations. Design evaluation reveals absolute stall delay occurring by multiple hardware conversions to logarithms and to exponents, and furthermore the experiments evaluation reveals HMMs computation boundaries related to their probabilities and floating-point representation. The performance differences at each stage of computation are summarized in performance comparison between hardware acceleration using MLEAU and typical software implementation on an ARM or Intel processor.

2

Graph search approach to rectangle packing problem

Korzeń M., Klęsk P.

Journal of Applied Computer Science

|

2015

|

Vol. 23, nr 1

47--62

EN

A rectangle packing problem is considered, where the goal is to suitably arrange a subset of given rectangles within a container so that the area of wastes (uncovered spaces) is the smallest. We propose a reduction of this problem to a graph search problem and show possible solving approaches by means of well known BFS, Dijkstra’s and A* algorithms. We explain the way we construct search graphs for the problem, taking under consideration two main variants: (1) with arbitrary straight-line cuts, (2) with straight-line cuts which must go along the whole length or width of the remaining container — ‘full cuts’. We also give some insights on: optimization criterion, search stopping condition and heuristics we use. Finally, we present results of experiments carried out.

3

Child well being estimation as a multi-criteria decision problem

Adamus E., Klęsk P., Kołodziejczyk J., Korzeń M., Piegat A., Pluciński M.

Metody Informatyki Stosowanej

|

2011

|

nr 4

279-286

EN

The aim of the article is to establish a list of capabilities with reference to children’s well being in Poland. This issue can be considered as a multicriterial classification problem where decision attributes classes are ordered due to the preference – criteria. We used a Dominance-based Rough Set Approach (DRSA) adapted to deal with missing values. Analysis was performed on data set collected in Zachodniopomorskie district as a result of survey conduction.

4

Rules induction on child well being

Adamus E., Klęsk P., Kołodziejczyk J., Korzeń M., Piegat A., Pluciński M.

Metody Informatyki Stosowanej

|

2010

|

nr 4 (24)

5-10

EN

The aim of this research was to induct rules from a dataset obtained through a survey on child well-being that was performed in Poland Western Pomarania. For rule induction the exhaustive algorithm was used. The assessment of the strengths of found rules can be carried out and expressed in terms of: the conditional entropy and the Kullback-Leibler's number. Resulting rules are elements of a Pareto optimal set of derived rules, which are 'sensible' and 'interesting', Each rule combines thefunctionings (activities during childhood) and subjective evaluation of childhood.

5

A comparison of certain generalization bounds of learning machines for practical applications

Klęsk P.

Metody Informatyki Stosowanej

|

2010

|

nr 4 (24)

35-45

EN

In statisticallearning bounds on generalization error and sample complexities are important elements. In the paper we compare several selected generalization bounds having in mind their practical applications. In particular; we state twa theorems which compare bounds derived via additive and multiplicative versions of Chemoff inequality. In experimental part we show (using a benchmark data set) how one can practically apply bounds and sample complexity.

6

Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks

Klęsk P.

International Journal of Applied Mathematics and Computer Science

|

2010

|

Vol. 20, no 3

525-544

EN

Two known approaches to complexity selection are taken under consideration: n-fold cross-validation and structural risk minimization. Obviously, in either approach, a discrepancy between the indicated optimal complexity (indicated as the minimum of a generalization error estimate or a bound) and the genuine minimum of unknown true risks is possible. In the paper, this problem is posed in a novel quantitative way. We state and prove theorems demonstrating how one can calculate pessimistic probabilities of discrepancy between these minima for given for given conditions of an experiment. The probabilities are calculated in terms of all relevant constants: the sample size, the number of cross-validation folds, the capacity of the set of approximating functions and bounds on this set. We report experiments carried out to validate the results.

7

Passive operating system fingerprinting using neural networks and induction of decision rules

Bielski B., Klęsk P.

Metody Informatyki Stosowanej

|

2008

|

nr 4 (Tom 17)

15--25

EN

One of the most difficult task for people managing big- or even medium-size computer network is determining the accurate number of hosts that are protected. This information is really helpful for accurately configuring network-based devices such as intrusion detection systems. Exact knowledge of the operating systems (residing in hosts) can be useful for excluding many alerts that cannot apply to a remote operating system that is being examined. In this context, we consider a classification problem (we try to recognize the class of operating system) when some of the characteristics of the system are modified by its user or any other program (e.g. for internet connection tuning). We use neural networks (MLP, RBF) and rule induction techniques. It should be stressed that existing fingerprinting tools get high accuracy results when tested on the “clean” versions of operating systems, but they fail to detect systems with modified TCP/IP parameters.

8

O Ukrytych Modelach Markowa i ich zastosowaniu do rozpoznawania ciągów znaków pisma odręcznego

Klęsk P.

Metody Informatyki Stosowanej

|

2008

|

nr 1 (Tom 13)

175-189

EN

In the paper, selected informations on Hidden Markov Models (also called Hidden Markov Chains) are reminded. Basic riotions are defined and algorithms related to these models are shortly presented. The research part of the papers shows results of three conducted experiments entitled: "pork cutlet", "form sheet" and ''poetaster". The most important experiment "form sheet" gives a good starting point to a practical application of HMMs to the. handwriting recognition. The "poetaster" experiment shows possible application of HMMs in so called "artifial creation".

9

Mining interesting rules and patterns for salt sensitivity of blood pressure

Korzeń M., Klęsk P., Ciechanowicz A., Kaczmarczyk M., Widecka K., Jaroszewicz S.

Metody Informatyki Stosowanej

|

2008

|

nr 3 (Tom 16)

149--157

EN

Given a medical data set containing genetic description of sodium-sensitive and nonsensitive patients, we examine it using several techniques: induction of decision rules, naive Bayes classifier, voting perceptron classifier, decision trees, SVM classifier. We specifically focus on induction of decision rules and so called Pareto-optimal rules, which are of large interpretative value for physicians. We find statistically relevant combinations of attributes, which affect the sodium sensitivity.