XAlgo: a Design Probe of Explaining Algorithms' Internal States via Question-Answering

Title of the Paper

XAlgo: a Design Probe of Explaining Algorithms’ Internal States via Question-Answering

Paper Information

• Domain: Human-Computer Interaction and Explainable Artificial Intelligence (XAI)
• Keywords: Explainable AI, Question-Answering, Algorithms, Design Probe, Algorithm Internal States

Research Background and Issues

• Problems or Challenges:

  • For many algorithm users (especially non-experts), algorithms are often perceived as incomprehensible "black boxes," making it difficult to understand how or why specific results are generated.
  • Existing explanatory methods, such as rule extraction, component visualization, or input-output attribution analysis, predominantly focus on data-driven models, while providing insufficient explanations for the internal states of process-driven deterministic algorithms.
  • Current solutions fail to meet the needs of user groups situated between algorithm developers and end-users (e.g., students, system administrators) who seek to understand the internal states of algorithms.

• Importance of the Problem:

  • Lack of transparency in algorithm-driven scenarios may lead to mistrust or even incorrect decision-making.
  • Providing user-friendly algorithm explainability features can promote learning and application, support system monitoring, and facilitate troubleshooting, yielding significant social and technological impacts.

• Research Motivation and Related Work:

  • Existing research on algorithm explainability tends to emphasize reconstructive methods (using surrogate models to represent the behavior of the original model), which fail to deeply reveal the internal mechanisms of algorithms.
  • Question-answering (QA), as a natural communication method among humans, offers new opportunities for designing user-centered explainable AI systems.

Solution

• Method or Solution: The study proposes a model named XAlgo, which enables non-expert users to obtain explanations of deterministic algorithms' internal states through questioning, including the following functionalities:

  1. Question Classification: Using semantic parsing and NLP techniques, user questions are categorized into five types (causal, contrastive, descriptive, confirmatory, and conceptual).
  2. Answer Generation: Based on the classification results, information related to node states is extracted from the algorithm's internal representation (e.g., pseudocode) to generate answers.

• Innovative Features:

  • XAlgo is the first to integrate descriptive and interactive mechanisms, employing a question-answering model to present and explain specific internal states of algorithms rather than merely reconstructing input-output relationships.
  • A hierarchical directed acyclic graph (HDAG) is introduced as a structured representation of algorithm execution states, supporting dynamic querying and multi-level explanations.

• Implementation Steps and Key Technologies:

  • Construct an HDAG containing the internal states (nodes) of the algorithm, based on pseudocode, recording information such as goals, operations, and objects in layers.
  • Parse key information in user questions (e.g., temporal indicators, objects, values, actions) to locate the corresponding algorithm nodes.
  • Generate natural language answers based on node descriptions, while providing causal or contrastive explanations.

Research Findings

• Specific Findings:

  • A design probe experiment based on XAlgo was conducted, using the QuickSort algorithm learning scenario to collect user questions and evaluate the system's response effectiveness.
  • XAlgo successfully classified and answered most user questions, particularly those related to algorithm states, providing clear and detailed explanations of algorithm operations.
  • User feedback indicated that XAlgo significantly improved the learning experience, with its answers offering a solid foundation for understanding algorithms.

• Advantages and Comparisons:

  • Compared to existing platforms that only display algorithm animations, XAlgo introduces interactivity, allowing users to actively pose questions and receive detailed explanations.
  • Although XAlgo is not yet fully mature in guiding users to complete specific tasks, participants generally found its answers helpful for algorithm learning.

• Experiment and Evaluation Results:

  • During the experiment, user questions about algorithms were distributed between concept-related questions (42%) and algorithm state-related questions (58%), with causal and confirmatory questions being the most common.
  • Evaluations of XAlgo-generated answers showed high satisfaction (accuracy mean: 6.11/7; detail mean: 6.56/7).
  • No significant differences were observed in test scores across different groups, indicating that the challenges of learning algorithms still require more proactive guidance.

• Limitations and Future Directions:

  • Accurately implementing XAlgo's NLP capabilities and meeting the needs of different question classifications remain technical challenges.
  • For complex statistical learning algorithms (e.g., neural networks), XAlgo needs to integrate high-level visualization tools to enhance explainability.
  • In learning scenarios, the study suggests that QA mechanisms should proactively ask or guide users to address the limitations of passive answering.

Appendix and References

The paper cites extensive research related to explainable AI, question-answering, and algorithm teaching, providing theoretical foundations and technical insights for designing interactive explainability systems in the future.