Confianza y Reputación en Sistemas Multi-Agente Ramón Hermoso Traba Universidad Rey Juan Carlos [email protected] Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 2 1. Introducción Aproximación al problema Confianza O: comprar un + coche Coste nuevo P1 + Riesgo + … P2 C1 C1 P3 Acción: Comprar coche a P2 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente P4 3 1. Introducción Aproximación al problema Ok, coordination is fine, but… Human-based Any other again?... factor metaphores that leads the agent to act? Bob 18/02/2016 What Comeabout on!, this Let me tell “istrust ” on you a course something… others? about agents!!! bla, bla, bla Alice Confianza y Reputación en Sistemas Multi-Agente 4 1. Introducción Definiciones [Gambetta90] RAE “La confianza es la probabilidad subjetiva por la que un individuo A espera que otro individuo B realice una determinada acción de la que el bienestar de A depende” Confianza: esperanza firme que se tiene de alguien o algo Reputación: prestigio o estima en que son tenidos alguien o algo Falta de consenso semántico 18/02/2016 Confianza ≠ Reputación Trust ≠ Reputation ≠ Confidence ≠ Reliability ≠ Willingness … Confianza y Reputación en Sistemas Multi-Agente 5 1. Introuducción Definiciones Dificultad de modelización Medida de la estima o del prestigio Subjetividad Dificultad para el diseño Medida cuantitativas o cualitativas… ¿Qué es algo bueno? ¿Y para quién? tAB = 0.7 | tBA = 0.3 | tBC = “bueno” | tBA = k Distintos campos confluyen: informática (modelos computacionales), sociología (redes sociales), psicología (estados mentales), economía (funciones de utilidad, toma de decisiones, etc.), … 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 6 1. Introducción Definiciones Modelos de confianza Sirven para estimar la confianza en un agente/situación Predicen el comportamiento en una hipotética interacción confianza = f (explocal ,reputación,...) Confianza ≠ Confiar La confianza se usa como factor en procesos de selección de acciones: Confianza Selección de la acción Planificación Determinación de acciones Búsqueda de la acción Negociación / Ejecución 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 7 Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 8 2. Modelos de confianza Comerciales Dominios comerciales o redes sociales Ejemplo: eBay Usado como ayuda al usuario Valoración de opiniones distribuida Visión de valoraciones unívoca Naturaleza de las valoraciones: 18/02/2016 Suma de opiniones numéricas individuales: +1,0,-1 Comentarios textuales Visión global de la reputación de los usuarios Confianza y Reputación en Sistemas Multi-Agente 9 2. Modelos de confianza Comerciales Trip Advisor (www.tripadvisor.es) Opiniones Votaciones Ránkings Positivos (preferencias) Negativos (características a evitar) 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 10 2. Modelos de confianza Comerciales Dominios comerciales o redes sociales Ejemplo: eConcozco, Friendster, Facebook, … Aplicable a todo tipo de interacciones Intercambio de datos Redes P2P Descarga de ficheros 18/02/2016 Usan valoraciones como indicación al usuario Opiniones Ratings 1..10 “muy bueno” Confianza y Reputación en Sistemas Multi-Agente 11 Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 12 2. Modelos de Confianza Tipos de modelos Modelos centralizados vs. distribuidos Centralizados Distribuidos 18/02/2016 Mejor gestión de la información Presunción de autoridad (¿debemos confiar en ella?) Menos flexible / más dependiente Permiten subjetividad Mecanismo adaptativo y autónomo de control social normas sociales emergentes (sociedades humanas) Antropomorfismo Más robusto Modelos centralizados y distribuidos ¡¡¡compatibles!!! Confianza y Reputación en Sistemas Multi-Agente 13 2. Modelos de Confianza Investigación ¿Cómo lograr sistemas estables usando la confianza? 1. Empatía o reciprocidad con los agentes a partir de factores como la disposición o la fiabilidad (otros muchos) 2. 18/02/2016 Se obtienen y evolucionan por Modelos de Confianza La confianza será una medida para decidir la interacción con otro agente (necesaria pero no suficiente) Interacciones directas e indirectas Información interna (experiencia pasada) o externa (opiniones de terceros) Diseño de protocolos y mecanismos para las interacciones (reglas de encuentro) Confianza y Reputación en Sistemas Multi-Agente 14 2. Modelos de Confianza Investigación Problemas Ajuste de la confianza tras una experiencia directa Ajuste de la confianza tras una experiencia indirecta (p.ej. en una organización o grupo) Cómo agregar opiniones de otros a las experiencias locales propias Cómo ajustar la confianza en agentes que han servido como fuentes de reputación Exploración vs. Explotación 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 15 2. Modelos de confianza Investigación Factores a tener en cuenta: Capacidad Disposición Permisos Utilidad (no sólo económica…) Altruismo Egoísmo Dependencia … 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 16 2. Modelos de confianza Investigación Dos formas de conceptualizar la confianza en sistemas multi-agente Nivel individual: creencia sobre el comportamiento futuro de otro agente en una situación determinada lo mejor para el agente Nivel de sistema: usada para forzar a los agentes a actuar de forma benevolente (normas de comportamiento emergente) lo mejor para el sistema Conceptos: honestidad, benevolencia, malicia, incompetencia, altruismo difíciles de distinguir 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 17 2. Modelos de confianza Investigación Clasificación de modelos de confianza Modelos basados en Aprendizaje y Evolución Modelos basados en Reputación Modelos Socio-Cognitivos Modelos para Organizaciones Alineación semántica 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 18 2. Modelos de confianza Investigación – Aprendizaje y Evolución EVOLUCIÓN No siempre escenarios cooperativos Aunque éstos no son ideales Malevolencia Incompetencia Desconocimiento, … Utilidad vs. Confianza (equilibrio) [Wu,Sun] Confianza emerge como resultado de la evolución de estrategias en varias interacciones 18/02/2016 Mayor ganancia a largo plazo para los agentes “buenos” sacrificando parte de su utilidad a corto plazo (Dilema del prisionero) Umbral en el número de interacciones (característico para el cálculo) Variabilidad de los resultados Confianza y Reputación en Sistemas Multi-Agente 19 2. Modelos de confianza Investigación – Aprendizaje y Evolución APRENDIZAJE [Birk] Confianza también emerge del aprendizaje Dar más peso a los objetivos sociales vs. objetivos individuales Metáfora de la sociedad (inversión) Ciclo de actuación 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 20 2. Modelos de confianza Investigación – Aprendizaje y Evolución Ciclo de Birk Equilibrio final Aprenden ( beneficio global) Mayoría corrupta Mayoría cooperativa Explotan ( beneficio individual) 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 21 2. Modelos de confianza Investigación – Aprendizaje y Evolución Problemas: Asumen información completa (estrategias, recompensas, utilidades,…) Probados con restricciones fijas, no en el mundo real Resultado de interacciones valor dicotómico (0 ó 1) 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 22 2. Modelos de confianza Investigación - Reputación Opinión o vista de alguien acerca de algo Confianza ≠ Reputación Reputación es un medio para la Confianza (ej. eBay) Líneas de investigación en Reputación: Métodos para recoger ratings acerca de lo “bueno” que es el agente Métodos de razonamiento para la agregación de esa información Mecanismos de actualización (nuevos pesos) Recuperación y agregación con Redes Sociales 18/02/2016 Representación mediante grafos (relaciones) Los ratings “fluyen” entre los nodos por los arcos [Schillo et al.] Honestidad y Altruismo Posibilidad para los agentes de adquirir información de otros Confianza y Reputación en Sistemas Multi-Agente 23 2. Modelos de confianza Investigación - Reputación Agregación Combinación de valores de reputación que llegan a un agente Ejemplo: eBay (+1, -1). Comentarios? Modelos basados en teorías más sólidas: [Yu y Singh] Teoría de Dempster-Shafer Funciones de creencia - tres tipos de valores: 18/02/2016 Trustworthy Untrustworthy Uncertain Confianza y Reputación en Sistemas Multi-Agente 24 2. Modelos de confianza Investigación - Reputación Concepto de witness Problema: Testigos o fuentes de reputación Asunción de que nunca mienten Cómo elergir las fuentes de reputación Todo intercambio de información implica riesgo de imprecisión (casual o intencionada) A más intercambio mayor riesgo Soluciones: 18/02/2016 [Schillo] honestidad y altruismo [Sen y Dutta] probabilidad de mentira sobre los testigos Confianza y Reputación en Sistemas Multi-Agente 25 2. Modelos de confianza Investigación - Reputación [Sabater y Sierra] 3 dimensiones de la reputación: Dimensión individual Dimensión social 18/02/2016 Reputación como suma ponderada de impresiones subjetivas que derivan de interacciones directas Impresión del grupo de a1 acerca de a2 Impresión del grupo de a1 acerca del grupo de a2 Impresión de los agentes del grupo de a2 sobre su compañero Dimensión ontológica Confianza y Reputación en Sistemas Multi-Agente 26 2. Modelos de confianza Investigación - Reputación Búsqueda de un modelo de confianza basado en reputación: Más valor a experiencias propias Cuanto mayor es el intercambio de información mayor es la probabilidad de hacer un razonamiento inexacto (incompetencia – malevolencia) Buscamos un equilibrio entre Razonamiento local experiencia propia hasta ahora Información externa reputación Confianza 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 27 2. Modelos de confianza Investigación – Cognitivos Creencias acerca de la valoración del entorno y las características del agente evaluado (estado mental) Castelfranchi (ISTC-CNR) visión cognitiva de la confianza vs. visión cuantitativa (para agentes BDI) Competencia Buena voluntad Persistencia Motivación Problemas Cómo se crea y evoluciona la confianza como atributo mental Les falta base experiental (“muy sociológico”) Costosos Combinación con modelos probabilísticos 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 28 2. Modelos de confianza Investigación – Orientados a OV Modelos de confianza orientados a organizaciones de agentes Organización SMAs + restricciones Roles, interacciones, normas, … Aprovechan la información de la organización para mejorar modelos de confianza Similitud de roles/interacciones Argumentación con normas 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 29 2. Modelos de confianza Investigación – Orientados a organizaciones Definición de la Organización Proporcionado por la organización Problema de decisión del agente • Los agentes deben cumplir objetivos • Los agentes deben realizar diversas interacciones para cumplir estos objetivos • De entre los agentes capacitados (por su rol) para realizar las interacciones, ¿a cuál de ellos elegir? 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 30 2. Modelos de confianza Investigación – Orientados a OV Los agentes mantienen una Local Interaction Table (LIT): 18/02/2016 Estructura de datos que compila los resultados de las interacciones pasadas Indexados por claves del tipo agente/rol/interaction (<X,Y,Z>) Con valores asociados de confidence y reliability <X,Y,Z>: unidad atómica “agente X jugando el rol Y en la interación Z” Confidence (cA <X,Y,Z>): de la propia experiencia del agente Reliability (rA <X,Y,Z>): mide cómo de seguro está un agente acerca de su propio valor de confidence en la situación <X,Y,Z> Confianza y Reputación en Sistemas Multi-Agente 31 2. Modelos de confianza Investigación – Orientados a OV Enfoque básico: 18/02/2016 “… un agente A jugando el rol Estudiante necesita encontrar un compañero para un tipo de práctica en una asignatura específica” El estudiante mirará en su LIT las interacciones pasadas haciendo ese tipo de prácticas (I) con otros estidiantes (R) El agente A seleccionará a aquel agente con una mayor confidence en su LIT poniendo atención únicamente en aquellas entradas <X,R,I>, donde X puede ser cualquier otro agente Confianza y Reputación en Sistemas Multi-Agente 32 2. Modelos de confianza Investigación – Orientados a OV Problema: la LIT puede ser incompleta No hay entradas para la situación <X,Y,Z> Existe baja precisión en los valores para las entradas <X,Y,Z> Hipótesis: los agentes se comportan de manera similar cuando juegan roles similares o actúan en interacciones similares Los valores de confidence pueden ser aproximados a partir de las entradas en la LIT del agenteen lugar de preguntar a fuentes de reputación Experiencias con un agente en roles/interacciones similares pueden ser usadas para aproximar mejor valores de confidence Las similitudes pueden ser obtenidas a partir de las taxonomías de roles e interacciones que facilita la organización 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 33 2. Modelos de confianza Investigación – Orientados a OV Basic trust model aplicado a los datos de la LIT: Sacamos partido a la estructura de la organización (inference trust model): wA X ,Y ,Z rA X ,Y ,Z sim( X , Y , Z , B, R, I ) Cálculo de la Similitud: Actualización de confidence: Actualización de la reliability: basado en el número de interacciones y en su variabilidad 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 34 2. Modelos de confianza Investigación – Alineación semántica Línea de investigación en dominios SOC Especialmente Semantic Web Services Cualquier dominio de intercambio de información Solución: definir ontologías ‘ad-hoc’ Problema: mundo de la heterogeneidad ¿Qué es 0.5 en [0..1]? ¿0.7 es bueno para ti? ¿Cómo identificar situaciones iguales o similares? “Traductores” semánticos Entidades intermedias Interpretan lo que quieren decir Como con los lenguajes de representación del conocimiento Técnicas más avanzadas Integración de ontologías a través de reglas 18/02/2016 … Confianza y Reputación en Sistemas Multi-Agente 35 Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 36 3. Testbeds - ART Agent, Reputation and Trust (ART) testbed http://www.lips.utexas.edu/art-testbed/index.html Motivación 18/02/2016 Excesiva heterogeneidad de las métricas para evaluar modelos de confianza Unificación de perspectivas Entorno común de experimentación La competición hace más llamativa la herramienta Confianza y Reputación en Sistemas Multi-Agente 37 3. 18/02/2016 Testbeds - ART Confianza y Reputación en Sistemas Multi-Agente 38 3. Testbeds - ART Tasadores reciben clientes que pagan precio fijo por tasación Las pinturas se distribuyen aleatoriamente entre las eras Al pasar rondas los mejores tasadores recibirán más clientes (y por tanto más beneficios) 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 39 3. Testbeds - ART Tasadores saben su nivel de expertise en cada era Tasadores no saben el nivel de los demás Tasadores pueden comprar reputaciones, por un precio fijo, de otros tasadores. Valor de reputación entre 0 y 1, valoración sólo para comunicación entre agentes 18/02/2016 No se fuerza a usar una representación interna fija Confianza y Reputación en Sistemas Multi-Agente 40 3. 18/02/2016 Testbeds - ART Confianza y Reputación en Sistemas Multi-Agente 41 3. Testbeds - ART Compra/Venta de opiniones 18/02/2016 Por cada pintura, un tasador puede pedir opiniones (a un precio fijo) de otros tasadores La simulación genera opiniones sobre las pinturas para los tasadores que aceptan dar opiniones La precisión de la opinión es proporcional al expertise del agente que da la opinión sobre la era del cuadro y al dinero invertido en la opinión Confianza y Reputación en Sistemas Multi-Agente 42 3. Testbeds - ART Métricas De un agente De la sociedad de agentes 18/02/2016 Dinero del ganador Error medio cometido en las tasaciones Desviación típica del error cometido en las tasaciones Número de cada tipo de mensajes intercambiados Saldo de cada agente Ganancia de cada agente en cada iteración Número de mensajes y transacciones ocurridas Distribución de transacciones entre agentes Confianza y Reputación en Sistemas Multi-Agente 43 3. 18/02/2016 Testbeds - ART Confianza y Reputación en Sistemas Multi-Agente 44 3. Testbeds - ART Ventajas Intento de unificar visiones y criterios No fija la representación del conocimiento de los agentes Aceptado por la comunidad (bajando la popularidad ) Desventajas Orientado a maximizar la función de tasación Teoría de juegos no debería ser el fin 18/02/2016 En una misma población Dilema del Prisionero Iterado (más complejo) Resultados “anormales” en las competiciones Confianza y Reputación en Sistemas Multi-Agente 45 Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 46 3. Testbeds - TOAST Trust Organisational Agent System Testbed (TOAST) Objetivo Proporcionar un soporte experimental para la evaluación de modelos de confianza en organizaciones virtuales SMAs + algunas restricciones (roles, interacciones, objetivos, normas, …) Características Experimental setup: Experiment generation Generación estocástica de las características de los agentes (capacidad, diversidad) Experiment execution 18/02/2016 Definición de la OV: Taxonomías de Roles, Interacciones Número y tipos de objetivos/agentes Evaluación cuantitativa de los modelos de confianza Confianza y Reputación en Sistemas Multi-Agente 47 3. Testbeds - TOAST Ejemplo de taxonomía de Roles Definición de objetivos <GoalsType> <Goal Name="Select Subject to Enrol"> <Interaction Name="Study Subject"> <Role Name="Student"> </Role> <Role Name="Academic Staff"> </Role> </Interaction> </Goal> <Goal Name="Select Lecturer"> <Interaction Name="Teach"> <Role Name="Academic Staff"> </Role> <Role Name="Student"> </Role> </Interaction> </Goal> … 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 48 3. Testbeds – TOAST Generación de experimentos Generación estocástica Asignación Agentes/Objetivos Asignación Agentes/Roles Qué es lo que un agente tiene que hacer Qué funcionalidades ofrecen los agentes Valores de capacidad Agentes/Rol/Interacción Cómo de “bueno” es un agente jugando un rol determinado en una interacción específica Se modela mediante distribuciones de probabilidad normales 18/02/2016 Media: habilidad del agente para realizar la acción Desviación típica: variaciones sufridas por diferentes situaciones Confianza y Reputación en Sistemas Multi-Agente 49 3. Testbeds – TOAST Dinámica de ejecución 1. Los objetivos son entregado en las colas de los agentes 2. Los agentes toman los objetivos y les asocian interacciones 3. Los agentes se basan en sus modelos de confianza para elegir un agente de entre los posibles candidatos 4. TOAST determina la utilidad de las interacciones 5. Los agentes actualizan sus modelos 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 50 3. Testbeds – TOAST Dinámica de ejecución Generador de Objetivos ?? Valores capacidad Organización F 0.25 {C,E,F,Z} F ?? Y {A,Y} Agente A 0.72 Y ?? Agente B 18/02/2016 X Agente C {A,D,Y,X} Confianza y Reputación en Sistemas Multi-Agente 0.64X 51 Contenidos Introducción 1. Aproximación al problema Definiciones Modelos de Confianza 2. Comerciales Investigación Testbeds 3. ART Testbed TOAST 4. Discusión 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 52 4. Posibles trabajos Discusión del próximo día: J.Sabater y C.Sierra. “REGRET: a reputation model for gregarious societies”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs. 475-482, 2002. 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 53 4. Posibles trabajos Teóricos Estado del Arte: Modelos probabilísticos: 18/02/2016 A Survey of Trust in Computer Science and the Semantic Web. Donovan Artz and Yolanda Gil. A Survey of Trust and Reputation Systems for Online Service Provision. Audun Jøsang, Roslan Ismail, Colin Boyd Trust in Multiagent Systems. S. Ramchurn, T.D. Huynh, N. Jennings. The Knowledge Engineering Review (v.19, págs: 1-25) TRAVOS-R Jigar Patel TRAVOS-C W.T. Luke Teacy Otros Modelos cognitivos Castelfranchi, Falcone Confianza y Reputación en Sistemas Multi-Agente 54 4. Posibles trabajos Teórico-prácticos Desarrollo teórico y experimental de algún agente en ART Testbed Competición? http://www.lips.utexas.edu/art-testbed/index.html 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 55 Bibliografía D. Gambetta. “Trust”. Basil Blackwell, Oxford, 1990 D.J. Wu y Y. Sun. “The emergence of trust in multi-agent bidding: A computational approach”. Proceedings of the 34th Hawaii International Conference on System Sciences, IEEE Computer Society Press, 2001 A. Birk. “Learning to trust”. Trust in Cyber-Societies, págs. 133-144. Springer-Verlag, 2001 C. Castelfranchi y R. Falcone. “Principles of trust for MAS: cognitive anatomy, social importance, and quantification”. Proceedings of International Conference of Multi-Agent Systems (ICMAS’98), págs. 72-79, 1998 R.Jurca y B.Faltings. “An incentive compatible reputation mechanism”. Proceedings of the IEEE Conference on ECommerce, págs. 285-292, 2003 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 56 Bibliografía J.Sabater y C.Sierra. “REGRET: a reputation model for gregarious societies”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs. 475-482, 2002 M.Schilo, P.Funk y M.Rovatsos. “Using trust for detecting deceptive agents in artificial societies”. Applied Artificial Intelligence journal, págs. 825-848, 2000 S.Sen y P.S.Dutta. “The evolution and stability of cooperative trails”. Proceedins of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), págs. 1114-1120, 2002 B.Yu y M. Singh. “Detecting deception in reputation management”. Proceedings of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’02), 2002 B.Yu y M. Singh. “An evidential model of distributed reputation management”. Proceedings of 2nd International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’03), 2003 18/02/2016 Confianza y Reputación en Sistemas Multi-Agente 57
© Copyright 2024