Turing Machines and Markov Algorithms are, and were designed to be, the most powerful devices possible in the field of abstract automata: by their means any and every computable function can be computed. Because of their equal, indeed maximal, strength, it was naturally assumed that these devices should be equivalent. Nonetheless a formal, exact proof of this universally presumed equivalence was lacking. The present dissertation rectifies that omission by developing the desired complete, rigorous proof of the equivalence between Turing Machines and Markov Algorithms. The demonstration is being conducted in a constructionist way: for any given Markov Algorithm it is shown that a Turing Machine can be constructed capable of performing exactly what the Algorithm can do and nothing more, and vice versa. The proof consists in the theoretical construction, given an arbitrary Markov Algorithm, of a Turing Machine behaving in exactly the same way as the Algorithm for all possible inputs; and conversely. Furthermore, the proof is given concrete shape by designing a computer program which can actually carry out the said theoretical constructions. The equivalence between TM and MA as proven in the first part of our thesis, is being used in the second part for establishing some important consequent results: Thus the equivalence of Deterministic and Nondeterministic MA, of TM and Type 0 Grammars, and of Labelled and Unlabelled MA is concisely shown, and the use of TM as recognizers for type 1 and 3 grammars exclusively is exhibited. It is interesting that, by utilizing the equivalence of TM and MA, it was made possible that the proofs of these latter results be based on primitive principles.

This thesis addresses a comprehensive approach to understanding the time-varying thermal errors in machine tools. Errors in machine tools are generally classified as being time or spatial dependent. Thermal errors are strongly dependent on the continuously changing operating conditions of a machine and its surrounding environment. Uniform temperature rises or stable temperature gradients, which produce time-invariant thermal errors, are considered to be rare in ordinary shop floor environments. Difficulties in analysing time-varying thermal errors are that, first of all, the temperature distribution within the components of a machine should be evaluated, and secondly, the distribution is continuously changing with time. These difficulties can be overcome by introducing a point-wise description method with three thermal parameters. From the theoretical analysis of simple machine elements such as bars, beams and cylinders, and extensive finite-element simulation data for a straightedge subject to room temperature variations, three thermal parameters, i. e. time-delay, time-constant and gain, were identified to obtain a precise description of the thermal deformation of a point of a machine body. Time-delay is dependent largely on thermal diffusivity, and the heat transfer mechanism. The time-constant is governed by heat capacity, heat transfer mechanism and body size. Gain, on the other hand, is determined by the thermal expansion coefficient, heat transfer mechanism and mechanical constraint. The three thermal parameters, in turn, imply that thermal deformation of a point in a body can be described by a simple first- order differential equation. Regarding their dependence on the heat transfer mechanism, a more refined description requires a time-varying linear first-order differential equation. Such an equation can be applied to each point of interest of a machine body. The final form of modelling, using the parameters, is a state-space equation gathering the governing equations for the points of interest. By adopting the point-wise discrete modelling method, we can overcome the difficulty of the spatial distribution of the temperature. Indeed, the calibration of a machine tool is usually performed at discrete points. The completion of this approach was made by presenting the methods by which the three thermal parameters can be evaluated. The first method employs analytical tools based on simplifying assumptions about the shape and boundary conditions of machine components. The second method was to apply numerical techniques to complex machine components. Because there are many drawbacks in theoretical approaches, experimental techniques are essential to complement them. The three thermal parameters can be easily identified using popular parameter identification techniques which can be applied to time-varying cases by their recursive forms. The techniques described were applied to modelling the thermal errors in a single-point diamond turning research machine. It was found that the dominant error component was spindle axial growth. The predictive model for the time-constant was shown to be in agreement with both the machine and with the scaled physical model rig.

Master of Science / Department of Computer Science / William Hsu / This work focuses on the data science challenge problem of predicting the decision for past immigration visa applications using supervised machine learning for classification. I describe an end-to-end approach that first prepares historical data for supervised inductive learning, trains various discriminative models, and evaluates these models using simple statistical validation methods. The H-1B visa allows employers in the United States to temporarily employ foreign nationals in various specialty occupations that require a bachelor’s degree or higher in the specific specialty, or its equivalents. These specialty occupations may often include, but are not limited to: medicine, health, journalism, and areas of science, technology, engineering and mathematics (STEM). Every year the United States Citizenship and Immigration Service (USCIS) grants a current maximum of 85,000 visas, even though the number of applicants surpasses this amount by a huge difference and this selection process is claimed to be a lottery system. The dataset used for this experimental research project contains all the petitions made for this visa cap from the year 2011 to 2016. This project aims at using discriminative machine learning techniques to classify these petitions and predict the “case status” of each petition based on various factors. Exploratory data analysis is also done to determine the top employers, the locations which most appeal for foreign nationals under this visa cap and the job roles which have the highest number of foreign workers. I apply supervised inductive learning algorithms such as Gaussian Naïve Bayes, Logistic Regression, and Random Forests to identify the most probable factors for H-1B visa certifications and compare the results of each to determine the best predictive model for this testbed.

Master of Science / Department of Computing and Information Sciences / William H. Hsu / Need is a function of both individual household’s ability to meet basic requirements such as food, shelter, clothing, medical care, and transportation, and latent exogenous factors such as the cost of living and available community support for such requirements. Identifying this need driven poverty helps in understanding the socioeconomic status of individuals and to identify the areas of development. This work aims at using georeferenced data from the American Community Survey (ACS) to estimate baseline need based on aggregated socioeconomic variables indicating absolute and relative poverty. In this project, I implement and compare the results of several machine learning classification algorithms such as Random Forest, Support Vector Machine, and Logistic Regression to identify poverty for different block groups in the United States

Multi-lable learning (ML), multi-instance multi-label learning (MIML), large network learning and random under-sampling system are four active research topics in machine learning which have been studied intensively recently. So far, there are still a lot of open problems to be figured out in these topics which attract worldwide attention of researchers. This thesis mainly focuses on several novel methods designed for these research tasks respectively. Then main difference between ML learning and traditional classification task is that in ML learning, one object can be characterized by several different labels (or classes). One important observation is that the labels received by similar objects in ML data are usually highly correlated with each other. In order to exploring this correlation of labels between objects which might be a key issue in ML learning, we consider to require the resulting label indicator to be low rank. In the proposed model, nuclear norm which is a famous convex relaxation of intractable matrix rank is introduced to label indicator in order to exploiting the underlying correlation in label domain. Motivated by the idea of spectral clustering, we also incorporate information from feature domain by constructing a graph among objects based on their features. Then with partial label information available, we integrate them together into a convex low rank based model designed for ML learning. The proposed model can be solved efficiently by using alternating direction method of multiplier (ADMM). We test the performance on several benchmark ML data sets and make comparisons with the state-of-art algorithms. The classification results demonstrate the efficiency and effectiveness of the proposed low rank based methods. One step further, we consider MIML learning problem which is usually more complicated than ML learning: besides the possibility of having multiple labels, each object can be described by multiple instances simultaneously which may significantly increase the size of data. To handle the MIML learning problem we first propose and develop a novel sparsity-based MIML learning algorithm. Our idea is to formulate and construct a transductive objective function for label indicator to be learned by using the method of random walk with restart that exploits the relationships among instances and labels of objects, and computes the affinities among the objects. Then sparsity can be introduced in the labels indicator of the objective function such that relevant and irrelevant objects with respect to a given class can be distinguished. The resulting sparsity-based MIML model can be given as a constrained convex optimization problem, and it can be solved very efficiently by using the augmented Lagrangian method (ALM). Experimental results on benchmark data have shown that the proposed sparse-MIML algorithm is computationally efficient, and effective in label prediction for MIML data. We demonstrate that the performance of the proposed method is better than the other testing MIML learning algorithms. Moreover, one big concern of an MIML learning algorithm is computational efficiency, especially when figuring out classification problem for large data sets. Most of the existing methods for solving MIML problems in literature may take a long computational time and have a huge storage cost for large MIML data sets. In this thesis, our main aim is to propose and develop an efficient Markov Chain based learning algorithm for MIML problems. Our idea is to perform labels classification among objects and features identification iteratively through two Markov chains constructed by using objects and features respectively. The classification of objects can be obtained by using labels propagation via training data in the iterative method. Because it is not necessary to compute and store a huge affinity matrix among objects/instances, both the storage and computational time can be reduced significantly. For instance, when we handle MIML image data set of 10000 objects and 250000 instances, the proposed algorithm takes about 71 seconds. Also experimental results on some benchmark data sets are reported to illustrate the effectiveness of the proposed method in one-error, ranking loss, coverage and average precision, and show that it is competitive with the other methods. In addition, we consider the module identification from large biological networks. Nowadays, the interactions among different genes, proteins and other small molecules are becoming more and more significant and have been studied intensively. One general way that helps people understand these interactions is to analyze networks constructed from genes/proteins. In particular, module structure as a common property of most biological networks has drawn much attention of researchers from different fields. However, biological networks might be corrupted by noise in the data which often lead to the miss-identification of module structure. Besides, some edges in network might be removed (or some nodes might be miss-connected) when improper parameters are selected which may also affect the module identified significantly. In conclusion, the module identification results are sensitive to noise as well as parameter selection of network. In this thesis, we consider employing multiple networks for consistent module detection in order to reduce the effect of noise and parameter settings. Instead of studying different networks separately, our idea is to combine multiple networks together by building them into tensor structure data. Then given any node as prior label information, tensor-based Markov chains are constructed iteratively for identification of the modules shared by the multiple networks. In addition, the proposed tensor-based Markov chain algorithm is capable of simultaneously evaluating the contribution from each network. It would be useful to measure the consistency of modules in the multiple networks. In the experiments, we test our method on two groups of gene co-expression networks from human beings. We also validate biological meaning of modules identified by the proposed method. Finally, we introduce random under-sampling techniques with application to X-ray computed tomography (CT). Under-sampling techniques are realized to be powerful tools of reducing the scale of problem especially for large data analysis. However, information loss seems to be un-avoidable which inspires different under-sampling strategies for preserving more useful information. Here we focus on under-sampling for the real-world CT reconstruction problem. The main motivation is to reduce the total radiation dose delivered to patient which has arisen significant clinical concern for CT imaging. We compare two popular regular CT under-sampling strategies with ray random under-sampling. The results support the conclusion that random under-sampling always outperforms regular ones especially for the high down-sampling ratio cases. Moreover, based on the random ray under-sampling strategy, we propose a novel scatter removal method which further improves performance of ray random under-sampling in CT reconstruction.

Orientador: Lee Luan Ling / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-24T05:09:39Z (GMT). No. of bitstreams: 1 FernandezMerjildo_DiegoAlonso_M.pdf: 6281716 bytes, checksum: 6e22526557511699a8961e5b44949c78 (MD5) Previous issue date: 2013 / Resumo: O presente trabalho propõe um algoritmo AdaBoost modificado, que minimiza o efeito do overfitting no treinamento produzido por amostras ruidosas. Para este fim, a atualização da distribuição de pesos é feita baseado na fragmentação do erro de treinamento, o qual permite atualizar efetivamente as amostras classificadas incorretamente para cada nível de taxa de erro. Subsequentemente, o algoritmo desenvolvido é aplicado no processo de detecção de faces, utilizando os Padrões Binários Locais Multi-Escala em Blocos (Multiscale Block Local Binary Patterns (MB-LBP)) como padrões característicos para formação de uma cascata de classificadores. Os resultados experimentais mostram que o algoritmo proposto é simples e eficiente, evidenciando vantagens sobre os algoritmos AdaBoost clássicos, em termos de maior capacidade de generalização, prevenção de overfitting e maiores taxas de acerto em imagens de baixa resolução / Abstract: This work aims a modification to the AdaBoost algorithm applied to face detection. Initially, we present the approaches used in face detection, highlighting the success of methods based on appearance. Then, we focus on the AdaBoost algorithm, its performance and the improvements realized by author as published literature. Despite the indisputable success of Boosting algorithms, it is affected by the high sensitivity to noisy samples. In order to avoid overfitting of noisy samples, we consider that the error rate is divided into fragmentary errors. We introduce a factor based on misclassified samples, to update the weight distribution in the training procedure. Furthermore, the algorithm developed is applied to face detection procedure, for which it is used Block Multiscale Local Binary Patterns (MB-LBP) in feature extraction as well as a cascade of classifiers. The experimental results show that the proposal to include a factor based on the frequency of misclassified samples, is simple and efficient, showing advantages over classical AdaBoost algorithms, which include ability to generalize, preventing overfitting and higher hit rates in images of low resolution / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

M. Ing. (Electrical and Electronic Engineering) / This dissertation describes the development of a modular real-time controller implemented on a personal computer for a hydrostatically driven vehicle. In such a vehicle the conventional mechanical transmission is replaced with a hydrostatic pump and two hydrostatic motors, making use of the secondary control principle. The infinitely variable transmission and wheel pair controller gives the vehicle superior traction and mobility over conventionally driven vehicles.

In the face of rapid development in information technology coupled with a growing dynamism in global markets, new concepts of building computer controlled machines have proliferated. Such approaches promise to lead to a new generation of machines which typically share common design objectives. They seek to advance the underlying concepts of contemporary computer controlled machines (such as robots, CNC, etc.) in a way that resultant systems demonstrate attributes of flexibility, extendibility, configurability, openness, modularity and so on.

The work reported in this thesis is concerned with both a fundamental assessment and the provision of a comprehensive MDI system for milling machines. The conceptual design has led to the realisation of a prototype work station which represents advances beyond the current state of the art for systems containing an APT-like processor and employs a powerful and flexible conversationally-based system with graphics support. The work station has been interfaced in STR mode to a numerically controlled milling machine and the effectiveness of the programming system has been demonstrated by the production of four workpieces.

My thesis is an analysis of classical problems in perceptual cognition as they appear in Descartes' mechanical philosophy. My primary focus will be on animals, as well as on the models and metaphors that Descartes used to explain how sense perception, information processing, self-regulation, and self-determination occur in natural automata. His models and metaphors typically include man-made devices of his age and a variety of natural processes taken from the inanimate part of nature, which will also be an integral part of my discussion. Throughout the analysis, I will approach these issues from the vantage point of the notion of physiological autonomy, a concept I develop to show how the inner mechanisms of organic bodies contribute to their autonomous functioning in the physical world in Descartes' conception. This is an important task because it allows us to have a better understanding of the mechanical approach to the living in the early modern period, but also because the approach I adopt here highlights the shortcomings of existing literature on the bête-machine theory which most often fail to appreciate Descartes' efforts to imagine a working cognitive system inside non-human living creatures. Even those commentators who direct their attention to Descartes' views about animals emphasise the limitations of natural automata resulting from what they are not, i.e. they are not mind-body unions as humans, whereas I shall maintain that if we understand correctly what the machinery of the body is capable of, we will understand better what Descartes has to say about human cognition as well, in particular, what he believes the body contributes to the cognitive economy of embodied minds.