descubrimiento de la verdad

Proceso de elección del valor real real de un elemento de datos.

El descubrimiento de la verdad (también conocido como búsqueda de la verdad ) es el proceso de elegir el valor real de un elemento de datos cuando diferentes fuentes de datos proporcionan información contradictoria al respecto.

Se han propuesto varios algoritmos para abordar este problema, que van desde métodos simples como la votación por mayoría hasta otros más complejos capaces de estimar la confiabilidad de las fuentes de datos . ^[1]

Los problemas de descubrimiento de la verdad se pueden dividir en dos subclases: verdad única y verdad múltiple. En el primer caso sólo se permite un valor verdadero para un elemento de datos (por ejemplo, cumpleaños de una persona, capital de un país). Mientras que en el segundo caso se permiten múltiples valores verdaderos (por ejemplo, actores de una película, autores de un libro). ^{[2] [3]}

Normalmente, el descubrimiento de la verdad es el último paso de un proceso de integración de datos , cuando se han unificado los esquemas de diferentes fuentes de datos y se han detectado los registros que hacen referencia al mismo elemento de datos . ^[4]

Principios generales

La abundancia de datos disponibles en la web hace que cada vez sea más probable encontrar que diferentes fuentes proporcionen (parcial o completamente) valores diferentes para el mismo dato . Esto, junto con el hecho de que estamos aumentando nuestra dependencia de los datos para tomar decisiones importantes, motiva la necesidad de desarrollar buenos algoritmos de descubrimiento de la verdad . ^[5]  

Muchos métodos disponibles actualmente se basan en una estrategia de votación para definir el valor real de un elemento de datos . Sin embargo, estudios recientes han demostrado que, si nos basamos únicamente en el voto mayoritario , podríamos obtener resultados erróneos incluso en el 30% de los datos . ^[5]

La solución a este problema es evaluar la confiabilidad de las fuentes y dar más importancia a los votos provenientes de fuentes confiables. ^{[4] [5]}

Idealmente, se podrían aprovechar las técnicas de aprendizaje supervisado para asignar una puntuación de confiabilidad a las fuentes después de etiquetar manualmente los valores proporcionados; Desafortunadamente, esto no es factible ya que la cantidad de ejemplos etiquetados necesarios debe ser proporcional a la cantidad de fuentes y, en muchas aplicaciones, la cantidad de fuentes puede ser prohibitiva. ^{[2] [6]}

Descubrimiento de verdad única versus verdad múltiple

El descubrimiento de una verdad única y de una verdad múltiple son dos problemas muy diferentes. ^[2]

El descubrimiento de una verdad única se caracteriza por las siguientes propiedades:

• sólo se permite un valor verdadero para cada elemento de datos ;
• los diferentes valores proporcionados para un determinado elemento de datos se oponen entre sí;
• Los valores y fuentes pueden ser correctos o erróneos.

Mientras que en el caso de verdades múltiples se mantienen las siguientes propiedades:

• la verdad está compuesta por un conjunto de valores;
• diferentes valores podrían proporcionar una verdad parcial;
• afirmar un valor para un determinado dato no implica oponerse a todos los demás valores;
• el número de valores verdaderos para cada elemento de datos no se conoce a priori.

El descubrimiento de múltiples verdades tiene características únicas que hacen que el problema sea más complejo y debe tenerse en cuenta al desarrollar soluciones de descubrimiento de la verdad. ^[2]

Los ejemplos siguientes señalan las principales diferencias de los dos métodos. Sabiendo que en ambos ejemplos la verdad la proporciona la fuente 1, en el caso de verdad única (primera tabla) podemos decir que las fuentes 2 y 3 se oponen a la verdad y como resultado proporcionan valores incorrectos. Por otro lado, en el segundo caso (segunda tabla), las fuentes 2 y 3 no son ni correctas ni erróneas, sino que proporcionan un subconjunto de los valores verdaderos y al mismo tiempo no se oponen a la verdad.

Confiabilidad de la fuente

La gran mayoría de los métodos de descubrimiento de la verdad se basan en un enfoque de votación: cada fuente vota por un valor de un determinado elemento de datos y, al final, el valor con el voto más alto se selecciona como el verdadero. En los métodos más sofisticados, los votos no tienen el mismo peso para todas las fuentes de datos ; de hecho, se da más importancia a los votos que provienen de fuentes confiables. ^[5]

La confiabilidad de la fuente generalmente no se conoce a priori , pero se estima con un enfoque iterativo. En cada paso del algoritmo de descubrimiento de la verdad, se refina la puntuación de confiabilidad de cada fuente de datos , lo que mejora la evaluación de los valores verdaderos, lo que a su vez conduce a una mejor estimación de la confiabilidad de las fuentes. Este proceso suele terminar cuando todos los valores alcanzan un estado de convergencia. ^[5]

La confiabilidad de la fuente puede basarse en diferentes métricas, como la precisión de los valores proporcionados, la copia de valores de otras fuentes y la cobertura del dominio. ^[1]

Detectar comportamientos de copia es muy importante; de ​​hecho, la copia permite difundir valores falsos fácilmente, lo que hace que el descubrimiento de la verdad sea muy difícil, ya que muchas fuentes votarían por los valores incorrectos. Generalmente los sistemas disminuyen el peso de los votos asociados a los valores copiados o incluso no los cuentan en absoluto. ^[7]

Métodos de verdad única

La mayoría de los métodos de descubrimiento de la verdad actualmente disponibles han sido diseñados para funcionar bien sólo en el caso de una sola verdad. ^{[1] [3]}

A continuación se informan algunas de las características de las tipologías más relevantes de métodos de verdad única y cómo los diferentes sistemas modelan la confiabilidad de las fuentes. ^[5]

Votación mayoritaria

La votación por mayoría es el método más sencillo, el valor más popular se selecciona como el verdadero. La votación por mayoría se utiliza comúnmente como punto de referencia al evaluar el desempeño de métodos más complejos.

Basado en enlaces web

Estos métodos estiman la confiabilidad de la fuente explotando una técnica similar a la utilizada para medir la autoridad de las páginas web basadas en enlaces web . El voto asignado a un valor se calcula como la suma de los votos asignados a los valores que proporciona la fuente. ^{[5] [8]}

Basado en la recuperación de información

Estos métodos estiman la confiabilidad de la fuente utilizando medidas de similitud típicamente utilizadas en la recuperación de información . La confiabilidad de la fuente se calcula como la similitud del coseno (u otras medidas de similitud ) entre el conjunto de valores proporcionados por la fuente y el conjunto de valores considerados verdaderos (ya sea seleccionados de forma probabilística u obtenidos a partir de una verdad fundamental). ^{[5] [9]}

basado en bayesiano

Estos métodos utilizan la inferencia bayesiana para definir la probabilidad de que un valor sea verdadero condicionado a los valores proporcionados por todas las fuentes.

${\displaystyle P(v\mid \psi (o))={\frac {P(\psi (o)\mid v)\cdot P(v)}{P(\psi (o))}}}$

donde es un valor proporcionado para un elemento de datos y es el conjunto de valores observados proporcionados por todas las fuentes para ese elemento de datos específico . ${\displaystyle \textstyle v}$ ${\displaystyle \textstyle o}$ ${\displaystyle \textstyle \psi (o)}$

Luego, la confiabilidad de una fuente se calcula en función de la precisión de los valores que proporciona. ^{[7] [10]} Otros métodos más complejos explotan la inferencia bayesiana para detectar comportamientos de copia y utilizan estos conocimientos para evaluar mejor la confiabilidad de la fuente. ^[7]

Métodos de verdades múltiples

Debido a su complejidad , se ha dedicado menos atención al estudio del descubrimiento de múltiples verdades ^{[2] [3]}

A continuación se informan dos tipologías de métodos de verdades múltiples y sus características.

basado en bayesiano

Estos métodos utilizan la inferencia bayesiana para definir la probabilidad de que un grupo de valores sea verdadero condicionado a los valores proporcionados por todas las fuentes de datos . En este caso, dado que podría haber varios valores verdaderos para cada elemento de datos y las fuentes pueden proporcionar varios valores para un único elemento de datos, no es posible considerar los valores individualmente. Una alternativa es considerar asignaciones y relaciones entre un conjunto de valores proporcionados y las fuentes que los proporcionan. Luego, la confiabilidad de una fuente se calcula en función de la precisión de los valores que proporciona. ^[2]

Los métodos más sofisticados también consideran la cobertura del dominio y los comportamientos de copia para estimar mejor la confiabilidad de la fuente. ^{[2] [3]}

Modelos Gráficos Probabilísticos basados

Estos métodos utilizan modelos gráficos probabilísticos para definir automáticamente el conjunto de valores verdaderos de un elemento de datos determinado y también para evaluar la calidad de la fuente sin necesidad de supervisión. ^[11]

Aplicaciones

Muchas aplicaciones del mundo real pueden beneficiarse del uso de algoritmos de descubrimiento de la verdad. Los dominios de aplicación típicos incluyen: atención médica , detección social/de multitudes , agregación de crowdsourcing , extracción de información y construcción de bases de conocimientos . ^[1]

Los algoritmos de descubrimiento de la verdad también podrían utilizarse para revolucionar la forma en que se clasifican las páginas web en los motores de búsqueda , pasando de los métodos actuales basados ​​en el análisis de enlaces como el PageRank , a procedimientos que clasifican las páginas web en función de la exactitud de la información que proporcionan. ^[12]

Ver también

• Integración de datos
• Integración de información
• Fusión de datos (integración de datos)
• Calidad de datos

Referencias

1. Li, Yaliang; Gao, Jing; Meng, Chuishi; Li, Qi; Su, Lu; Zhao, Bo; Fan, Wei; Han, Jiawei (25 de febrero de 2016). "Una encuesta sobre el descubrimiento de la verdad". Boletín de exploraciones de ACM SIGKDD . 17 (2): 1–16. doi :10.1145/2897350.2897352. S2CID  9060471.
2. Wang, Xianzhi; Sheng, Quan Z.; Colmillo, Xiu Susie; Yao, Lina; Xu, Xiaofei; Li, Xue (2015). "Un enfoque bayesiano integrado para el descubrimiento eficaz de múltiples verdades". Actas de la 24ª Conferencia Internacional ACM sobre Gestión de la Información y el Conocimiento . Melbourne, Australia: Prensa ACM. págs. 493–502. doi :10.1145/2806416.2806443. hdl : 2440/110033 . ISBN 9781450337946. S2CID  16207808.
3. Lin, Xueling; Chen, Lei (2018). "Descubrimiento de múltiples verdades con reconocimiento de dominio a partir de fuentes en conflicto". Dotación VLDB . 11 (5): 635–647. doi :10.1145/3187009.3177739.
4. Dong, Xin Luna ; Srivastava, Divesh (15 de febrero de 2015). "Integración de Big Data". Conferencias de Síntesis sobre Gestión de Datos . 7 (1): 1–198. doi : 10.2200/S00578ED1V01Y201404DTM040 . ISSN  2153-5418.
5. , Xian; Dong, Xin Luna ; Lyon, Kenneth; Meng, Weiyi; Srivastava, Divesh (1 de diciembre de 2012). "Búsqueda de la verdad en la web profunda: ¿está resuelto el problema?". Actas del Fondo de Dotación VLDB . 6 (2): 97-108. arXiv : 1503.00303 . doi :10.14778/2535568.2448943. S2CID  3133027.
6. Ng, Andrew Y; Jordania, Michael I. (2001). "Sobre clasificadores discriminativos versus generativos: una comparación de regresión logística y Bayes ingenuo". Actas de la 14ª Conferencia Internacional sobre Sistemas de Procesamiento de Información Neural: Naturales y Sintéticos : 841–848.
7. Dong, Xin Luna ; Berti-Equille, Laure; Srivastava, Divesh (1 de agosto de 2009). "Integración de datos contradictorios: el papel de la dependencia de la fuente". Actas del Fondo de Dotación VLDB . 2 (1): 550–561. doi :10.14778/1687627.1687690. S2CID  9664056.
8. Kleinberg, Jon M. (1 de septiembre de 1999). "Fuentes autorizadas en un entorno de hipervínculos". Revista de la ACM . 46 (5): 604–632. doi : 10.1145/324133.324140 . S2CID  221584113.
9. Galland, Alban; Abiteboul, Serge; Marian, Amélie; Senellart, Pierre (2010). "Corroborar información de puntos de vista divergentes". Actas de la tercera conferencia internacional ACM sobre búsqueda web y minería de datos (PDF) . Nueva York, Nueva York, Estados Unidos: ACM Press. págs. 131-140. doi :10.1145/1718487.1718504. ISBN 9781605588896. S2CID  1761360.
10. Xiaoxin Yin; Jiawei Han; Yu, PD (2008). "Descubrimiento de la verdad con múltiples proveedores de información en conflicto en la Web". Transacciones IEEE sobre conocimiento e ingeniería de datos . 20 (6): 796–808. doi :10.1109/TKDE.2007.190745. ISSN  1041-4347.
11. Zhao, Bo; Rubinstein, Benjamín IP; Gemmell, Jim; Han, Jiawei (1 de febrero de 2012). "Un enfoque bayesiano para descubrir la verdad a partir de fuentes conflictivas para la integración de datos". Actas del Fondo de Dotación VLDB . 5 (6): 550–561. arXiv : 1203.0058 . doi :10.14778/2168651.2168656. S2CID  8837716.
12. "Las enormes implicaciones de la idea de Google de clasificar los sitios en función de su precisión". www.washingtonpost.com . 2015.