A computer program to estimate the parameters of covariate dependent higher order Markov model

This paper presents a computer program developed in S-plus to estimate the parameters of covariate dependent higher order Markov Chain and related tests. The program can be applied for two states Markov Chain with any order and any number of covariates depending on the PC capabilities. The program provides the maximum likelihood estimates of the parameters, together with their estimated standard error, t-value and significance level. It also produces the test results for likelihood ratio and model chi-square. To illustrate the program we have used a longitudinal data set on maternal morbidity of rural women in Bangladesh. The occurrences of haemorrhage, convulsion, or fits at different follow-ups were used as outcome variable. Economic status, wanted pregnancy, ages at marriage, and education of women were used as covariates.     

Topological models for boundary representation: a comparison with n-dimensional generalized maps

In boundary representation, a geometric object is represented by the union of a ‘topological’ model, which describes the topology of the modelled object, and an ‘embedding’ model, which describes the embedding of the object, for instance in three-dimensional Euclidean space. In recent years, numerous topological models have been developed for boundary representation, and there have been important developments with respect to dimension and orientability. In the main, two types of topological models can be distinguished. ‘Incidence graphs’ are graphs or hypergraphs, where the nodes generally represent the cells of the modelled subdivision (vertex, edge, face, etc.), and the edges represent the adjacency and incidence relations between these cells. ‘Ordered’ models use a single type of basic element (more or less explicitly defined), on which ‘element functions’ act; the cells of the modelled subdivision are implicitly defined in this type of model. In this paper some of the most representative ordered topological models are compared using the concepts of the n-dimensional generalized map and the n-dimensional map. The main result is that ordered topological models are (roughly speaking) equivalent with respect to the class of objects which can be modelled (i.e. with respect to dimension and orientability).     

Optic flow segmentation as an ill-posed and maximum likelihood problem

It is shown how the segmentation problem encountered in the interpretation of visual motion, for example, may be formulated as an ill-posed problem using the notion of maximum likelihood to provide a general framework and guide the choice of regularizing constraints. The statistical consequences of the segmentation procedure proposed are examined and it is shown how the notion of maximum likelihood leads to a natural way of estimating parameters in the optimization function, especially the noise levels to be assigned. A minimum entropy regularization constraint is then used to ensure that the interpretation of the visual data elicits as much spatial structure as possible. It is shown by means of a ‘toy’ optic flow example how this is achieved when there are several parameter dimensions over which to segment.     

Neural networks deterioration models for serviceability condition of buried stormwater pipes

Buried stormwater pipe networks play a key role in surface drainage systems for urban areas of Australia. The pipe networks are designed to convey water from rainfall and surface runoff only and do not transport sewage. The deterioration of stormwater pipes is commonly graded into structural and serviceability condition using CCTV inspection data in order to recognize two different deterioration processes and consequences. This study investigated the application of neural networks modelling (NNM) in predicting serviceability deterioration that is associated with reductions of pipe diameter until a complete blockage. The outcomes of the NNM are predictive serviceability condition for individual pipes, which is essential for planning proactive maintenance programs, and ranking of pipe factors that potentially contribute to the serviceability deterioration. In this study the Bayesian weight estimation using Markov Chain Monte Carlo simulation was used for calibrating the NNM on a case study in order to account for the uncertainty often encountered in NNM's calibration using conventional back-propagation weight estimation. The performance and the ranked factors obtained from the NNM were also compared against a classical model using multiple discrimination analysis (MDA). The results showed that the predictive performance of the NNM using Bayesian weight estimation is better than that of the NNM using conventional backpropagation and MDA model. Furthermore, among nine input factors, ‘pipe age’ and ‘location’ appeared insignificant whilst ‘pipe size’, ‘slope’, ‘the number of trees’ and ‘climatic condition’ were found consistently important over both models for serviceability deterioration process. The remaining three factors namely, ‘structure’, ‘soil’ and ‘buried depth’ might be redundant factors. A better and more consistent data collection regime may help to improve the predictive performance of the NNM and identify the significant factors.     

On the complexity of ω-type Turing acceptors

Turing machines are considered as recognizers of sets of infinite (ω-type) sequences, so called ω-languages. The basic results on such ω-type Turing acceptors were presented in a preceding paper. This paper focuses on the theory of deterministic ω-type Turing acceptors (ω-DTA's) which turns out to be crucially different from the ‘classical’ theory of Turing machines. It is shown that there exists no ω-DTA which is universal for all ω-DTA's. Two infinite complexity hierarchies for ω-DTA's are established, the ‘states hierarchy’, corresponding to the number of states in the machine, and the ‘designated sets hierarchy’, corresponding to the number of designated sets of states used in the recognition. Concrete examples of ω-languages characterizing each of the complexity classes are exhibited. Two additional examples of interesting ω-languages are presented:

1. (i) An ω-language which is ‘inherently non-deterministic’, i.e. can be recognized by a non-deterministic Turing acceptor but by no deterministic acceptor.

2. (ii) An ω-language which cannot be recognized even by a non-deterministic Turing acceptor.

The above examples are constructed without using diagonalization. Oscillating ω-DTA's, i.e. ω-DTA's which are allowed to oscillate on ω-inputs, are also considered and are shown to be strictly more powerful than non-oscillating ω-DTA's, yet strictly less powerful than non-deterministic ω-Turing acceptors.     

The living in a lattice rule language

This paper presents a rule-based query language for an object-oriented database model. The database model supports complex objects, object identity, classes and types, and a class/type hierarchy. The instances are described by ‘object relations’ which are functions from a set of objects to value sets and other object sets. The rule language is based on object-terms which provide access to objects via the class hierarchy. Rules are divided into two classes: object-preserving rules manipulating existing objects (yielding a new ‘view’ on objects available in the object base) and object-generating rules creating new objects with properties derived from existing objects. The derived object sets are included in a class lattice. We give conditions for whether the instances of the ‘rules’ heads are ‘consistent’, i.e. represent object relations where the properties of the derived objects are functionally determined by the objects.     

Comparing shared and distributed memory computers

There are two distinct types of MIMD (Multiple Instruction, Multiple Data) computers: the shared memory machine, e.g. Butterfly, and the distributed memory machine, e.g. Hypercubes, Transputer arrays. Typically these utilize different programming models: the shared memory machine has monitors, semaphores and fetch-and-add; whereas the distributed memory machine uses message passing. Moreover there are two popular types of operating systems: a multi-tasking, asynchronous operating system and a crystalline, loosely synchronous operating system.

In this paper I firstly describe the Butterfly, Hypercube and Transputer array MIMD computers, and review monitors, semaphores, fetch-and-add and message passing; then I explain the two types of operating systems and give examples of how they are implemented on these MIMD computers. Next I discuss the advantages and disadvantages of shared memory machines with monitors, semaphores and fetch-and-add, compared to distributed memory machines using message passing, answering questions such as “is one model ‘easier’ to program than the other?” and “which is ‘more efficient‘?”. One may think that a shared memory machine with monitors, semaphores and fetch-and-add is simpler to program and runs faster than a distributed memory machine using message passing but we shall see that this is not necessarily the case. Finally I briefly discuss which type of operating system to use and on which type of computer. This of course depends on the algorithm one wishes to compute.     

An approach towards the design of intelligent man-machine interfaces used in process control

This paper is related to improvements carried out n the field of human-machine communication in complex industrial processes, using the concept of the ‘intelligent’ interface. Following a review of literature on this subject, an ‘intelligent’ interface design based on ergonomical concepts is described. Finally, we present our approach to the design of an ‘intelligent’ interface. The Decisional Module of Imagery (D.M.I.) as it is called, is based on two models: a task model and a user model. The D.M.I.'s structure and its integration in an experimental platform are described in the last part of this paper.     

SAS macro program for non-homogeneous Markov process in modeling multi-state disease progression

Writing a computer program for modeling multi-state disease process for cancer or chronic disease is often an arduous and time-consuming task. We have developed a SAS macro program for estimating the transition parameters in such models using SAS IML. The program is very flexible and enables the user to specify homogeneous and non-homogeneous (i.e. Weibull distribution, log-logistic, etc.) Markov models, incorporate covariates using the proportional hazards form, derive transition probabilities, formulate the likelihood function, and calculate the maximum likelihood estimate (MLE) and 95% confidence interval within a SAS subroutine. The program was successfully applied to an example of a three-state disease model for the progression of colorectal cancer from normal (disease free), to adenoma (pre-invasive disease), and finally to invasive carcinoma, with or without adjusting for covariates. This macro program can be generalized to other k-state models with s covariates.     

Fast Riccati equation solutions: Partitioned algorithms

In this paper, using the ‘partitioning’ approach to estimation, exceptionally robust and fast computational algorithms for the effective solution of continuous Riccati equations are presented. The algorithms have essentially a decomposed or ‘partitioned’ structure which is both theoretically interesting as well as computationally attractive. Specifically, the ‘partitioned’ solution is given exactly in terms of a set of elemental solutions which are both simple as well as completely decoupled from each other, and as such computable in either a parallel or serial processing mode. Moreover, the overall solution is given by a simple recursive operation of the elemental solution. Extensive computer simulation has shown that the ‘partitioned’ algorithm is numerically very effective and robust, especially in the case of ill-conditioned Riccati solutions, e.g. for ill-conditioned initial conditions, or for stiff system matrices. Further, the ‘partitioned’ algorithm is very fast, ranging up to several orders of magnitude faster than the corresponding Runge-Kutta algorithm.     

A simulation method for time-dependent structural reliability

A one-dimensional simulation procedure is developed for use in estimating structural reliability in multi-dimensional load and resistance space with the loads represented as stochastic process. The technique employed is based on the idea of using ‘strips’ of points parallel to each other and sampled on the limit state hyperplanes. The ‘local’ outcrossing rate and the zero time failure probability P_f(0) associated with the narrow strips are derived using the conditional reliability index. When the domain boundary consists of a set of limit states, second order bounds are used to obtain a lower bound approximation of the outcrossing rate and P_f(0) associated with the union of a set of λ strips. It is shown by examples that for high reliability problems, λ may be much less than the number of limit states without significant loss of accuracy and with considerable saving in computation time. It was also found that the rate of convergence of the simulations is quite fast even without using importance sampling.     

The constituents of business interaction––generic layered patterns

In order to perform business modelling as apart of information systems development, there is a need for frameworks and methods. The paper proposes a framework for business interaction based on a language/action perspective. The framework is an architecture of five generic layers. The first layer concept is ‘business act’, which functions as the basic unit of analysis. The following four layer concepts are ‘action pair’, ‘exchange’, ‘business transaction’, and ‘transaction group’. The framework is inspired by a similar framework constructed by Weigand et al. The paper makes a critical examination of this framework as a basis for the proposed framework.     

Token swap test revisited

The token swap test measures the association between row and column variables of a 2×2 table in sample misclassification space, and makes no assumptions about repeated, random sampling from a source population. Despite its conceptual usefulness, the token swap test is not implemented by standard statistical software packages. Here the author describes ‘tokenSwaps’, a Mathematica program that performs a token swap test. The ‘tokenSwaps’ program also performs a one-tailed Fisher exact test, allowing results of the two methods to be compared. The program uses recursive functional programming and local rewrite rules to achieve substantial coding economy. Examples of the operation of the program are given, and its limitations are discussed.     

Real-time integrated model for visual perception and fuzzy control

Current state-of-the-art security systems incorporate ‘passive’ and/or ‘human’ elements, the effectiveness of which can only be measured by their ability to ‘deter’ intruders. However, rapidly changing economic and cultural conditions have weakened the strengths associated with such systems. In the not too distant future, the need for an ‘active’ security system will become necessary in order to reduce the onslaught of crime.

This paper presents a conceptual basis for the incorporation of artificial intelligence concepts in the design and implementation of ‘active’ security systems. Specifically, the paper discusses issues pertaining to a real-time model for visual perception and tracking of possible intruders.     

Bioequivalence revisited: non-parametric analysis of two-period cross-over studies

Hauschke et al.'s non-parametric bioequivalence procedure for treatment effects and some aspects of computer implementation, among them Meineke and De Hey's algorithm, are explored. For studies with up to sixty subjects, a table of indices of the ranked intersubject-intergroup mean ratios or differences is given, to establish non-parametric 90% confidence intervals. It is shown that non-parametric analysis is not limited to treatment effects: it can also be applied to period and sequence effects. This extended procedure can be seen as the non-parametric analogue of analysis of variance on two-period cross-over studies. A FORTRAN program (BIOQNEW) incorporating Meineke and De Mey's algorithm is presented. This program provides non-parametric point estimates for treatment and period effects, 90% and 95% confidence intervals for test-versus-reference treatments, the 95% confidence interval for periods and a test on sequence effects, so that it can also be used for other than bioequivalence studies. BIOEQNEW can handle ratios (‘multiplicative model’) as well as differences (‘additive model’). It optionally provides the complete non-parametric posterior probability distribution for treatment ratios or differences, so that Schuirmann's ‘two one-sided tests procedure’ can also be performed in a non-parametric way.     

Comparison of several discrete arithmetic schemes for simulating a constrained jet and a lab-scale tangential fired furnace

For tangential fired furnace, the false diffusion will occur when the flow is oblique to the grid lines. It is a major factor to cause serious errors to the prediction of tangential fired furnace. In order to decrease this false diffusion, this study has considered several alternative to the widely used upwind-differencing scheme with the aim of identifying which could be regarded as the most suitable in a general-purpose solving procedure for tangential furnace. The representations adopted are ‘hybrid’, ‘quick’ and ‘27-point’ treatments. Here, ‘27-point’ is a new discrete arithmetic scheme developed by the authors. All these schemes are used to simulate a constrained jet and a lab-scale tangential furnace and to compare solutions with the datum. Overall, the ‘27-point’ approximation emerged as the most satisfactory for simulating tangential furnace.     

HCI ‘Intraface Model’ for System Design

We outline an alternative model of the interface in HCI, the ‘intraface’, in response to design issues arising from navigational and learning problems in hypertext domains. Ours is a model of general application to computer systems. It is composed of four key elements, identifiable within a dynamic interconnected context. These are the user; his/her interests; the tools employed and the ‘ensemble’ of representations brought to bear. In this paper we sketch the present shortcomings of HCI design before outlining the background for the model which draws upon two themes in contemporary psychology, conversational analysis and ‘affordance’ realist theories in perception. This framework allows for the development of principles of cooperation, user engagement and learning in HCI environments.     

Defining a taxonomy of output modalities from an HCI perspective

The paper addresses an issue that must be resolved to produce a scientifically sound and practically useful reference model for intelligent multimedia presentation systems (IMP systems), namely that of providing, from the point of view of Human-Computer Interaction (HCI), a systematic understanding of the types of output information to be presented by IMP systems. The term ‘medium’, as it is used in the context of multimedia systems, is too coarse-grained for distinguishing between different types of output information. The paper introduces the notion of (representational) ‘modalities’ to enable sufficiently fine-grained distinctions to be made. For the term itself to be meaningful, ‘multimodal’ presentations must be composed of unimodal representations. In the approach presented, unimodal representations are defined from a small number of basic properties whose combinations specify the ‘generic’ level of a taxonomy of unimodal output modalities. Additional basic property distinctions serve to generate the more fine-grained ‘atomic’ and ‘sub-atomic’ levels in a hierarchical fashion. The taxonomy is set up with the aim of satisfying four basic requirements, viz. completeness, orthogonality, relevance and intuitiveness. A concluding discussion illustrates the practical use of the taxonomy.     

On uncertainty versus size in branching programs

We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. The uncertainty is measured by the average depth of so-called ‘splitting trees’ for sets of inputs reaching particular nodes of the program.

We first demonstrate the approach for read-once branching programs. Then, we introduce a strictly larger class of so-called ‘balanced’ branching programs and, using the suggested approach, prove that some explicit Boolean functions cannot be computed by balanced programs of polynomial size. These lower bounds are new since some explicit functions, which are known to be hard for most previously considered restricted classes of branching programs, can be easily computed by balanced branching programs of polynomial size.     

Boundary matching algorithm for connected component labelling using linear quadtrees

A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2ⁿ × 2ⁿ. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.