FenixEdu™

Dissertação

{en_GB=Learning the Leader-Follower Structure from Data Streams} {} EVALUATED

Detalhes: {pt=Muitas aplicações geram uma enorme quantidade de dados constituídos por sinais cuja evolução resulta de uma estrutura subjacente. Esta estrutura, quando conhecida, permite não só compreender melhor os dados como pode ser explorada para tarefas de inferência. Esta tese foca-se numa estrutura de líderes-seguidores, em que um pequeno subconjunto dos sinais (líderes) determina a acção dos restantes (seguidores). O objetivo principal é identificar os líderes e os parâmetros que explicam a influência dos líderes nos seguidores, expondo a estrutura subjacente aos dados. Considera-se duas restrições que incorporam informação prévia: restrições nos parâmetros e um limite superior no número de líderes. Começa-se por resolver o problema no qual cada seguidor tem o seu próprio conjunto de líderes. Formula-se o problema como uma optimização não convexa e propõe-se heurísticas baseadas numa relaxação convexa para o resolver. De seguida, aborda-se o problema de encontrar um único conjunto de líderes para todos os sinais. Propõe-se duas estratégias: a primeira resolve o primeiro problema para cada sinal e realiza uma votação para selecionar os líderes globais, a segunda estende as heurísticas propostas para realizar a inferência com todos os sinais. Para ambos os problemas, apresentam-se experiências que mostram um desempenho superior face a métodos adaptados da literatura. Para além disso, as heurísticas propostas podem ser aplicadas eficientemente usando algoritmos Frank-Wolfe, tornando-as atrativas para redes de maiores dimensões. Por fim, este trabalho é estendido em diferentes direções, lidando com observações em falta e mostrando a flexibilidade dos métodos através da sua aplicação em problemas distintos., en=A common objective of modern applications is to make sense of large streams of information. Such data is usually constituted by signals that evolve according to some underlying structure that, once known, allows not only to understand the data but also to carry inference tasks. This work focus on a leader-follower structure, where a small subset of signals (leaders) drives the remaining ones (followers). The main goal is to identify the leaders and the parameters representing the influence of leaders on followers, extracting the underlying graph of relationships. Two restrictions incorporating prior information are considered: constraints on the parameters and an upper-bound on the number of leaders. We start by solving the problem where each follower has its own set of leaders. We formulate it as a nonconvex optimization problem and propose heuristics based on a convex relaxation to solve it. We then approach the problem of finding a shared set of leaders for all signals. Two strategies are proposed: one solves the first problem for each signal and performs a voting to select the global leaders, the other extends the proposed heuristics to perform the inference with all network signals. For both problems, experiments show improved performance over methods adapted from the literature. Moreover, the proposed heuristics can be efficiently applied using Frank-Wolfe algorithms, rendering them attractive for larger networks. Finally, this work is extended in different ways, dealing with missing data and applying our methods in a wider range of setups, thus showing their flexibility.}
Keywords: {pt=Relações Líder-Seguidor, Identificação de Redes Causais, Redes Esparsas, Identificação de Líderes, Problemas de Optimização Convexos, Algoritmos Frank-Wolfe, en=Leader-Follower Relationships, Causal Graph Identification, Sparse Networks, Leadership Identification, Convex Optimization Problems, Frank-Wolfe Algorithms}

Discussão: novembro 27, 2019, 11:30