No description available.

This memo describes the initial results of a project to create aself-supervised algorithm for learning object segmentation from videodata. Developmental psychology and computational experience havedemonstrated that the motion segmentation of objects is a simpler,more primitive process than the detection of object boundaries bystatic image cues. Therefore, motion information provides a plausiblesupervision signal for learning the static boundary detection task andfor evaluating performance on a test set. A video camera andpreviously developed background subtraction algorithms canautomatically produce a large database of motion-segmented images forminimal cost. The purpose of this work is to use the information insuch a database to learn how to detect the object boundaries in novelimages using static information, such as color, texture, and shape.This work was funded in part by the Office of Naval Research contract#N00014-00-1-0298, in part by the Singapore-MIT Alliance agreement of11/6/98, and in part by a National Science Foundation Graduate StudentFellowship.

We describe a state-space tracking approach based on a Conditional Random Field(CRF) model, where the observation potentials are \emph{learned} from data. Wefind functions that embed both state and observation into a space wheresimilarity corresponds to $L_1$ distance, and define an observation potentialbased on distance in this space. This potential is extremely fast to compute and in conjunction with a grid-filtering framework can be used to reduce acontinuous state estimation problem to a discrete one. We show how a statetemporal prior in the grid-filter can be computed in a manner similar to asparse HMM, resulting in real-time system performance. The resulting system isused for human pose tracking in video sequences.

The growing requirements of a diversity of applications necessitate the deployment of large and powerful computing systems and failures in these systems may cause severe damage in every aspect from loss of human lives to world economy. However, current fault tolerance techniques cannot meet the increasing requirements for reliability. Thus new solutions are urgently needed and research on proactive schemes is one of the directions that may offer better efficiency. This thesis proposes a novel proactive failure management framework. Its goal is to reduce the failure penalties and improve fault tolerance efficiency in supercomputers when running complex applications. The proposed proactive scheme builds on two core components: failure prediction and proactive failure recovery. More specifically, the failure prediction component is based on the assessment of system events and employs semi-Markov models to capture the dependencies between failures and other events for the forecasting of forthcoming failures. Furthermore, a two-level failure prediction strategy is described that not only estimates the future failure occurrence but also identifies the specific failure categories. Based on the accurate failure forecasting, a prediction-based coordinated checkpoint mechanism is designed to construct extra checkpoints just before each predicted failure occurrence so that the wasted computational time can be significantly reduced. Moreover, a theoretical model has been developed to assess the proactive scheme that enables calculation of the overall wasted computational time.The prediction component has been applied to industrial data from the IBM BlueGene/L system. Results of the failure prediction component show a great improvement of the prediction accuracy in comparison with three other well-known prediction approaches, and also demonstrate that the semi-Markov based predictor, which has achieved the precision of 87.41% and the recall of 77.95%, performs better than other predictors.

The circular dataimage is defined by displaying direction as the color at the same direction in a color wheel composed of a sequence of two-color gradients with color continuity between gradients. The resulting image of circular-spatial data is continuous with high resolution. Examples include ocean wind direction, Earth's main magnetic field, and rocket nozzle internal combustion flow. The cosineogram is defined as the mean cosine of the angle between random components of direction as a function of distance between observation locations. It expresses the spatial correlation of circular-spatial data. A circular kriging solution is developed based on a model fitted to the cosineogram. A method for simulating circular random fields is given based on a transformation of a Gaussian random field. It is adaptable to any continuous probability distribution. Circular random fields were implemented for selected circular probability distributions. An R software package was created with functions and documentation.

[pt] Tabelas são uma forma bastante comum de organizar e publicar dados. Por exemplo, a Web possui um enorme número de tabelas publicadas em HTML, embutidas em documentos em PDF, ou que podem ser simplesmente baixadas de páginas Web. Porém, tabelas nem sempre são fáceis de interpretar pois possuem uma grande variedade de características e são organizadas de diversas formas. De fato, um grande número de métodos e ferramentas foram desenvolvidos para interpretação de tabelas. Esta dissertação apresenta a implementação de um algoritmo, baseado em Conditional Random Fields (CRFs), para classificar as linhas de uma tabela em linhas de cabeçalho, linhas de dados e linhas de metadados. A implementação é complementada por dois algoritmos para reconhecimento de tabelas em planilhas, respectivamente baseados em regras e detecção de regiões. Por fim, a dissertação descreve os resultados e os benefícios obtidos pela aplicação dos algoritmos a tabelas em formato HTML, obtidas da Web, e a tabelas em forma de planilhas, baixadas do Web site da Agência Nacional de Petróleo. / [en] Tables are widely adopted to organize and publish data. For example, the Web has an enormous number of tables, published in HTML, imbedded in PDF documents, or that can be simply downloaded from Web pages. However, tables are not always easy to interpret because of the variety of features and formats used. Indeed, a large number of methods and tools have been developed to interpret tables. This dissertation presents the implementation of an algorithm, based on Conditional Random Fields (CRFs), to classify the rows of a table as header rows, data rows or metadata rows. The implementation is complemented by two algorithms for table recognition in a spreadsheet document, respectively based on rules and on region detection. Finally, the dissertation describes the results and the benefits obtained by applying the implemented algorithms to HTML tables, obtained from the Web, and to spreadsheet tables, downloaded from the Brazilian National Petroleum Agency.

Since their recent introduction, conditional random fields (CRFs) have been successfully applied to a multitude of structured labelling tasks in many different domains. Examples include natural language processing (NLP), bioinformatics and computer vision. Within NLP itself we have seen many different application areas, like named entity recognition, shallow parsing, information extraction from research papers and language modelling. Most of this work has demonstrated the need, directly or indirectly, to employ some form of regularisation when applying CRFs in order to overcome the tendency for these models to overfit. To date a popular method for regularising CRFs has been to fit a Gaussian prior distribution over the model parameters. In this thesis we explore other methods of CRF regularisation, investigating their properties and comparing their effectiveness. We apply our ideas to sequence labelling problems in NLP, specifically part-of-speech tagging and named entity recognition. We start with an analysis of conventional approaches to CRF regularisation, and investigate possible extensions to such approaches. In particular, we consider choices of prior distribution other than the Gaussian, including the Laplacian and Hyperbolic; we look at the effect of regularising different features separately, to differing degrees, and explore how we may define an appropriate level of regularisation for each feature; we investigate the effect of allowing the mean of a prior distribution to take on non-zero values; and we look at the impact of relaxing the feature expectation constraints satisfied by a standard CRF, leading to a modified CRF model we call the inequality CRF. Our analysis leads to the general conclusion that although there is some capacity for improvement of conventional regularisation through modification and extension, this is quite limited. Conventional regularisation with a prior is in general hampered by the need to fit a hyperparameter or set of hyperparameters, which can be an expensive process. We then approach the CRF overfitting problem from a different perspective. Specifically, we introduce a form of CRF ensemble called a logarithmic opinion pool (LOP), where CRF distributions are combined under a weighted product. We show how a LOP has theoretical properties which provide a framework for designing new overfitting reduction schemes in terms of diverse models, and demonstrate how such diverse models may be constructed in a number of different ways. Specifically, we show that by constructing CRF models from manually crafted partitions of a feature set and combining them with equal weight under a LOP, we may obtain an ensemble that significantly outperforms a standard CRF trained on the entire feature set, and is competitive in performance to a standard CRF regularised with a Gaussian prior. The great advantage of LOP approach is that, unlike the Gaussian prior method, it does not require us to search a hyperparameter space. Having demonstrated the success of LOPs in the simple case, we then move on to consider more complex uses of the framework. In particular, we investigate whether it is possible to further improve the LOP ensemble by allowing parameters in different models to interact during training in such a way that diversity between the models is encouraged. Lastly, we show how the LOP approach may be used as a remedy for a problem that standard CRFs can sometimes suffer. In certain situations, negative effects may be introduced to a CRF by the inclusion of highly discriminative features. An example of this is provided by gazetteer features, which encode a word's presence in a gazetteer. We show how LOPs may be used to reduce these negative effects, and so provide some insight into how gazetteer features may be more effectively handled in CRFs, and log-linear models in general.

New view synthesis (NVS) is the problem of generating a novel image of a scene, given a set of calibrated input images of the scene, i.e. their viewpoints, and also that of the output image, are known. The problem is generally ill-posed---a large number of scenes can generate a given set of images, therefore there may be many equally likely (given the input data) output views. Some of these views will look less natural to a human observer than others, so prior knowledge of natural scenes is required to ensure that the result is visually plausible. The aim of this thesis is to compare and improve upon the various Markov random field} and conditional random field prior models, and their associated maximum a posteriori optimization frameworks, that are currently the state of the art for NVS and stereo (itself a means to NVS). A hierarchical example-based image prior is introduced which, when combined with a multi-resolution framework, accelerates inference by an order of magnitude, whilst also improving the quality of rendering. A parametric image prior is tested using a number of novel discrete optimization algorithms. This general prior is found to be less well suited to the NVS problem than sequence-specific priors, generating two forms of undesirable artifact, which are discussed. A novel pairwise clique image prior is developed, allowing inference using powerful optimizers. The prior is shown to perform better than a range of other pairwise image priors, distinguishing as it does between natural and artificial texture discontinuities. A dense stereo algorithm with geometrical occlusion model is converted to the task of NVS. In doing so, a number of challenges are novelly addressed; in particular, the new pairwise image prior is employed to align depth discontinuities with genuine texture edges in the output image. The resulting joint prior over smoothness and texture is shown to produce cutting edge rendering performance. Finally, a powerful new inference framework for stereo that allows the tractable optimization of second order smoothness priors is introduced. The second order priors are shown to improve reconstruction over first order priors in a number of situations.

O presente trabalho estuda o modelo de Blume-Capel na rede aleatória e também analisa a inclusão de um termo de campo cristalino aleatório e de um termo de campo local aleatório. Ao resolver o modelo na rede aleatória, uma técnica de conectividade finita foi utilizada, na qual cada spin é conectado a um número finito de outros spins. Os spins foram conectados de acordo com uma distribuição de Poisson, os termos de campo aleatório seguiram uma distribuição bimodal e as interações entre os spins foram consideradas uniformes. Desse modo, só há desordem nas conexões entre os spins. O foco desse trabalho foi determinar como a natureza da transição de fase é alterada com a conectividade e se há um comportamento reentrante das linhas de transição de fase. A técnica de réplicas é usada para obter equações de ponto de sela para a distribuição de campos locais. Um Ansatz de simetria de réplicas foi utilizado para a função de ordem e esse foi escrito em termos de uma distribuição bidimensional de campos efetivos, onde uma das componentes é associada com um termo linear dos spins e a outra com o termo de campo cristalino. Com isso, equações para as funções de ordem e a energia livre podem ser obtidas. Uma técnica de dinâmica populacional é usada para resolver numericamente a equação auto-consistente para a distribuição de campos locais e outros parâmetros, como a magnetização, a atividade da rede e a energia livre. Os resultados indicam que a natureza da transição ferromagnética-paramagnética, a posição do ponto tricrítico e a existência de reentrância dependem fortemente do valor da conectividade e, nos casos com um termo de campo aleatório, dependem da intensidade dos campos aleatórios. No caso em que o campo cristalino é aleatório, o ponto tricrítico é suprimido para valores acima de um certo valor de aleatoriedade. / The present work studies the Blume-Capel model in a random network and also analyses the inclusion of a random crystal-field term and a random field term. To solve the model in a random network a finite connectivity technique is used, in which each spin is connected to a finite number of other spins. The spins were connected according a Poisson distribution, the random field terms followed a bimodal distribution and the bonds between the spins were considered uniform. Thus, there is only a connection disorder. The focus of this work was on determining how the nature of the phase transition changes with the connectivity and the random fields and if there is a reentrant behavior of the phase boundaries. The replica technique is used to obtain saddle-point equations for the effective local-field distribution. The replica symmetric Ansatz for the order function is written in terms of a two-dimensional effective-field distribution, where one of the components is associated with a linear form in the spins and the other with the crystal-field term. This allows one to derive equations for the order function and for the free-energy. A population dynamics procedure is used to solve numerically a self-consistency equation for the distribution of the local field and with it some physical parameters, like magnetization and free-energy. The results obtained indicate that the nature of the F-P transition, the location of the tricritical point and the presence of a reentrant phase depend strongly on the connectivity. In the cases with a random field term, those are also dependent on the intensity of the fields. For the case with a random crystal-field term, the tricritical point is supressed above a certain value of randomness.

Neste trabalho utilizam-se duas adaptações do modelo originalmente proposto por van Hemmen com o intuito de investigar os efeitos de um campo aleatório hi sob as transições de fases: um modelo com spin 1 estudado na versão clássica e um modelo na formulação fermiônica. A escolha do modelo de van Hemmen está relacionada ao fato de que não e necessário utilizar o método das réplicas para tratar a desordem. No primeiro caso, o modelo clássico conta com um campo cristalino (D) que favorece energeticamente os estados não interagentes. As interações aleatórias Ji j são respons aveis por introduzir desordem e frustração ao problema. Tanto as variáveis aleatórias quanto o campo aleatório seguem uma distribuição de probabilidades bimodal. Analisando o comportamento dos parâmetros de ordem e da energia livre, diagramas de fases da temperatura pelo acoplamento ferromagnético J0 e pelo campo cristalino D para diferentes valores de hi foram construídos. Os resultados indicam que a presença do campo aleatório tende a reduzir o ponto tricrítico das transições de fases e, para determinado valor de hi, uma nova solução da fase vidro de spin (VS) pode ser favorecida. Além disso, para valores relativamente altos de hi, o problema apresenta pontos multicríticos nas transições de fase. Também busca-se investigar nesse modelo se o mesmo e capaz de apresentar algum tipo de transição inversa (TI) As TI são uma classe de transições de fases altamente contraintuitivas, em que uma fase usualmente ordenada tem entropia maior que uma fase desordenada. Elas se manifestam nos diagramas de fases através de uma reentrância da fase desordenada-ordenada-desordenada conforme a temperatura diminui. Embora o modelo apresente diversos pontos tricríticos na transição PM/VS, nenhum tipo de transição reentrante foi observada, não havendo, portanto, nenhuma evidência de transição inversa no sistema. Já o modelo analisado na formulação fermiônica conta com um potencial químico (m), que controla a diluição magnética relacionada ao favorecimento dos sítios duplamente ocupados ou vazios, e com um campo magnético transverso G, que introduz flutuações quânticas ao problema. Nesse caso, as interações de spin Ji j e o campo aleatório seguem uma distribuição gaussiana. A introdução do campo hi, a nível de campo médio, permite investigar as TI sob os efeitos de uma desordem que não e uma fonte de frustração Os resultados mostram uma transição reentrante da fase VS para a fase paramagnética (PM) na ausência de G e hi. A reentrância aparece para um certo intervalo de m, em que se encontra uma fase PM a baixas temperaturas com menor entropia do que a fase VS, caracterizando a transição do tipo congelamento inverso (CI). No entanto o CI e gradualmente suprimido quando os efeitos hi são intensificados. Além disso, o CI e completamente destruído pelas flutuações quânticas provenientes do G. Dessa forma, a desordem combinada com a diluição pode apresentar um cenário favorável a ocorrência de CI, enquanto o campo aleatório e as flutuações quânticas agem contra este tipo de transição. / In this work, two adaptations to the original model proposed by van Hemmen are used with the aim of investigating the e ects of a random eld hi under the phase transitions: a model studied in the classical version and a model in the fermionic formulation. The van Hemmen model was chosen because the disorder can be treated without the use of the replica method. In the rst case, the classic model has a crystal eld (D) which energetically favors the non-interacting states. The random interactions Ji j are responsible for introduce disorder and frustration to the problem. Both random eld and random variables follow a bimodal probability distribution. Analyzing the behavior of the order parameters and the free energy, phase diagrams of temperatura T versus the ferromagnetic coupling J0 and T versus the crystal eld D for di erent values of hi were build. The results indicate that the presence of the random eld tends to reduce the tricritical point of the phase transitions. For a given value of hi, a new solution of phase spin glass (SG) can be favored. In addition, for su ciently high enough values of hi the problem presents multicritical points in phase transitions. It is also intended to investigate if this model is able to present some kind of inverse transition (IT) IT is a class of highly nonintuitive phase transitions in that the usual ordered phase has more entropy than the disordered one. The IT manifests in the phase diagrams as a reentrance of the disordered-ordereddisordered phase according to the temperature decreases. Although the model presents several tricritical points in the transition PM=SG, no type of reentrant transition was observed. Therefore, there is no evidence of inverse transition in this model. The model analyzed in the fermionic formulation has a chemical potential (m), which has the role of controlling the magnetic dilution related to favoring double-occupation or empty sites. This model also counts with a transverse magnetic eld G, which introduces quantum uctuations to the problem. In this case, the spin interactions Ji j and random eld follow a Gaussian distribution The introduction of the hi allows the investigation of IT under the e ects of a disorder that is not a source of frustration. The results show a reentrant transition from the SG phase to the PM phase in the absence of G and hi. The reentrance appears for a certain range of m, in which there is a PM phase at low temperatures with lower entropy than the SG phase, characterizing the inverse freezing (IF) transition. However, IF is gradually suppressed when the e ects hi are intensi ed. Moreover, the IF is completely destroyed by quantum uctuations from G. Thus, the disorder combined with the dilution may present the favorable scenario to the occurrence of IF, while the random eld and the uctuations quantum mechanics act against this kind of transition.