En el presente trabajo, se estudian las propiedades del método de estimación no paramétrico en un modelo de “Enfermedad - Muerte" de proceso de Markov. Este modelo posee tres estados 1, 2 y 3 correspondientes a “salud", “enfermedad" y “muerte" respectivamente y solo admite las transiciones de 1-2, 1-3 y 2-3, asimismo a este proceso se le denomina de Markov porque la probabilidad de transición de un estado a otro es independiente del tiempo de permanencia en el estado inicial. Las funciones de tiempo de muerte y enfermedad, así como la función de riesgo de muerte dada la enfermedad son los parámetros del modelo \Enfermedad - Muerte". Sin embargo la estimación de estas funciones del modelo no es directa pues existen dos formas de censura en los datos: los intervalos censurados y la pérdida de estados de transición; por lo que se utiliza un algoritmo de autoconsistencia para calcular estos estimadores. Los intervalos censurados y la pérdida de estados de transición se generan porque los pacientes son evaluados periódicamente. En un intervalo censurado (t1 , t2) se conoce que la enfermedad ocurrió entre un tiempo t1 y t2 pero no el momento exacto, mientras que para la pérdida de estados de transición se sabe que la enfermedad no ha ocurrido hasta la última medición pero se desconoce si la enfermedad ocurre entre esta última medición y el tiempo final del estudio. En la aplicación del modelo \Enfermedad - Muerte" de proceso de Markov a una base de clientes de una administradora de fondos de pensiones (AFP) se consideran los intervalos censurados para los reclamos de los clientes, as__ como la pérdida de estados de transición para los traspasos. Modelar los tiempos de traspaso y de reclamo de los afiliados bajo un proceso de Markov \Enfermedad - Muerte" con intervalos censurados y pérdida de estados de transición intermedia, aumenta la precisión de los estimadores de las funciones de tiempo y riesgo. / Tesis

Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / La prevención del crimen ha ganado cada vez más espacio e importancia entre las políticas públicas en seguridad ciudadana, tanto en Chile como en el mundo. Durante la investigación realizada en este trabajo, se desarrolla un modelo para predecir los crímenes sobre una ciudad, que incluye el efecto de intervenciones preventivas y que permite además estudiar el fenómeno de desplazamiento que se le atribuye a este tipo de medidas. Ambos aspectos incluidos rara vez en los modelos de predicción revisados en la literatura. La estructura utilizada corresponde a un modelo de Markov oculto, donde el atractivo de un lugar para cometer un tipo específico de crimen se considera oculto y se estudia a través de el registro de crímenes observados en dicho lugar, considerando el efecto que intervenciones policiales podrían tener. De manera de demostrar el tipo de información y uso que se puede hacer del modelo desarrollado, se aplicó éste en un caso de estudio. Los datos de los crímenes y vigilancia policial utilizados se obtuvieron mediante un simulador del crimen sobre una ciudad ficticia. El modelo estimado, permitió comparar el efecto de la vigilancia en el lugar donde es ubicada, así como en las áreas aledañas, según el atractivo de cada lugar. Encontrándose que las celdas más atractivas son más susceptibles a esta vigilancia, tanto en la reducción de crímenes esperados al posicionarse un vigilante en un lugar, como en el aumento de la tasa de crímenes cuando un policía es ubicado en lugares aledaños. A partir de las matrices de transición se clasificaron las unidades de estudio, que componen la ciudad virtual, según su potencial para pasar a un estado de alta atractividad. Donde le grupo más numeroso corresponde al de celdas, de Bajo y Mediano Potencial, que permanecen en el mínimo estado de atractividad, reportando pocos crímenes en el lugar. Por el contrario, aquellas celdas, de Alto Potencial, que tienen probabilidades significativas de llegar y permanecer en estados de alta atractividad es el grupo menos numeroso, y el que además suele concentrar los crímenes. Esto se alinea con lo que sugiere la literatura respecto a unos pocos lugares concentrado la mayoría de los crímenes. Para validar el modelo se comparó su ajuste y predicciones con los obtenidos de otros cuatro modelos con diferentes especificaciones y estructuras (HMM Homogéneo, Clases Latentes, Regresión de Poisson y Persistencia), obteniendo mejores tasas de aciertos en la predicción de los crímenes futuros, de alrededor del 97%. Además el modelo destaca prediciendo los crímenes de las celdas de Alto Potencial, respecto a los modelos alternativos, alcanzando tasas de aciertos de 97% en comparación con las obtenidas por los otros cuatro modelos: 78%, 92%, 48% y 34% respectivamente. Se concluye además, en el experimento, que la inclusión del efecto de la policía permite capturar mejor el fenómeno delictivo, mejorando el desempeño al predecir el número de crímenes. Finalmente, en relación a los objetivos planteados en este trabajo, se puede concluir que el modelo HMM desarrollado logra incorporar de forma efectiva los dos atributos que se deseaban estudiar en el fenómeno delictivo: considerar la atractividad de forma dinámica,actualizándose período a período, e incluir el efecto de la vigilancia en la predicción.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Hidden Markov models (HMM) han sido ampliamente usados para modelar comportamientos dinámicos tales como atención del consumidor, navegación en internet, relación con el cliente, elección de productos y prescripción de medicamentos por parte de los médicos. Usualmente, cuando se estima un HMM simultáneamente para todos los clientes, los parámetros del modelo son estimados asumiendo el mismo número de estados ocultos para cada cliente. Esta tesis busca estudiar la validez de este supuesto identificando si existe un potencial sesgo en la estimación cuando existe heterogeneidad en el número de estados. Para estudiar el potencial sesgo se realiza un extenso ejercicio de simulación de Monte Carlo. En particular se estudia: a) si existe o no sesgo en la estimación de parámetros, b) qué factores aumentan o disminuyen el sesgo, y c) qué métodos pueden ser usados para estimar correctamente el modelo cuando existe heterogeneidad en el número de estados. En el ejercicio de simulación, se generan datos utilizando un HMM con dos estados para el 50% de clientes y un HMM con tres estados para el 50% restante. Luego, se utiliza un procedimiento MCMC jerárquico Bayesiano para estimar los parámetros de un HMM con igual número de estados para todos los clientes. En cuanto a la existencia de sesgo, los resultados muestran que los parámetros a nivel individual son recuperados correctamente, sin embargo los parámetros a nivel agregado correspondientes a la distribución de heterogeneidad de los parámetros individuales deben ser reportados cuidadosamente. Esta dificultad es generada por la mezcla de dos segmentos de clientes con distinto comportamiento. En cuanto los factores que afectan el sesgo, los resultados muestran que: 1) cuando la proporción de clientes con dos estados aumenta, el sesgo de los resultados agregados también aumenta; 2) cuando se incorpora heterogeneidad en las probabilidades condicionales, se generan estados duplicados para los clientes con 2 estados y los estados no representan lo mismo para todos los clientes, incrementando el sesgo a nivel agregado; y 3) cuando el intercepto de las probabilidades condicionales es heterogéneo, incorporar variables exógenas puede ayudar a identificar los estados igualmente para todos los clientes. Para reducir los problemas mencionados se proponen dos enfoques. Primero, usar una mezcla de Gaussianas como distribución a priori para capturar heterogeneidad multimodal, y segundo usar un modelo de clase latente con HMMs de distintos número de estados para cada clase. El primer modelo ayuda en representar de mejor forma los resultados agregados. Sin embargo, el modelo no evita que existan estados duplicados para los clientes con menos estados. El segundo modelo captura la heterogeneidad en el número de estados, identificando correctamente el comportamiento a nivel agregado y evitando estados duplicados para clientes con dos estados. Finalmente, esta tesis muestra que en la mayoría de los casos estudiados, el supuesto de un número fijo de estados no genera sesgo a nivel individual cuando se incorpora heterogeneidad. Esto ayuda a mejorar la estimación, sin embargo se deben tomar precauciones al realizar conclusiones usando los resultados agregados.

Orientador: Mário Hissamitsu Tarumoto / Resumo: A observação de fenômenos naturais, como as mudanças de temperatura é bastante frequente no mundo atual, de forma que vários estudos têm sido realizados com o intuito de prever a ocorrência delas tendo em vista o que ocorreu no passado. Estudos desta natureza, em que a coleta de dados ocorre de forma contínua, seja por medida horária ou diária, não apresenta independência entre as observações. Entre as possíveis formas de análise, há a aplicação de técnicas de séries temporais ou também a teoria dos valores extremos. No entanto, um dos objetivos deste estudo é construir uma matriz de transição, de tal forma que possamos determinar a probabilidade, por exemplo, de alta temperatura amanhã, dado que hoje foi observado este fenômeno. Para a obtenção deste resultado, uma possibilidade é construir um modelo baseado em dados dependentes que seguem um processo de Markov, em que a suposição é de que exista dependência somente com o dia anterior. Neste trabalho, pretendemos construir este modelo e realizar a aplicação em dados de temperatura na cidade de Presidente Prudente-SP no período de janeiro de 2011 a dezembro de 2016. Posteriormente vamos realizar comparações entre o modelo markoviano de nido a partir da distribuição Weibull bivariada de Marshall e Olkin e outros modelos markovianos de nidos a partir das funções cópulas. / Abstract: The observation of natural phenomena, such as temperature changes, is quite frequent in the world today, so that several studies have been carried out with the intention of predicting their occurrence in view of what has happened in the past. Data of this nature, in which the data collection occurs continuously, whether by hourly or daily measurement, does not present independence between observations. Among the possible forms of analysis is the application of time-series techniques, however, the purpose of this study is to construct a transition matrix, so that we can determine the probability, for example, of high temperature tomorrow, since today this phenomenon was observed. To obtain this result, one possibility is to construct a model based on dependent data that follows a Markov process, in which the assumption is that there is dependence only with the previous day. In this work, we intend to build this model and perform the application on temperature data in the city of Presidente Prudente-SP from January 2011 to December 2016. For which comparisons were made between the Markovian model de ned from the distribution Weibull bivariate of Marshall and Olkin and other Markovian models de ned from the copula functions. / Mestre

Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

Dissertação apresentada para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Professor Doutor Diamantino Rui da Silva Freitas

Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

En el presente trabajo, se estudian las propiedades del método de estimación no paramétrico en un modelo de “Enfermedad - Muerte" de proceso de Markov. Este modelo posee tres estados 1, 2 y 3 correspondientes a “salud", “enfermedad" y “muerte" respectivamente y solo admite las transiciones de 1-2, 1-3 y 2-3, asimismo a este proceso se le denomina de Markov porque la probabilidad de transición de un estado a otro es independiente del tiempo de permanencia en el estado inicial. Las funciones de tiempo de muerte y enfermedad, así como la función de riesgo de muerte dada la enfermedad son los parámetros del modelo \Enfermedad - Muerte". Sin embargo la estimación de estas funciones del modelo no es directa pues existen dos formas de censura en los datos: los intervalos censurados y la pérdida de estados de transición; por lo que se utiliza un algoritmo de autoconsistencia para calcular estos estimadores. Los intervalos censurados y la pérdida de estados de transición se generan porque los pacientes son evaluados periódicamente. En un intervalo censurado (t1 , t2) se conoce que la enfermedad ocurrió entre un tiempo t1 y t2 pero no el momento exacto, mientras que para la pérdida de estados de transición se sabe que la enfermedad no ha ocurrido hasta la última medición pero se desconoce si la enfermedad ocurre entre esta última medición y el tiempo final del estudio. En la aplicación del modelo \Enfermedad - Muerte" de proceso de Markov a una base de clientes de una administradora de fondos de pensiones (AFP) se consideran los intervalos censurados para los reclamos de los clientes, as__ como la pérdida de estados de transición para los traspasos. Modelar los tiempos de traspaso y de reclamo de los afiliados bajo un proceso de Markov \Enfermedad - Muerte" con intervalos censurados y pérdida de estados de transición intermedia, aumenta la precisión de los estimadores de las funciones de tiempo y riesgo.

Made available in DSpace on 2015-03-03T15:22:32Z (GMT). No. of bitstreams: 1 FranciscoMCM.pdf: 1391370 bytes, checksum: 2bdc2511202e3397ea85e69a321f5847 (MD5) Previous issue date: 2010-02-10 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / In this work we study the Hidden Markov Models with finite as well as general state space. In the finite case, the forward and backward algorithms are considered and the probability of a given observed sequence is computed. Next, we use the EM algorithm to estimate the model parameters. In the general case, the kernel estimators are used and to built a sequence of estimators that converge in L1-norm to the density function of the observable process / Neste trabalho estudamos os modelos de Markov ocultos tanto em espa?o de estados finito quanto em espa?o de estados geral. No caso discreto, estudamos os algoritmos para frente e para tr?s para determinar a probabilidade da sequ?ncia observada e, em seguida, estimamos os par?metros do modelo via algoritmo EM. No caso geral, estudamos os estimadores do tipo n?cleo e os utilizamos para conseguir uma sequ?ncia de estimadores que converge na norma L1 para a fun??o densidade do processo observado

Para diagnosticar un cáncer se realiza, entre otras pruebas, algún test de imagen, como puede ser una radiografía, ecografía o resonancia magnética. Mediante estos tests pueden detectarse zonas con alta sospecha tumoral, cuyo diagnóstico debe confirmase finalmente mediante la realización de una biopsia. Este tipo de imágenes, sin embargo, no son fáciles de interpretar, lo que provoca que el profesional encargado de analizarlas, a pesar de su experiencia, no sea capaz de detectar en ellas un porcentaje importante de tumores (falsos negativos). Una posibilidad para mejorar el diagnóstico y disminuir el número de falsos negativos consiste en utilizar sistemas de diagnóstico asistido por ordenador o computer-aided diagnosis (CAD). Un sistema de CAD analiza la imagen médica y trata de detectar zonas sospechosas de contener alguna anomalía. Estas zonas son marcadas sobre la propia imagen con un doble objetivo: llamar la atención del profesional encargado de analizarla hacia la zona sospechosa y aportar una segunda opinión respecto al diagnóstico. En esta tesis se presentan y evaluan diversas técnicas de visión por computador y reconocimiento de formas orientadas a la detección de tumores en imágenes médicas, con el objetivo de diseñar sistemas de CAD que permitan un mejor diagnóstico. El trabajo se ha centrado en el diagnóstico de cáncer de próstata a partir de imágenes de ecografía, y en el diagnóstico de cáncer de mama a partir de imágenes de radiografía. Se han evaluado diversos métodos de extracción de características basados en la intensidad, frecuencia, texturas o en gradientes. En la etapa de clasificación se ha utilizado un clasificador no paramétrico basado en distancias (k-vecinos más cercanos) y otro paramétrico basado en modelos de Markov. A lo largo del trabajo se evidencian las distintas problemáticas que surgen en este tipode tareas y se proponen soluciones a cada una de ellas. El diagnóstico de cáncer de próstata asistido por ordenador es una tarea extrema / Llobet Azpitarte, R. (2006). Aportaciones al diagnóstico de cáncer asistido por ordenador [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1862