ON THE SIMULTANEOUS MINIMIZATION OF WORST TESTING COST AND EXPECTED TESTING COST WITH DECISION TREES
| Autor: | ALINE MEDEIROS SAETTLER |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Zdroj: | Repositório Institucional da PUC_RIOPontifícia Universidade Católica do Rio de JaneiroPUC_RIO. |
| Druh dokumentu: | masterThesis |
| Popis: | PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR PROGRAMA DE EXCELENCIA ACADEMICA O problema de minimizar o custo de avaliar uma função discreta lendo sequencialmente as suas variáveis é um problema que surge em diversas aplicações, entre elas sistemas de diagnóstico automático e aprendizado ativo. Neste problema, cada variável da função está associada a um custo, que se deve pagar para checar o seu valor. Além disso, pode existir uma distribuição de probabilidades associadas aos pontos onde a função está definida. A maioria dos trabalhos nesta área se concentra ou na minimização do custo máximo ou na minimização do custo esperado gasto para avaliar a função. Nesta dissertação, mostramos como obter uma Ômicron logaritmo de N aproximação em relação à minimização do pior custo (a melhor aproximação possível assumindo que P é diferente de NP). Nós também mostramos um procedimento polinomial para avaliar uma função otimizando simultaneamente o pior custo e o custo esperado. The problem of minimizing the cost of evaluating a discrete function by sequentially reading its variables is a problem that arises in several applications, among them automatic diagnosis design and active learning. In this problem, each variable of the function is associated with a cost, that we have to pay in order to check its value. In addition, there may exist a probability distribution associated with the points where the function is defined. Most of the work in the area has focussed either on the minimization of the maximum cost or on the minimization of the expected cost spent to evaluate the function. In this dissertation, we show how to obtain an Ômicron logarithm of N approximation with respect to the worst case minimization (the best possible approximation under the assumption that P is different from NP). We also show a polynomial time procedure for evaluate a function that simultaneously optimizes both the worst and the expected costs. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|