Higher-Order Functions for Parsing

In combinator parsing, the text of parsers resembles BNF notation. We present the basic method, and a number of extensions. We address the special problems presented by white-space, and parsers with separate lexical and syntactic phases. In particular, a combining form for handling the offside rule is given. Other extensions to the basic method include an $quot;into$quot; combining form with many useful applications, and a simple means by which combinator parsers can produce more informative error messages.

Robust image hash functions using higher order spectra

Robust hashing is an emerging field that can be used to hash certain data types in applications unsuitable for traditional cryptographic hashing methods. Traditional hashing functions have been used extensively for data/message integrity, data/message authentication, efficient file identification and password verification. These applications are possible because the hashing process is compressive, allowing for efficient comparisons in the hash domain but non-invertible meaning hashes can be used without revealing the original data. These techniques were developed with deterministic (non-changing) inputs such as files and passwords. For such data types a 1-bit or one character change can be significant, as a result the hashing process is sensitive to any change in the input. Unfortunately, there are certain applications where input data are not perfectly deterministic and minor changes cannot be avoided. Digital images and biometric features are two types of data where such changes exist but do not alter the meaning or appearance of the input. For such data types cryptographic hash functions cannot be usefully applied. In light of this, robust hashing has been developed as an alternative to cryptographic hashing and is designed to be robust to minor changes in the input. Although similar in name, robust hashing is fundamentally different from cryptographic hashing. Current robust hashing techniques are not based on cryptographic methods, but instead on pattern recognition techniques. Modern robust hashing algorithms consist of feature extraction followed by a randomization stage that introduces non-invertibility and compression, followed by quantization and binary encoding to produce a binary hash output. In order to preserve robustness of the extracted features, most randomization methods are linear and this is detrimental to the security aspects required of hash functions. Furthermore, the quantization and encoding stages used to binarize real-valued features requires the learning of appropriate quantization thresholds. How these thresholds are learnt has an important effect on hashing accuracy and the mere presence of such thresholds are a source of information leakage that can reduce hashing security. This dissertation outlines a systematic investigation of the quantization and encoding stages of robust hash functions. While existing literature has focused on the importance of quantization scheme, this research is the first to emphasise the importance of the quantizer training on both hashing accuracy and hashing security. The quantizer training process is presented in a statistical framework which allows a theoretical analysis of the effects of quantizer training on hashing performance. This is experimentally verified using a number of baseline robust image hashing algorithms over a large database of real world images. This dissertation also proposes a new randomization method for robust image hashing based on Higher Order Spectra (HOS) and Radon projections. The method is non-linear and this is an essential requirement for non-invertibility. The method is also designed to produce features more suited for quantization and encoding. The system can operate without the need for quantizer training, is more easily encoded and displays improved hashing performance when compared to existing robust image hashing algorithms. The dissertation also shows how the HOS method can be adapted to work with biometric features obtained from 2D and 3D face images.

Higher order universal one-way hash functions from the subset sum assumption

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log m). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’ k+1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

Higher order derivatives and norms of certain matrix functions

Tese de doutoramento, Matemática (Álgebra Lógica e Fundamentos), Universidade de Lisboa, Faculdade de Ciências, 2014

Pattern recognition using invariants defined from higher order spectra : 2-D image inputs

A new algorithm for extracting features from images for object recognition is described. The algorithm uses higher order spectra to provide desirable invariance properties, to provide noise immunity, and to incorporate nonlinearity into the feature extraction procedure thereby allowing the use of simple classifiers. An image can be reduced to a set of 1D functions via the Radon transform, or alternatively, the Fourier transform of each 1D projection can be obtained from a radial slice of the 2D Fourier transform of the image according to the Fourier slice theorem. A triple product of Fourier coefficients, referred to as the deterministic bispectrum, is computed for each 1D function and is integrated along radial lines in bifrequency space. Phases of the integrated bispectra are shown to be translation- and scale-invariant. Rotation invariance is achieved by a regrouping of these invariants at a constant radius followed by a second stage of invariant extraction. Rotation invariance is thus converted to translation invariance in the second step. Results using synthetic and actual images show that isolated, compact clusters are formed in feature space. These clusters are linearly separable, indicating that the nonlinearity required in the mapping from the input space to the classification space is incorporated well into the feature extraction stage. The use of higher order spectra results in good noise immunity, as verified with synthetic and real images. Classification of images using the higher order spectra-based algorithm compares favorably to classification using the method of moment invariants

An investigation of higher-order multi-objective optimisation for 3D aerodynamic shape design

We investigate the performance of different variants of a suitably tailored Tabu Search optimisation algorithm on a higher-order design problem. We consider four objective func- tions to describe the performance of a compressor stator row, subject to a number of equality and inequality constraints. The same design problem has been previously in- vestigated through single-, bi- and three-objective optimisation studies. However, in this study we explore the capabilities of enhanced variants of our Multi-objective Tabu Search (MOTS) optimisation algorithm in the context of detailed 3D aerodynamic shape design. It is shown that with these enhancements to the local search of the MOTS algorithm we can achieve a rapid exploration of complicated design spaces, but there is a trade-off be- tween speed and the quality of the trade-off surface found. Rapidly explored design spaces reveal the extremes of the objective functions, but the compromise optimum areas are not very well explored. However, there are ways to adapt the behaviour of the optimiser and maintain both a very efficient rate of progress towards the global optimum Pareto front and a healthy number of design configurations lying on the trade-off surface and exploring the compromise optimum regions. These compromise solutions almost always represent the best qualitative balance between the objectives under consideration. Such enhancements to the effectiveness of design space exploration make engineering design optimisation with multiple objectives and robustness criteria ever more practicable and attractive for modern advanced engineering design. Finally, new research questions are addressed that highlight the trade-offs between intelligence in optimisation algorithms and acquisition of qualita- tive information through computational engineering design processes that reveal patterns and relations between design parameters and objective functions, but also speed versus optimum quality. © 2012 AIAA.

Higher-order moments in the theory of diversifying and portfolio composition

This paper examines the role of higher-order moments in portfolio choice within an expected-utility framework. We consider two-, three-, four- and five-parameter density functions for portfolio returns and derive exact conditions under which investors would all be optimally plungers rather than diversifiers. Through comparative statics we show the importance of higher-order risk preference properties, such as riskiness, prudence and temperance, in determining plunging behaviour. Empirical estimates for the S&P500 provide evidence for the optimality of diversification.

Higher order turän inequalities

The celebrated Turân inequalities P 2 n(x)-P n-x(x)P n+1(x) ≥ 0, x ε[-1,1], n ≥ 1, where P n(x) denotes the Legendre polynomial of degree n, are extended to inequalities for sums of products of four classical orthogonal polynomials. The proof is based on an extension of the inequalities γ 2 n - γ n-1γ n+1 ≥ 0, n ≥ 1, which hold for the Maclaurin coefficients of the real entire function ψ in the Laguerre-Pölya class, ψ(x) = ∑ ∞ n=0 γ nx n / n!. ©1998 American Mathematical Society.

Higher Visual Functions in the Upper and Lower Visual Fields: a pilot study in healthy subjects

Visual perception is not identical in the upper and lower visual hemifields. The mechanisms behind this difference can be found at the retinal, cortical, or higher attentional level. In this study, a new visual test battery, that involves real-time comparisons of complex visual stimuli, such as shape of objects, and speed of moving dot patterns, in the upper and lower visual hemifields, is presented. This study represents, to our knowledge, the first to implement such a visual test battery in an immersive environment composed of a hemisphere, in order to present visual stimuli in precise regions of the visual field. Ten healthy volunteers were tested in this pilot study. The results showed a higher accuracy in the image matching when the visual test was performed in the lower visual hemifield.

Higher order elicitability and Osband’s principle

A statistical functional, such as the mean or the median, is called elicitable if there is a scoring function or loss function such that the correct forecast of the functional is the unique minimizer of the expected score. Such scoring functions are called strictly consistent for the functional. The elicitability of a functional opens the possibility to compare competing forecasts and to rank them in terms of their realized scores. In this paper, we explore the notion of elicitability for multi-dimensional functionals and give both necessary and sufficient conditions for strictly consistent scoring functions. We cover the case of functionals with elicitable components, but we also show that one-dimensional functionals that are not elicitable can be a component of a higher order elicitable functional. In the case of the variance, this is a known result. However, an important result of this paper is that spectral risk measures with a spectral measure with finite support are jointly elicitable if one adds the “correct” quantiles. A direct consequence of applied interest is that the pair (Value at Risk, Expected Shortfall) is jointly elicitable under mild conditions that are usually fulfilled in risk management applications.

Pure higher-order effects in the portfolio choice model

This paper examines the effects of higher-order risk attitudes and statistical moments on the optimal allocation of risky assets within the standard portfolio choice model. We derive the expressions for the optimal proportion of wealth invested in the risky asset to show they are functions of portfolio returns third- and fourth-order moments as well as on the investor’s risk preferences of prudence and temperance. We illustrate the relative importance that the introduction of those higher-order effects have in the decision of expected utility maximizers using data for the US.

Ordinal Arithmetic: A Case Study for Rippling in a Higher Order Domain

This paper reports a case study in the use of proof planning in the context of higher order syntax. Rippling is a heuristic for guiding rewriting steps in induction that has been used successfully in proof planning inductive proofs using first order representations. Ordinal arithmetic provides a natural set of higher order examples on which transfinite induction may be attempted using rippling. Previously Boyer-Moore style automation could not be applied to such domains. We demonstrate that a higher-order extension of the rippling heuristic is sufficient to plan such proofs automatically. Accordingly, ordinal arithmetic has been implemented in lambda-clam, a higher order proof planning system for induction, and standard undergraduate text book problems have been successfully planned. We show the synthesis of a fixpoint for normal ordinal functions which demonstrates how our automation could be extended to produce more interesting results than the textbook examples tried so far.

Speaker identification using higher order spectral phase features and their effectiveness vis-a-vis Mel-Cepstral features

The effectiveness of higher-order spectral (HOS) phase features in speaker recognition is investigated by comparison with Mel Cepstral features on the same speech data. HOS phase features retain phase information from the Fourier spectrum unlikeMel–frequency Cepstral coefficients (MFCC). Gaussian mixture models are constructed from Mel– Cepstral features and HOS features, respectively, for the same data from various speakers in the Switchboard telephone Speech Corpus. Feature clusters, model parameters and classification performance are analyzed. HOS phase features on their own provide a correct identification rate of about 97% on the chosen subset of the corpus. This is the same level of accuracy as provided by MFCCs. Cluster plots and model parameters are compared to show that HOS phase features can provide complementary information to better discriminate between speakers.