Métodos de inferencia basados en búsqueda heurística para cadenas de clasificadores probabilísticos

Resumen

En la clasificación multietiqueta, una instancia puede ser etiquetada con varias de las etiquetas o clases de un conjunto predefinido, frente a la clasificación multiclase en la que solo es posible asignar una de esas clases. Varios problemas reales caen en este tipo de tarea de aprendizaje, por ejemplo, asignación de etiquetas a recursos en redes sociales, detección de objetos en imágenes o diagnóstico médico. Por lo general, la presencia de una etiqueta puede depender de la probabilidad con la que otras se produzcan. De hecho, la existencia de esta dependencia ha despertado gran interés entre los investigadores que se han dedicado a estudiar varios tipos de relaciones entre las etiquetas y la manera de explotarlas, prestando mayor atención en la dependencia condicional, que captura la probabilidad de que ciertas etiquetas sean relevantes a partir de la descripción de cada instancia. El método Probabilistic Classifier Chains (PCC) ha ganado interés debido a su prometedora propiedad de estimar la probabilidad conjunta condicional y obtener así predicciones óptimas en términos de la medida subset 0/1 loss. Sin embargo, el método PCC original sufre de un alto coste computacional, debido a que realiza una búsqueda exhaustiva que explora todas las posibles soluciones para finalmente quedarse con la mejor. Por ello, algunos investigadores han centrado sus estudios en diseñar alternativas de inferencia eficientes que eviten explorar todas las posibles soluciones. El algoritmo ε-Approximate (ε-A), el algoritmo Beam Search (BS) y los métodos basados en Monte Carlo son técnicas que surgieron como alternativas a la búsqueda exhaustiva, aunque solamente el algoritmo ε-A con ε=0 garantiza teóricamente alcanzar una solución óptima. Este trabajo continua en esta línea estudiando la posibilidad de utilizar el algoritmo A* como método alternativo para realizar inferencia en PCC. Su interés radica en que este algoritmo proporciona soluciones óptimas si el heurístico de búsqueda es admisible. Esta tesis propone dos familias de heurísticos admisibles que garantizan que A*, al igual que ε-A con ε=0, teóricamente alcance soluciones óptimas. Así mismo, el diseño de estos heurísticos ha sido cuidadoso para que además de ser admisibles, sean lo más dominantes posibles para permitir obtener soluciones óptimas sin explorar demasiadas soluciones. La primera familia de heurísticos diseñada solo es aplicable cuando los clasificadores base son lineales. Esta asunción de linealidad se realiza en un intento por conseguir una solución de compromiso entre, un heurístico admisible que pueda calcularse con la máxima profundidad para incrementar su dominancia, pero que a la vez sea computacionalmente tratable. Adicionalmente, se incluyó en este heurístico un parámetro de profundidad que nos permite controlar su nivel de dominancia y su complejidad computacional, logrando con ello que la inferencia mediante el algoritmo A* sea más competitiva. La segunda familia de heurísticos surge para evitar la limitación del primer grupo de heurísticos de ser únicamente viables para clasificadores base lineales. La propuesta consiste en realizar una búsqueda exhaustiva pero de profundidad limitada por un parámetro, que de nuevo reduce su dominancia, pero permite que computacionalmente sea viable. Los experimentos, realizados sobre varios conjuntos de datos de referencia muestran que el algoritmo A* con las familias de heurísticos propuestos alcanza predicciones óptimas y exploran menos nodos que otros métodos de la literatura. A pesar de esto, no es tan rápido como el algoritmo ε-A con ε=0 cuando la búsqueda es altamente dirigida, debido al coste del cálculo del heurístico. Sin embargo, muestran su potencial cuando los conjuntos de datos presentan más incertidumbre, logrando en estos casos hacer predicciones más rápidas que el resto de métodos existentes en la literatura. In multi-label classification, a subset of a predefined set of labels or classes can be assigned to an instance unlike multi-class classification where just one class can be assigned. Several real problems fall into this type of learning task. For example, assigning tags to resources in social networks, detecting objects in images or medical diagnosis. In general, the presence of a label may depend on the likelihood that others occur. In fact, this dependence has aroused great interest among researchers, who study various types of relationships between tags and how to exploit them, especially focusing on conditional dependence, which captures the probability that certain tags are relevant from the description of an instance. The Probabilistic Classifier Chains (PCC) method has gained interest because of its promising property of being able to estimate the conditional joint probability, thus obtaining optimal predictions in terms of the measure subset 0/1 loss. However, the original PCC method suffers from a high computational cost, because it performs an exhaustive search that explores all possible solutions before taking one of the best ones. That is the reason why some researchers focused on designing efficient inference alternatives that avoid exploring all possible solutions. The ε-Approximate (ε-A) algorithm, the Beam Search (BS) algorithm and the Monte Carlo sampling methods arose as alternatives to the exhaustive search, but only the ε-A algorithm with ε=0 theoretically guarantees reaching an optimal solution in terms of subset 0/1 loss. This work continues in this line, studying the possibility of using the algorithm A* as an alternative to perform inference in PCC. Its interest lies in that this algorithm guarantees optimal solutions if the search heuristic is admissible. This thesis proposes two families of admissible heuristics that makes A* theoretically guarantee optimal solutions, as ε-A algorithm with ε=0. Also, the design of the heuristics has been careful in order to make them be both admissible and as dominant as possible so that optimal solutions are reached without exploring too many solutions. The first family of heuristics designed is just suitable when the base classifiers are linear. This linearity assumption intends to obtain a trade-off solution between an admissible heuristic that can be computed for the maximum depth, increasing its dominance, and a computationally tractable heuristic. In fact, a depth parameter was included in the heuristic to control its dominance and its computational cost, making A* algorithm more competitive in terms of computational cost. The second family of heuristics arises to avoid the limitation of only being viable for linear base classifiers. The proposal is to perform an exhaustive search, but limiting the depth of the search by a parameter to make the heuristic be computationally viable, although at the cost of reducing its dominance. Experiments performed on several benchmark datasets show that the algorithm A* with the proposed families of heuristics reaches optimum predictions for subset 0/1 loss and explores fewer nodes than other methods in the literature. Despite this fact, it is not so fast as the ε-A algorithm with ε=0 when the search is highly directed. However, they show their potential when the data sets present more uncertainty, providing in this case faster predictions than the rest of methods in the literature.