Using Graph Components Derived from an Associative Concept Dictionary to Predict fMRI Neural Activation Patterns that Represent the Meaning of Nouns

In this study, we introduce an original distance definition for graphs, called the Markov-inverse-F measure (MiF). This measure enables the integration of classical graph theory indices with new knowledge pertaining to structural feature extraction from semantic networks. MiF improves the conventional Jaccard and/or Simpson indices, and reconciles both the geodesic information (random walk) and co-occurrence adjustment (degree balance and distribution). We measure the effectiveness of graph-based coefficients through the application of linguistic graph information for a neural activity recorded during conceptual processing in the human brain. Specifically, the MiF distance is computed between each of the nouns used in a previous neural experiment and each of the in-between words in a subgraph derived from the Edinburgh Word Association Thesaurus of English. From the MiF-based information matrix, a machine learning model can accurately obtain a scalar parameter that specifies the degree to which each voxel in (the MRI image of) the brain is activated by each word or each principal component of the intermediate semantic features. Furthermore, correlating the voxel information with the MiF-based principal components, a new computational neurolinguistics model with a network connectivity paradigm is created. This allows two dimensions of context space to be incorporated with both semantic and neural distributional representations.

Paving the way for the use of the SDQ in economic evaluations of school-based population health interventions: an empirical analysis of the external validity of SDQ mapping algorithms to the CHU9D in an educational setting

Purpose
The Strengths and Difficulties Questionnaire (SDQ) is a behavioural screening tool for children. The SDQ is increasingly used as the primary outcome measure in population health interventions involving children, but it is not preference based; therefore, its role in allocative economic evaluation is limited. The Child Health Utility 9D (CHU9D) is a generic preference-based health-related quality of-life measure. This study investigates the applicability of the SDQ outcome measure for use in economic evaluations and examines its relationship with the CHU9D by testing previously published mapping algorithms. The aim of the paper is to explore the feasibility of using the SDQ within economic evaluations of school-based population health interventions.
Methods
Data were available from children participating in a cluster randomised controlled trial of the school-based roots of empathy programme in Northern Ireland. Utility was calculated using the original and alternative CHU9D tariffs along with two SDQ mapping algorithms. t tests were performed for pairwise differences in utility values from the preference-based tariffs and mapping algorithms.
Results
Mean (standard deviation) SDQ total difficulties and prosocial scores were 12 (3.2) and 8.3 (2.1). Utility values obtained from the original tariff, alternative tariff, and mapping algorithms using five and three SDQ subscales were 0.84 (0.11), 0.80 (0.13), 0.84 (0.05), and 0.83 (0.04), respectively. Each method for calculating utility produced statistically significantly different values except the original tariff and five SDQ subscale algorithm.
Conclusion
Initial evidence suggests the SDQ and CHU9D are related in some of their measurement properties. The mapping algorithm using five SDQ subscales was found to be optimal in predicting mean child health utility. Future research valuing changes in the SDQ scores would contribute to this research.

Memory-centric VDF Graph Transformations for Practical FPGA Implementation

Realising memory intensive applications such as image and video processing on FPGA requires creation of complex, multi-level memory hierarchies to achieve real-time performance; however commerical High Level Synthesis tools are unable to automatically derive such structures and hence are unable to meet the demanding bandwidth and capacity constraints of these applications. Current approaches to solving this problem can only derive either single-level memory structures or very deep, highly inefficient hierarchies, leading in either case to one or more of high implementation cost and low performance. This paper presents an enhancement to an existing MC-HLS synthesis approach which solves this problem; it exploits and eliminates data duplication at multiple levels levels of the generated hierarchy, leading to a reduction in the number of levels and ultimately higher performance, lower cost implementations. When applied to synthesis of C-based Motion Estimation, Matrix Multiplication and Sobel Edge Detection applications, this enables reductions in Block RAM and Look Up Table (LUT) cost of up to 25%, whilst simultaneously increasing throughput.

Novel Application of Genetic Sequencing algorithms to optimisation of hardware resource sharing for DSP

Field programmable gate array (FPGA) technology is a powerful platform for implementing computationally complex, digital signal processing (DSP) systems. Applications that are multi-modal, however, are designed for worse case conditions. In this paper, genetic sequencing techniques are applied to give a more sophisticated decomposition of the algorithmic variations, thus allowing an unified hardware architecture which gives a 10-25% area saving and 15% power saving for a digital radar receiver.

Compact Routing Messages in Self-Healing Trees

Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact routing scheme. Besides, our schemes are developed for low memory nodes, i.e., nodes need only O(log2 n) memory, and are thus, compact schemes.
We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version (using only O(log n) local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008]. The second algorithm (CompactFTZ) combines CompactFT with Thorup-Zwick’s treebased compact routing scheme [SPAA 2001] to produce a fully compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time with the affected nodes self-healing locally by adding few edges. CompactFT recovers from each attack in only O(1) time and ∆ messages, with only +3 degree increase and O(log∆) graph diameter increase, over any sequence of deletions (∆ is the initial maximum degree).
Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver has not been deleted, with only an additional O(y log ∆) latency, where y is the number of nodes that have been deleted on the path between s and t. If t has been deleted, s gets informed and the packet removed from the network.

Synthesis of FPGA-based accelerators implementing recursive algorithms

O desenvolvimento de sistemas computacionais é um processo complexo, com múltiplas etapas, que requer uma análise profunda do problema, levando em consideração as limitações e os requisitos aplicáveis. Tal tarefa envolve a exploração de técnicas alternativas e de algoritmos computacionais para optimizar o sistema e satisfazer os requisitos estabelecidos. Neste contexto, uma das mais importantes etapas é a análise e implementação de algoritmos computacionais. Enormes avanços tecnológicos no âmbito das FPGAs (Field-Programmable Gate Arrays) tornaram possível o desenvolvimento de sistemas de engenharia extremamente complexos. Contudo, o número de transístores disponíveis por chip está a crescer mais rapidamente do que a capacidade que temos para desenvolver sistemas que tirem proveito desse crescimento. Esta limitação já bem conhecida, antes de se revelar com FPGAs, já se verificava com ASICs (Application-Specific Integrated Circuits) e tem vindo a aumentar continuamente. O desenvolvimento de sistemas com base em FPGAs de alta capacidade envolve uma grande variedade de ferramentas, incluindo métodos para a implementação eficiente de algoritmos computacionais. Esta tese pretende proporcionar uma contribuição nesta área, tirando partido da reutilização, do aumento do nível de abstracção e de especificações algorítmicas mais automatizadas e claras. Mais especificamente, é apresentado um estudo que foi levado a cabo no sentido de obter critérios relativos à implementação em hardware de algoritmos recursivos versus iterativos. Depois de serem apresentadas algumas das estratégias para implementar recursividade em hardware mais significativas, descreve-se, em pormenor, um conjunto de algoritmos para resolver problemas de pesquisa combinatória (considerados enquanto exemplos de aplicação). Versões recursivas e iterativas destes algoritmos foram implementados e testados em FPGA. Com base nos resultados obtidos, é feita uma cuidada análise comparativa. Novas ferramentas e técnicas de investigação que foram desenvolvidas no âmbito desta tese são também discutidas e demonstradas.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

Politopo de Birkhoff acíclico

Neste trabalho estabelece-se uma interpreta c~ao geom etrica, em termos da teoria dos grafos, para v ertices, arestas e faces de uma qualquer dimens~ao do politopo de Birkho ac clico, Tn = n(T), onde T e uma arvore com n v ertices. Generaliza-se o resultado obtido por G. Dahl, [18], para o c alculo do di^ametro do grafo G( t n), onde t n e o politopo das matrizes tridiagonais duplamente estoc asticas. Adicionalmente, para q = 0; 1; 2; 3 s~ao obtidas f ormulas expl citas para a contagem do n umero de q faces do politopo de Birkho tridiagonal, t n, e e feito o estudo da natureza geom etrica dessas mesmas faces. S~ao, tamb em, apresentados algoritmos para efectuar contagens do n umero de faces de dimens~ao inferior a de uma dada face do politopo de Birkho ac clico.

Optimisation of viscoelastic treatments using genetic algorithms

Viscoelastic treatments are one of the most efficient treatments, as far as passive damping is concerned, particularly in the case of thin and light structures. In this type of treatment, part of the strain energy generated in the viscoelastic material is dissipated to the surroundings, in the form of heat. A layer of viscoelastic material is applied to a structure in an unconstrained or constrained configuration, the latter proving to be the most efficient arrangement. This is due to the fact that the relative movement of both the host and constraining layers cause the viscoelastic material to be subjected to a relatively high strain energy. There are studies, however, that claim that the partial application of the viscoelastic material is just as efficient, in terms of economic costs or any other form of treatment application costs. The application of patches of material in specific and selected areas of the structure, thus minimising the extension of damping material, results in an equally efficient treatment. Since the damping mechanism of a viscoelastic material is based on the dissipation of part of the strain energy, the efficiency of the partial treatment can be correlated to the modal strain energy of the structure. Even though the results obtained with this approach in various studies are considered very satisfactory, an optimisation procedure is deemed necessary. In order to obtain optimum solutions, however, time consuming numerical simulations are required. The optimisation process to use the minimum amount of viscoelastic material is based on an evolutionary geometry re-design and calculation of the modal damping, making this procedure computationally costly. To avert this disadvantage, this study uses adaptive layerwise finite elements and applies Genetic Algorithms in the optimisation process.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Completely supervised training algorithms for B-spline neural networks and neuro-fuzzy systems

Complete supervised training algorithms for B-spline neural networks and fuzzy rule-based systems are discussed. By interducing the relationship between B-spline neural networks and certain types of fuzzy models, training algorithms developed initially for neural networks can be adapted by fuzzy systems.

Preface to the special section on algorithms and architectures for real-time control

Rapid developments in microelectronics and computer science continue to fuel new opportunities for real-time control engineers. The ever-increasing system complexity and sophistication, environmental legislation, economic competition, safety and reliability constitute some of the driving forces for the research themes presented at the IFAC Workshop on Algorithms and Architectures for Real-Time Control (AARTC'2000). The Spanish Society for Automatic Control hosted AARTC'2000, which was held at Palma de Maiorca, Spain, from 15 to 17 May. This workshop was the sixth in the series.

Comparison of on-line learning algorithms for RBF models in greenhouse environmental control problems

The problem with the adequacy of radial basis function neural networks to model the inside air temperature as a function of the outside air temperature and solar radiation, and the inside relative humidity in an hydroponic greenhouse is addressed.

Automatic parallelization of matricial algorithms

The introduction of parallel processing architectures allowed the real time impelemtation of more sophisticated control algorithms with tighter specifications in terms of sampling time. However, to take advantage of the processing power of these architectures the control engeneer, due to the lack of appropriate tools, must spend a considerable amount of time in the parallelizaton of the control algorithm.