On some Properties of Boolean Functions and Their Binary Decision Diagrams

Иво Й. Дамянов - Манипулирането на булеви функции е основнo за теоретичната информатика, в това число логическата оптимизация, валидирането и синтеза на схеми. В тази статия се разглеждат някои първоначални резултати относно връзката между граф-базираното представяне на булевите функции и свойствата на техните променливи.

Designing extended entry decision tables and optimal decision trees using decision diagrams /

Bibliography: p. 52-53.

Using Sensitivity as a Method for Ranking the Test Cases Classified by Binary Decision Trees

Usually, data mining projects that are based on decision trees for classifying test cases will use the probabilities provided by these decision trees for ranking classified test cases. We have a need for a better method for ranking test cases that have already been classified by a binary decision tree because these probabilities are not always accurate and reliable enough. A reason for this is that the probability estimates computed by existing decision tree algorithms are always the same for all the different cases in a particular leaf of the decision tree. This is only one reason why the probability estimates given by decision tree algorithms can not be used as an accurate means of deciding if a test case has been correctly classified. Isabelle Alvarez has proposed a new method that could be used to rank the test cases that were classified by a binary decision tree [Alvarez, 2004]. In this paper we will give the results of a comparison of different ranking methods that are based on the probability estimate, the sensitivity of a particular case or both.

Synchronous versus asynchronous modeling of gene regulatory networks.

MOTIVATION: In silico modeling of gene regulatory networks has gained some momentum recently due to increased interest in analyzing the dynamics of biological systems. This has been further facilitated by the increasing availability of experimental data on gene-gene, protein-protein and gene-protein interactions. The two dynamical properties that are often experimentally testable are perturbations and stable steady states. Although a lot of work has been done on the identification of steady states, not much work has been reported on in silico modeling of cellular differentiation processes. RESULTS: In this manuscript, we provide algorithms based on reduced ordered binary decision diagrams (ROBDDs) for Boolean modeling of gene regulatory networks. Algorithms for synchronous and asynchronous transition models have been proposed and their corresponding computational properties have been analyzed. These algorithms allow users to compute cyclic attractors of large networks that are currently not feasible using existing software. Hereby we provide a framework to analyze the effect of multiple gene perturbation protocols, and their effect on cell differentiation processes. These algorithms were validated on the T-helper model showing the correct steady state identification and Th1-Th2 cellular differentiation process. AVAILABILITY: The software binaries for Windows and Linux platforms can be downloaded from http://si2.epfl.ch/~garg/genysis.html.

Chess endgame news

News that Bourzutschky confirms there is no sub-7-man pawnless zugzwang, and that Bourzutschky and Konoval are generating DTC EGTs with a new program. News also of Kristensen's work on EGTs using OBDDs, Ordered Binary Decision Diagrams.

Persuasion, binary choice, and the costs of dishonesty

We study the strategic interaction between a decision maker who needs to take a binary decision but is uncertain about relevant facts and an informed expert who can send a message to the decision maker but has a preference over the decision.We show that the probability that the expert can persuade the decision maker to take the expert's preferred decision is a hump-shaped function of his costs of sending dishonest messages.

RelMDD-A Library for Manipulating Relations Based on MDDs

Relation algebras is one of the state-of-the-art means used by mathematicians and computer scientists for solving very complex problems. As a result, a computer algebra system for relation algebras called RelView has been developed at Kiel University. RelView works within the standard model of relation algebras. On the other hand, relation algebras do have other models which may have different properties. For example, in the standard model we always have L;L=L (the composition of two (heterogeneous) universal relations yields a universal relation). This is not true in some non-standard models. Therefore, any example in RelView will always satisfy this property even though it is not true in general. On the other hand, it has been shown that every relation algebra with relational sums and subobjects can be seen as matrix algebra similar to the correspondence of binary relations between sets and Boolean matrices. The aim of my research is to develop a new system that works with both standard and non-standard models for arbitrary relations using multiple-valued decision diagrams (MDDs). This system will implement relations as matrix algebras. The proposed structure is a library written in C which can be imported by other languages such as Java or Haskell.

Willingness-to-pay for a probabilistic flood forecast: a risk-based decision-making game

Probabilistic hydro-meteorological forecasts have over the last decades been used more frequently to communicate forecastuncertainty. This uncertainty is twofold, as it constitutes both an added value and a challenge for the forecaster and the user of the forecasts. Many authors have demonstrated the added (economic) value of probabilistic over deterministic forecasts across the water sector (e.g. flood protection, hydroelectric power management and navigation). However, the richness of the information is also a source of challenges for operational uses, due partially to the difficulty to transform the probability of occurrence of an event into a binary decision. This paper presents the results of a risk-based decision-making game on the topic of flood protection mitigation, called “How much are you prepared to pay for a forecast?”. The game was played at several workshops in 2015, which were attended by operational forecasters and academics working in the field of hydrometeorology. The aim of this game was to better understand the role of probabilistic forecasts in decision-making processes and their perceived value by decision-makers. Based on the participants’ willingness-to-pay for a forecast, the results of the game show that the value (or the usefulness) of a forecast depends on several factors, including the way users perceive the quality of their forecasts and link it to the perception of their own performances as decision-makers.

Multiclass Adaboost Based on an Ensemble of Binary Adaboosts

This paper presents a multi-class AdaBoost based on incorporating an ensemble of binary AdaBoosts which is organized as Binary Decision Tree (BDT). It is proved that binary AdaBoost is extremely successful in producing accurate classification but it does not perform very well for multi-class problems. To avoid this performance degradation, the multi-class problem is divided into a number of binary problems and binary AdaBoost classifiers are invoked to solve these classification problems. This approach is tested with a dataset consisting of 6500 binary images of traffic signs. Haar-like features of these images are computed and the multi-class AdaBoost classifier is invoked to classify them. A classification rate of 96.7% and 95.7% is achieved for the traffic sign boarders and pictograms, respectively. The proposed approach is also evaluated using a number of standard datasets such as Iris, Wine, Yeast, etc. The performance of the proposed BDT classifier is quite high as compared with the state of the art and it converges very fast to a solution which indicates it as a reliable classifier.

The study of insect blood-feeding behaviour: 2. Recording techniques and the use of flow charts

This paper continues a discussion of approaches and methodologies we have used in our studies of feeding in haematophagous insects. Described are techniques for directly monitoring behaviour: electrical recording of feeding behaviour via resistance changes in the food canal, optical methods for monitoring mouthpart activity, and a computer technique for behavioural event recording. Also described is the use of "flow charts" or "decision diagrams" to model interrelated sequences of behaviours.

Dynamic simulation of regulatory networks using SQUAD.

BACKGROUND: The ambition of most molecular biologists is the understanding of the intricate network of molecular interactions that control biological systems. As scientists uncover the components and the connectivity of these networks, it becomes possible to study their dynamical behavior as a whole and discover what is the specific role of each of their components. Since the behavior of a network is by no means intuitive, it becomes necessary to use computational models to understand its behavior and to be able to make predictions about it. Unfortunately, most current computational models describe small networks due to the scarcity of kinetic data available. To overcome this problem, we previously published a methodology to convert a signaling network into a dynamical system, even in the total absence of kinetic information. In this paper we present a software implementation of such methodology. RESULTS: We developed SQUAD, a software for the dynamic simulation of signaling networks using the standardized qualitative dynamical systems approach. SQUAD converts the network into a discrete dynamical system, and it uses a binary decision diagram algorithm to identify all the steady states of the system. Then, the software creates a continuous dynamical system and localizes its steady states which are located near the steady states of the discrete system. The software permits to make simulations on the continuous system, allowing for the modification of several parameters. Importantly, SQUAD includes a framework for perturbing networks in a manner similar to what is performed in experimental laboratory protocols, for example by activating receptors or knocking out molecular components. Using this software we have been able to successfully reproduce the behavior of the regulatory network implicated in T-helper cell differentiation. CONCLUSION: The simulation of regulatory networks aims at predicting the behavior of a whole system when subject to stimuli, such as drugs, or determine the role of specific components within the network. The predictions can then be used to interpret and/or drive laboratory experiments. SQUAD provides a user-friendly graphical interface, accessible to both computational and experimental biologists for the fast qualitative simulation of large regulatory networks for which kinetic data is not necessarily available.

Päätöspuun käyttö tutkamaalien initialisoinnissa

Suomen ilmatilaa valvotaan reaaliaikaisesti, pääasiassa ilmavalvontatutkilla. Ilmatilassa on lentokoneiden lisäksi paljon muitakin kohteita, jotka tutka havaitsee. Tutka lähettää nämä tiedot edelleen ilmavalvontajärjestelmään. Ilmavalvontajärjestelmä käsittelee tiedot, sekä lähettää ne edelleen esitysjärjestelmään. Esitysjärjestelmässä tiedot esitetään synteettisinä merkkeinä, seurantoina joista käytetään nimitystä träkki. Näiden tietojen puitteissa sekä oman ammattitaitonsa perusteella ihmiset tekevät päätöksiä. Tämän työn tarkoituksena on tutkia tutkan havaintoja träkkien initialisointipisteessä siten, että voitaisiin määritellä tyypillinen rakenne sille mikä on oikea ja mikä väärä tai huono träkki. Tämän lisäksi tulisi ennustaa, mitkä Irakeista eivät aiheudu ilma- aluksista. Saadut tulokset voivat helpottaa työtä havaintojen tulkinnassa - jokainen lintuparvi ei ole ehdokas seurannaksi. Havaintojen luokittelu voidaan tehdä joko neurolaskennalla tai päätöspuulla. Neurolaskenta tehdään neuroverkoilla, jotka koostuvat neuroneista. Päätöspuu- luokittelijat ovat oppivia tietorakenteita kuten neuroverkotkin. Yleisin päätöpuu on binääripuu. Tämän työn tavoitteena on opettaa päätöspuuluokittelija havaintojen avulla siten, että se pystyy luokittelemaan väärät havainnot oikeista. Neurolaskennan mahdollisuuksia tässä työssä ei käsitellä kuin teoreettisesti. Työn tuloksena voi todeta, että päätöspuuluokittelijat ovat erittäin kykeneviä erottamaan oikeat havainnot vääristä. Vaikka tulokset olivat rohkaiseva, lisää tutkimusta tarvitaan määrittelemään luotettavammin tekijät, jotka parhaiten suorittavat luokittelun.

Lagrangian validation of numerical drifter trajectories using drifting buoys: Application to the Agulhas system

The skill of numerical Lagrangian drifter trajectories in three numerical models is assessed by comparing these numerically obtained paths to the trajectories of drifting buoys in the real ocean. The skill assessment is performed using the two-sample Kolmogorov–Smirnov statistical test. To demonstrate the assessment procedure, it is applied to three different models of the Agulhas region. The test can either be performed using crossing positions of one-dimensional sections in order to test model performance in specific locations, or using the total two-dimensional data set of trajectories. The test yields four quantities: a binary decision of model skill, a confidence level which can be used as a measure of goodness-of-fit of the model, a test statistic which can be used to determine the sensitivity of the confidence level, and cumulative distribution functions that aid in the qualitative analysis. The ordering of models by their confidence levels is the same as the ordering based on the qualitative analysis, which suggests that the method is suited for model validation. Only one of the three models, a 1/10° two-way nested regional ocean model, might have skill in the Agulhas region. The other two models, a 1/2° global model and a 1/8° assimilative model, might have skill only on some sections in the region

A novel shape feature for fast region-based pedestrian recognition

A new class of shape features for region classification and high-level recognition is introduced. The novel Randomised Region Ray (RRR) features can be used to train binary decision trees for object category classification using an abstract representation of the scene. In particular we address the problem of human detection using an over segmented input image. We therefore do not rely on pixel values for training, instead we design and train specialised classifiers on the sparse set of semantic regions which compose the image. Thanks to the abstract nature of the input, the trained classifier has the potential to be fast and applicable to extreme imagery conditions. We demonstrate and evaluate its performance in people detection using a pedestrian dataset.