No presente trabalho provamos resultados sobre as flutuações dos fluxos de partículas e das partículas marcadas no processo de Hammersley multiclasse. Os métodos das demonstrações são robustos, formulados de modo a serem aplicados em outros processos, em particular se aplicam ao processo de exclusão totalmente assimétrico multiclasse (TASEP multiclasse) e à seu respectivo modelo de percolação de última passagem. Os principais teoremas obtidos são um teorema central do limite para o choque, seu coeficiente de difusão e uma fórmula exata para a variância do fluxo de partículas de classe N >1 para o processo em equilíbrio multiclasse. / We prove fluctuations results concerning fluxes of particles and tagged particles on multiclass Hammersley process. The methods used are robust and apply to other processes, in particular all the proofs can be adapted to the Multiclass totally asymmetric simple exclusion process (Multiclass TASEP) and its respective last passage percolation model. The main theorems obtained are a central limit theorem for the shock, its diffusion coefficient and an exact formula for the variance of the $N$-th class particle flux in a stationary version of the multiclass process when N > 1.

No presente trabalho provamos resultados sobre as flutuações dos fluxos de partículas e das partículas marcadas no processo de Hammersley multiclasse. Os métodos das demonstrações são robustos, formulados de modo a serem aplicados em outros processos, em particular se aplicam ao processo de exclusão totalmente assimétrico multiclasse (TASEP multiclasse) e à seu respectivo modelo de percolação de última passagem. Os principais teoremas obtidos são um teorema central do limite para o choque, seu coeficiente de difusão e uma fórmula exata para a variância do fluxo de partículas de classe N >1 para o processo em equilíbrio multiclasse. / We prove fluctuations results concerning fluxes of particles and tagged particles on multiclass Hammersley process. The methods used are robust and apply to other processes, in particular all the proofs can be adapted to the Multiclass totally asymmetric simple exclusion process (Multiclass TASEP) and its respective last passage percolation model. The main theorems obtained are a central limit theorem for the shock, its diffusion coefficient and an exact formula for the variance of the $N$-th class particle flux in a stationary version of the multiclass process when N > 1.

Nous considérons des jeux de congestion sur des graphes. Dans les jeux non-atomiques, nous considérons un ensemble de joueurs infinitésimaux. Chaque joueur veut aller d'un sommet à un autre en choisissant une route de coût minimal. Le coût de chaque route dépend du nombre de joueur la choisissant. Dans les jeux atomiques divisibles, nous considérons un ensemble de joueurs ayant chacun une demande à transférer d'un sommet à un autre, en la subdivisant éventuellement sur plusieurs routes. Dans ces jeux, un équilibre de Nash est atteint lorsque chaque joueur a choisi une stratégie de coût minimal. L'existence d'un équilibre de Nash est assurée sous de faibles hypothèses. Les principaux sujets sont l'unicité, le calcul, l'efficacité et la sensibilité de l'équilibre de Nash. De nombreux résultats sont connus dans le cas où les joueurs sont tous impactés de la même façon par la congestion. Le but de cette thèse est de généraliser ces résultats au cas où les joueurs ont des fonctions de coût différentes. Nous obtenons des résultats sur l'unicité de l'équilibre dans les jeux non-atomiques. Nous donnons deux algorithmes capables de calculer un équilibre dans les jeux non-atomiques lorsque les fonctions de coût sont affines. Nous obtenons une borne sur le prix de l'anarchie pour certains jeux atomiques divisibles et prouvons qu'il n'est pas borné en général, même lorsque les fonctions sont affines. Enfin, nous prouvons des résultats sur la sensibilité de l'équilibre par rapport à la demande dans les jeux atomiques divisibles / We consider congestion games on graphs. In nonatomic games, we are given a set of infinitesimal players. Each player wants to go from one vertex to another by taking a route of minimal cost, the cost of a route depending on the number of players using it. In atomic splittable games, we are given a set of players with a non-negligible demand. Each player wants to ship his demand from one vertex to another by dividing it among different routes. In these games, we reach a Nash equilibrium when every player has chosen a minimal-cost strategy. The existence of a Nash equilibrium is ensured under mild conditions. The main issues are the uniqueness, the computation, the efficiency and the sensitivity of the Nash equilibrium. Many results are known in the specific case where all players are impacted in the same way by the congestion. The goal of this thesis is to generalize these results in the case where we allow player-specific cost functions. We obtain results on uniqueness of the equilibrium in nonatomic games. We give two algorithms able to compute a Nash equilibrium in nonatomic games when the cost functions are affine. We find a bound on the price of anarchy for some atomic splittable games, and prove that it is unbounded in general, even when the cost functions are affine. Finally we find results on the sensitivity of the equilibrium to the demand in atomic splittable games

No presente trabalho, estudamos alguns sistemas de partículas interagentes que podem ser vistos como modelos simples de fluxo de tráfego, a saber: O Processo de Hammersley-Aldous-Diaconis e o Processo de Exclusão. Exploramos suas representações como modelos de crescimento no plano. Ênfase é dada aos casos em que há mais de um tipo de partícula, aos processos multiclasses e às suas relações com modelos de filas. Analogia entre os modelos é usada para provar os resultados. Por fim, damos uma nova prova para o cálculo da variância assintótica reescalonada do fluxo de partículas de segunda classe no processo de Hammersley multiclasse em equilíbrio. / In the present work we study the following interacting particle systems which can be seen as simple models of traffic flow: The Hammersley-Aldous-Diaconis Process and the Exclusion Process. We explore the related growth models in the plane. Focus is given to cases where there are more than one kind of particles, to the multitype processes and to their relations with queue models. Analogy between the models is used to prove the results. At last, we give a new proof for the calculation of the asimptotic flux of second class particles in the Multiclass Hammersley process in equilibrium.

Diversos problemas envolvem a classificação de dados em categorias, também denominadas classes. A partir de um conjunto de dados cujas classes são conhecidas, algoritmos de Aprendizado de Máquina (AM) podem ser utilizados na indução de um classificador capaz de predizer a classe de novos dados do mesmo domínio, realizando assim a discriminação desejada. Dentre as diversas técnicas de AM utilizadas em problemas de classificação, as Máquinas de Vetores de Suporte (Support Vector Machines - SVMs) se destacam por sua boa capacidade de generalização. Elas são originalmente concebidas para a solução de problemas com apenas duas classes, também denominados binários. Entretanto, diversos problemas requerem a discriminação dos dados em mais que duas categorias ou classes. Nesta Tese são investigadas e propostas estratégias para a generalização das SVMs para problemas com mais que duas classes, intitulados multiclasses. O foco deste trabalho é em estratégias que decompõem o problema multiclasses original em múltiplos subproblemas binários, cujas saídas são então combinadas na obtenção da classificação final. As estratégias propostas visam investigar a adaptação das decomposições a cada aplicação considerada, a partir de informações do desempenho obtido em sua solução ou extraídas de seus dados. Os algoritmos implementados foram avaliados em conjuntos de dados gerais e em aplicações reais da área de Bioinformática. Os resultados obtidos abrem várias possibilidades de pesquisas futuras. Entre os benefícios verificados tem-se a obtenção de decomposições mais simples, que requerem menos classificadores binários na solução multiclasses. / Several problems involve the classification of data into categories, also called classes. Given a dataset containing data whose classes are known, Machine Learning (ML) algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, thus performing the desired discrimination. Among the several ML techniques applied to classification problems, the Support Vector Machines (SVMs) are known by their high generalization ability. They are originally conceived for the solution of problems with only two classes, also named binary problems. However, several problems require the discrimination of examples into more than two categories or classes. This thesis investigates and proposes strategies for the generalization of SVMs to problems with more than two classes, known as multiclass problems. The focus of this work is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are then combined to obtain the final classification. The proposed strategies aim to investigate the adaptation of the decompositions for each multiclass application considered, using information of the performance obtained for its solution or extracted from its examples. The implemented algorithms were evaluated on general datasets and on real applications from the Bioinformatics domain. The results obtained open possibilities of many future work. Among the benefits observed is the obtainment of simpler decompositions, which require less binary classifiers in the multiclass solution.

Made available in DSpace on 2016-12-12T20:22:54Z (GMT). No. of bitstreams: 1 Juliana P Detroz.pdf: 11151863 bytes, checksum: f8e2db7d1e13c674adf28e9484a35d9d (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the emerging hydric crisis, water shortage has been a great global concern. Water supply companies have been increasingly looking for solutions to reduce water wastage and many efforts have been made aiming to promote a better management of this resource. Fraud detection is one of these actions, as the irregular violations are usually held precariously, thus, causing leaks. Hidden and apparent leakage is a major cause of the high water loss rates. In this context, the use of technology in order to automate the identification of potential frauds can be an important support tool to avoid water waste. In this sense, this research aims to apply pattern recognition techniques in the implementation of an automated detection of suspected irregularities cases in water meters, through image analysis. We considered as a potential fraud when there is evidences of violations and seals absences. The proposed computer vision system is composed by three steps: the detection of the water meter location, obtained by OPF classifier and HOG descriptor, detecting the seals through morphological image processing and segmentation methods; and the classification of frauds, in which the condition of the water meter seals is assessed. We validated the proposed framework using a dataset containing images of water meter inspections. The water meter detection solution (HOG+OPF) achieved an average accuracy of 89.03%, showing superior results than SVM (linear and RBF). A comparative analysis of 12 feature descriptors (color and texture) was performed on the classification of the seals condition step. The results of these methods were evaluated individually and also combined, reaching average accuracy up to 81.29%. We concluded that the use of a computer vision system is a promising strategy and has potential to benefit and support the analysis of fraud detection. / Em tempos de racionamento dos recursos hídricos, o desperdício de água tem sido um tema de relevância mundial. Os vazamentos ocultos e aparentes são uma das principais causas dos elevados índices de perdas de água tratada. Esforços são despendidos pelas companhias de saneamento a fim de reduzir as perdas, sendo o combate às fraudes uma destas ações. Neste contexto, o uso da tecnologia para automatizar a identificação de fraude mostra-se uma importante ferramenta de apoio no combate ao desperdício. Esta pesquisa tem como objetivo aplicar técnicas de reconhecimento de padrões na detecção automatizada de casos suspeitos de irregularidades em hidrômetros. No escopo deste trabalho foram consideradas suspeitas de fraude as violações e ausências de lacres. A abordagem proposta visa, através de um sistema de visão computacional, auxiliar no combate a fraudes em hidrômetros e, consequentemente, evitar o desperdício de água associado a estas. Para isto, a execução do sistema proposto é dividida em três etapas: detecção do hidrômetro, fazendo uso do classificador OPF e descritor HOG; a detecção da área estimada dos lacres, obtida pela aplicação de métodos de processamento morfológico e segmentação; e a classificação das fraudes a partir da condição dos lacres do hidrômetro. A validação foi executada utilizando-se um conjunto de imagens de fiscalizações. Na primeira etapa, a solução utilizando o classificador OPF alcançou taxa de acerto média de 89, 03%, sendo superior a resultados dos métodos SVM linear e RBF. Para a classificação da condição dos lacres, realizou-se uma análise comparativa de 12 descritores de imagem, de cor e textura, sendo avaliados os resultados individuais e combinados, atingindo taxas de acerto média de até 81, 29%. Com isto, pode-se concluir que o uso de um sistema especialista de visão computacional para o problema de detecção de fraudes é uma estratégia promissora e com potencial para beneficiar a análise e o suporte à tomada de decisões.

No presente trabalho, estudamos alguns sistemas de partículas interagentes que podem ser vistos como modelos simples de fluxo de tráfego, a saber: O Processo de Hammersley-Aldous-Diaconis e o Processo de Exclusão. Exploramos suas representações como modelos de crescimento no plano. Ênfase é dada aos casos em que há mais de um tipo de partícula, aos processos multiclasses e às suas relações com modelos de filas. Analogia entre os modelos é usada para provar os resultados. Por fim, damos uma nova prova para o cálculo da variância assintótica reescalonada do fluxo de partículas de segunda classe no processo de Hammersley multiclasse em equilíbrio. / In the present work we study the following interacting particle systems which can be seen as simple models of traffic flow: The Hammersley-Aldous-Diaconis Process and the Exclusion Process. We explore the related growth models in the plane. Focus is given to cases where there are more than one kind of particles, to the multitype processes and to their relations with queue models. Analogy between the models is used to prove the results. At last, we give a new proof for the calculation of the asimptotic flux of second class particles in the Multiclass Hammersley process in equilibrium.

Diversos problemas envolvem a classificação de dados em categorias, também denominadas classes. A partir de um conjunto de dados cujas classes são conhecidas, algoritmos de Aprendizado de Máquina (AM) podem ser utilizados na indução de um classificador capaz de predizer a classe de novos dados do mesmo domínio, realizando assim a discriminação desejada. Dentre as diversas técnicas de AM utilizadas em problemas de classificação, as Máquinas de Vetores de Suporte (Support Vector Machines - SVMs) se destacam por sua boa capacidade de generalização. Elas são originalmente concebidas para a solução de problemas com apenas duas classes, também denominados binários. Entretanto, diversos problemas requerem a discriminação dos dados em mais que duas categorias ou classes. Nesta Tese são investigadas e propostas estratégias para a generalização das SVMs para problemas com mais que duas classes, intitulados multiclasses. O foco deste trabalho é em estratégias que decompõem o problema multiclasses original em múltiplos subproblemas binários, cujas saídas são então combinadas na obtenção da classificação final. As estratégias propostas visam investigar a adaptação das decomposições a cada aplicação considerada, a partir de informações do desempenho obtido em sua solução ou extraídas de seus dados. Os algoritmos implementados foram avaliados em conjuntos de dados gerais e em aplicações reais da área de Bioinformática. Os resultados obtidos abrem várias possibilidades de pesquisas futuras. Entre os benefícios verificados tem-se a obtenção de decomposições mais simples, que requerem menos classificadores binários na solução multiclasses. / Several problems involve the classification of data into categories, also called classes. Given a dataset containing data whose classes are known, Machine Learning (ML) algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, thus performing the desired discrimination. Among the several ML techniques applied to classification problems, the Support Vector Machines (SVMs) are known by their high generalization ability. They are originally conceived for the solution of problems with only two classes, also named binary problems. However, several problems require the discrimination of examples into more than two categories or classes. This thesis investigates and proposes strategies for the generalization of SVMs to problems with more than two classes, known as multiclass problems. The focus of this work is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are then combined to obtain the final classification. The proposed strategies aim to investigate the adaptation of the decompositions for each multiclass application considered, using information of the performance obtained for its solution or extracted from its examples. The implemented algorithms were evaluated on general datasets and on real applications from the Bioinformatics domain. The results obtained open possibilities of many future work. Among the benefits observed is the obtainment of simpler decompositions, which require less binary classifiers in the multiclass solution.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-13T19:50:34Z No. of bitstreams: 1 CHRISTIANE FERREIRA LEMOS LIMA - TESE PPGEE 2013..pdf: 5704501 bytes, checksum: da700470760daace1ac791c6514082a3 (MD5) / Made available in DSpace on 2018-08-13T19:50:34Z (GMT). No. of bitstreams: 1 CHRISTIANE FERREIRA LEMOS LIMA - TESE PPGEE 2013..pdf: 5704501 bytes, checksum: da700470760daace1ac791c6514082a3 (MD5) Previous issue date: 2013-04-19 / Capes / Este trabalho de tese tem como objetivo principal apresentar um novo esquema, direcionado à proteção de sistemas computacionais contra a ocorrência de invasões, fazendo uso de códigos corretores de erros e de medidas de informação. Para isto, considera-se que a identificação de diferentes tipos de ataques a uma rede de computadores pode ser vista como uma tarefa de classificação multiclasses, por envolver a discriminação de ataques em diversos tipos ou categorias. Com base nessa abordagem, o presente trabalho apresenta uma estratégia para classificação multiclasses, baseada nos princípios dos códigos corretores de erros, tendo em vista que para cada uma dasM classes do problema proposto é associada a um conjunto de palavras códigos de comprimento igual a N, em que N é o número de atributos, selecionados por meio de medidas de informação, e que serão monitorados por dispositivos de software, aqui chamados de detectores de rede e detectores dehost. Nesta abordagem, as palavras código que formam uma tabela são restritas a um sub-código de um código linear do tipo BCH (Bose-ChaudhuriHocquenghem), permitindo que a etapa de decodificação seja realizada, utilizando-se algoritmos de decodificação algébrica, o que não é possível para palavras código selecionadas aleatoriamente. Nesse contexto, o uso de uma variante de algoritmo genético é aplicado no projeto da tabela que será utilizada na identificação de ataques em redes de computadores. Dentre as contribuições efetivas desta tese, cujas comprovações são demonstradas em experimentos realizados por simulação computacional, tem-se a aplicação da teoria da codificação para a determinação de palavras código adequadas ao problema de detectar intrusões numa rede de computadores; a determinação dos atributos por meio do uso de árvores de decisão C4.5 baseadas nas medidas de informação de Rényi e Tsallis; a utilização de decodificação algébrica, baseado nos conceitos de decodificação tradicional e na decodificação por lista. / The thesis’s main objective is to present a scheme to protect computer networks against the occurrence of invasions by making use of error correcting codes and information measures. For this, the identification of attacks in a network is viewed as a multiclass classification task because it involves attacks discrimination into various categories. Based on this approach, this work presents strategies for multiclass problems based on the error correcting codes principles, where eachM class is associated with a codeword of lengthN, whereN is the number of selected attributes, chosen by use of information measures. These attributes are monitored by software devices, here called network detectors and detectors host. In this approach, the codewords that form a codewords table are a sub-code of a BCH-type linear code. This approach allows decoding step to be performed using algebraic decoding algorithms, what is not possible with random selected codewords. In this context, the use of a variant of genetic algorithm are applied in the table-approach design to be used in attacks identification in networks. The effective contributions of this thesis, demonstrated on the cientific experiments, are: the application of coding theory to determine the appropriate code words to network intrusion detection; the application of C4.5 decision tree based on information measurements of Rényi and Tsallis for attributes selection; the use of algebraic decoding, based on the concepts of the traditional decoding and list decoding techniques.