Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

Relation-algebraic semantics

The first half is a tutorial on orderings, lattices, Boolean algebras, operators on Boolean algebras, Tarski's fixed point theorem, and relation algebras.

In the second half, elements of a complete relation algebra are used as “meanings” for program statements. The use of relation algebras for this purpose was pioneered by de Bakker and de Roever in [10–12]. For a class of programming languages with program schemes, single μ-recursion, while-statements, if-then-else, sequential composition, and nondeterministic choice, a definition of “correct interpretation” is given which properly reflects the intuitive (or operational) meanings of the program constructs. A correct interpretation includes for each program statement an element serving as “input/output relation” and a domain element specifying that statement's “domain of nontermination”. The derivative of Hitchcock and Park [17] is defined and a relation-algebraic version of the extension by de Bakker [8, 9] of the Hitchcock-Park theorem is proved. The predicate transformers wp_s(-) and wlp_s(-) are defined and shown to obey all the standard laws in [15]. The “law of the excluded miracle” is shown to hold for an entire language if it holds for that language's basic statements (assignment statements and so on). Determinism is defined and characterized for all the program constructs. A relation-algebraic version of the invariance theorem for while-statements is given. An alternative definition of intepretation, called “demonic”, is obtained by using “demonic union” in place of ordinary union, and “demonic composition” in place of ordinary relational composition. Such interpretations are shown to arise naturally from a special class of correct interpretations, and to obey the laws of wp_s(-).     

On the almost-sure sample stability of systems with randomly time-varying delays

In a large class of multi-loop control systems, many feedback loops are “closed” through a time-shared digital computer, by means of algorithms which require information from sources which are sampled at a rate which is not synchronized with the sampling of the individual “plants”. This mis-synchronization, coupled with variations in the computer's task load caused by “interrupts”, results in a randomly time-varying delay in the closing of the various feedback loops. Consequently, the dynamics of each controlled “plant” in such a system may be modeled by means of a stochastic delay-differential equation. This paper presents some new research results concerning the sample stability, as opposed to statistical, or ensemble stability, of linear stochastic delay-differential equations.     

Comfort evaluation of hearing protection

Hearing protection is very important for workers in noisy work environments, although the willingness of workers to wear hearing protectors depends heavily on their comfort. This paper evaluates and recommends improvements for the comfort of hearing protection. Workers’ experience and comfort needs for hearing protection were investigated through a questionnaire that established the “comfort indices” for hearing protection. An earmuff “comfort tester” was designed to measure the comfort indices, and an experiment was conducted to measure workers’ perceived comfort into quantitative data. From the data, the range of these comfort indices in which workers will feel comfortable was determined. Finally, guidelines to improve the design of current hearing protection based on these “comfort indices” are proposed, which may help increase workers’ willingness to wear hearing protection.

Relevance to industry

Using these proposed guidelines may help improve the comfort of hearing protection and increase workers’ willingness to wear hearing protection in noisy work environments.     

Visual surveillance using deformable models of vehicles

This paper presents recent developments to a vision-based traffic surveillance system which relies extensively on the use of geometrical and scene context. Firstly, a highly parametrised 3-D model is reported, able to adopt the shape of a wide variety of different classes of vehicle (e.g. cars, vans, buses etc.), and its subsequent specialisation to a generic car class which accounts for commonly encountered types of car (including saloon, batchback and estate cars). Sample data collected from video images, by means of an interactive tool, have been subjected to principal component analysis (PCA) to define a deformable model having 6 degrees of freedom.

Secondly, a new pose refinement technique using “active” models is described, able to recover both the pose of a rigid object, and the structure of a deformable model; an assessment of its performance is examined in comparison with previously reported “passive” model-based techniques in the context of traffic surveillance. The new method is more stable, and requires fewer iterations, especially when the number of free parameters increases, but shows somewhat poorer convergence.

Typical applications for this work include robot surveillance and navigation tasks.     

Retrieval of movie scenes by semantic matrix and automatic feature weight update

A new semantic-based video scene retrieval method is proposed in this paper. Twelve low-level features extracted from a video clip are represented in a genetic chromosome and target videos that user has in mind are retrieved by the interactive genetic algorithm through the feedback iteration. In this procedure, high-level semantic relevance between retrieved videos is accumulated with so-called semantic relevance matrix and semantic frequency matrix for each iteration, and they are combined with an automatic feature weight update scheme to retrieve more target videos at the next iteration. Experiments over 300 movie scene clips extracted from latest well-known movies, showed an user satisfaction of 0.71 at the fourth iteration for eight queries such as “gloominess”, “happiness”, “quietness”, “action”, “conversation”, “explosion”, “war”, and “car chase”.     

Optimal control of demand-paging systems

Demand-paging systems are characterized as stochastic control processes, and optimal page replacement decisions are determined by means of dynamic programming. This approach is distinguished from others by its utilization of page structure information, which may be either supplied a priori or else dynamically learned. The main result is an optimal realizable solution for a general class of replacement problems. The resulting algorithm subsumes others (including “A₀”) as special cases.     

Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation

The computation of the greatest common divisor (GCD) of many polynomials is a nongeneric problem. Techniques defining “approximate GCD” solutions have been defined, but the proper definition of the “approximate” GCD, and the way we can measure the strength of the approximation has remained open. This paper uses recent results on the representation of the GCD of many polynomials, in terms of factorisation of generalised resultants, to define the notion of “approximate GCD” and define the strength of any given approximation by solving an optimisation problem. The newly established framework is used to evaluate the performance of alternative procedures which have been used for defining approximate GCDs.     

On the large deviations approximation for the stationary distribution of skip-free regulated queueing networks

Large deviations papers like that of Ignatyuk et al. [Russ. Math. Surv. 49 (1994) 41–99] have shown that asymptotically, the stationary distribution of homogeneous regulated networks is of the form

with the coefficient being different in various “boundary influence domains” and also depending on some of these domains on n. In this paper, we focus on the case of constant exponents and on a subclass of networks we call “strongly skip-free” (which includes all Jackson and all two-dimensional skip-free networks). We conjecture that an asymptotic exponent is constant iff it corresponds to a large deviations escape path which progresses gradually (from the origin to the interior) through boundary facets whose dimension always increases by one. Solving the corresponding large deviations problem for our subclass of networks leads to a family of “local large deviation systems” (LLDSs) (for the constant exponents), which are expressed entirely in terms of the cumulant generating function of the network. In this paper, we show that at least for “strongly skip-free” Markovian networks with independent transition processes, the LLDS is closely related to some “local boundary equilibrium systems” (LESs) obtained by retaining from the equilibrium equations only those valid in neighborhoods of the boundary.

Since asymptotic results require typically only that the cumulant generating function is well-defined over an appropriate domain, it is natural to conjecture that these LLDSs will provide the asymptotic constant exponents regardless of any distributional assumptions made on the network.

Finally, we outline a practical recipe for combining the local approximations to produce a global large deviations approximation , with the coefficients K_j determined numerically.     

Optimizing agent-based meeting scheduling through preference estimation

Meeting scheduling is a routine task that needs to be performed quite regularly and frequently within any organization. Unfortunately, this task can be quite tedious and time-consuming, potentially requiring a several rounds of negotiations among many people on the meeting date, time and place before a meeting can finally be confirmed. The objective of our research is to create an agent-based environment within which meeting scheduling can be performed and optimized. For meeting scheduling, we define optimality as the solution that has the highest average preference level among all the possible choices. Our model tries to mimic real life in that an individual's preferences are not made public. Without complete information, traditional optimal algorithms, such as A^* will not work. In this paper, we present a novel “preference estimation” technique that allows us to find optimal solutions to negotiations problems without needing to know the exact preference models of all the meeting participants beforehand. Instead, their preferences are “estimated” and built on the fly based on observations of their responses during negotiation. Another unique contribution is the use of “preference rules” that allow preferences to change dynamical as scheduling decisions are made. This mimics changing preferences as schedule gets filled. This paper uses two negotiation algorithms to compare the effect of “preference estimation”—one that is based on negotiation through relaxation and the other that extends this with preference estimations. Simulations were then performed to compare these algorithms.     

Aggregation of a class of interconnected, linear dynamical systems

In this paper, we introduce the notion of a “meaningful” average of a collection of dynamical systems as distinct from an “ensemble” average. Such a notion is useful for the study of a variety of dynamical systems such as traffic flow, power systems, and econometric systems. We also address the associated issue of the existence and computation of such an average for a class of interconnected, linear, time invariant dynamical systems. Such an “average” dynamical system is not only attractive from a computational perspective, but also represents the average behavior of the interconnected dynamical systems. The problem of analysis and control of heirarchical, large scale control systems can be simplified by approximating the lower level dynamics of such systems with such an average dynamical system.     

General structure and characteristics of quick response production system

The diversification and shorter production cycles urge manufacturers to shift their production systems from “make to stock” to “make to order” or an intermediate production system between them. The present paper deals with a production system developed by some manufacturers to meet requirements in the last decade. The system, which we call “Quick response to orders production system” or in brief “quick response production system (QRPS)”, is characterized by two key factors, i.e., “acceptable response time” and “semifinished product.” An acceptable response time is decided through the explicit or implicit approval of customers beforehand and manufacturers guarantee to ship products within an acceptable response time in a stochastic sense by processing the semifinished product according to customer order. As a result, manufacturers are able to reduce the inventory of finished products, while customers are able to enjoy the diversification of products and a stable supply from manufacturers. The general structure and characteristics of QRPS are discussed primarily from a quantitative point of view and a numerical example is shown to assist in understanding the design and operation of QRPS.     

Sensors and interfacing in robotics and manufacturing

Sensing is one of the most essential aspects of any robotic application, be it manufacturing or any automated process. Robotic sensors can be divided into two classes of “internal” and “external”. Examples of the first group are position or velocity, while the second group includes proximity, touch, or vision to name a few. The other important problem in manufacturing is interfacing with the environment within a cell. The object of this tutorial paper is to survey the two issues of “sensing” and “interfacing” in robotics and manufacturing.     

Efficient combinator code

Some combinatory logics are examined as object code for functional programs. The worst-case performances of certain algorithms for abstracting variables from combinatory expressions are analysed. A lower bound on the performance of any abstraction algorithm for a finite set of combinators is given. Using the combinators S, K, I, B, C, S′, B′, C′ and Y, the problem of finding an optimal abstraction algorithm is shown to be NP-complete. Some methods of improving abstraction algorithms for those combinators are examined, including “balancing” (for asymptotic performance) and “peephole” optimisations (for smaller cases).     

A fuzzy substroke extractor for handwritten Chinese characters

This paper incorporates fuzzy technique into handwritten Chinese character substroke extraction. By computing a fuzzy score for every possible substroke, feature loss is reduced without imposing unnecessary restrictions on the writing style. Our extractor is as good as existing crisp substroke extractors in unambiguous situations, and it outperforms them in ambiguous cases in terms of the number of desirable substrokes extracted. Comparing with the “explore-every-possibility” approach based on crisp decision, we arrive at the correct feature set in a smaller number of iterations. The extractor's performance could also be tuned via a number of system parameters.     

Color enhancement of highly correlated images. I. Decorrelation and HSI contrast stretches

Conventional enhancements for the color display of multispectral images are based on independent contrast modifications or “stretches” of three input images. This approach is not effective if the image channels are highly correlated or if the image histograms are strongly bimodal or more complex. Any of several procedures that tend to “stretch” color saturation while leaving hue unchanged may better utilize the full range of colors for the display of image information. Two conceptually different enhancements are discussed: the “decorrelation stretch”, based on principal-component (PC) analysis, and the “stretch” of “hue”-“saturation”-intensity (HSI) transformed data. The PC transformation is scene-dependent, but the HSI transformation is invariant. Examples of images enhanced by conventional linear stretches, decorrelation stretch, and by stretches of HSI transformed data are compared. Schematic variation diagrams or two- and three-dimensional histograms are used to illustrate the “decorrelation stretch” method and the effect of the different enhancements.     

What a histogram can really tell the classifier

This paper presents a simple and efficient clustering technique based on the partitioning of the data histogram. The clustering technique was developed in the context of a study of possible unsupervized classification procedures for multispectral earth imagery. The ultimate goal was on-board data compression, the algorithmic production of thematic maps.

The incoming raw spectral data is first reduced to its two principal (Karhunen-Loêve) components, the histogram of which is then partitioned into natural classes on the sole weight of evidence of the global statistics of the imagery. During the course of the study, it became clear that some connection existed between the proposed philosophy and professor Thom's novel theory of “catastrophes”.⁽¹⁾ A simple metric is added to the histogram topology. The metric uses both Shannon's and Fisher's notions of self information. In the domain of definition of the histogram, zones corresponding to the natural classes become separated by a no man's land, an inter-class zone. Under the same formulation, the metric is “Euclidean” on the class zone, “non-Euclidean”, i.e. “Lorentz” on the inter-class zone. This methodology and the underlying philosophy were tested in practice, and encouraging results were obtained.     

“Chaotic relaxation” in concurrently asynchronous neural networks

In this paper we analyze a fundamental issue which directly impacts the scalability of current theoretical neural network models to applicative embodiments, in both software as well as hardware. This pertains to the inherent and unavoidable concurrent asynchronicity of emerging fine-grained computational ensembles and the consequent chaotic manifestations in the absence of proper conditioning. The latter concern is particularly significant since the computational inertia of neural networks in general and our dynamical learning formalisms manifests itself substantially, only in massively parallel hardward—optical, VLSI or opto-electronic. We introduce a mathematical framework for systematically reconditioning additive-type models and derive a neuro-operator, based on the chaotic relaxation paradigm whose resulting dynamics are neither “concurrently” synchronous nor “sequentially” asynchronous. Necessary and sufficient conditions guaranteeing concurrent asynchronous convergence are established in terms of contracting operators. Lyapunov exponents are also computed to characterize the network dynamics and to ensure that throughput-limiting “emergent computational chaos” behavior in models reconditioned with concurrently asynchronous algorithms was eliminated.     

Generalized boundary conditions on the basis of a deformable-cell method: Free surfaces, density interfaces and open boundaries

In the numerical analysis of flows, we need to treat various types of boundary conditions; in particular, in the fields of oceanophysics or hydraulics, “free surface”, “density interface” and “open boundary” have been considered difficult to treat. On the basis of a deformable-cell method, the cells dividing the fluid can be deformed in accordance with the moving boundaries, as in the arbitrary-Lagrangian-Eulerian method, and these boundary conditions are systematically treated with a “generalized boundary equation”. The validity of this method is shown by a flow with a free surface, a density interface and an open boundary.     

A structure for expert systems maintenance

An approach to the design of maintainable expert systems is presented. Central to this approach is a conceptual model in which the data and knowledge are both modelled as formal “items” in a uniform way. “Objects” are introduced as “item building” operators. The notion of the “decomposition” of items and objects provides the foundation for a single rule of normalization. This single rule applies to all items and objects, including knowledge items, and is a non-trivial generalization of the traditional normal forms for database. Coupling relationships represent the necessary maintenance paths in the conceptual model. A complete characterization of coupling relationships is given, and the value of normalization to the reduction of maintenance costs is discussed.