The Chair of Computational Thinking for AI (CT4AI) is Prof Bruce William Watson. The CT4AI group has 19 active members, including two applied researchers, three postdoctoral researchers, and 10 PhD & Master's students. The group also has 10 affiliated research associates. The CT4AI group sits within the Stellenbosch School for Data-Science and Computational Thinking – a new structure cutting across all ten faculties of the university. The School collects almost all activities in AI, data-science, and computational thinking, though staff and students remain additionally affiliated with their faculty for domain knowledge. While CT4AI is the AI focus of the School, there are several other research groups working in and with AI, and most such departments collaborate with CT4AI. The postgraduate students in CT4AI have strong interaction with their home faculties and additionally spend time in the School's building, interacting across projects.
The research field of Computational Thinking for AI focuses on problem solving in AI, grounded in computational thinking skills and techniques. This includes problem abstraction and decomposition, symbolic modeling, computational logic, and algorithmic problem solving. Computational Thinking is therefore foundational to both symbolic AI with its advanced reasoning capabilities, and non-symbolic (connectionist) AI with its advanced learning capabilities.
Within this research field, the Computational Thinking for AI (CT4AI, for short) group in the School for Data Science and Computational Thinking at Stellenbosch University primarily focuses on the learning, design and analysis of correct, fair and secure algorithms, using data as the key ingredient. While machine learning and statistical techniques are showing impressive results, there is a lag in establishing the foundations for the correctness, fairness, and security of the algorithms produced with these approaches. This lag is also hindering the accessibility and applicability of such techniques in various domains, including, for example: cybersecurity, computational biology, and social network analysis.
Prof. Watson is an internationally recognized researcher and industry expert in the correctness and safety of algorithms – especially for glass-box ('explainable AI') correlation, and pattern and anomaly recognition. He has extensive expertise in programming language design, especially domain-specific ones, and is the inventor of several different kinds of algorithms that are known for being very fast but also proven to be correct based on a unique methodology for software development (Correctness-by-Construction). The methodology and calculi used by the Chair in Applied AI can be considered a secret weapon in the design of an entirely new generation of algorithms ready to be applied in AI and Quantum Computing.
The Chair's research group are global leaders in calculi for the design of algorithms, as well as for taxonomizing them. These algorithms are particularly aimed at finding patterns in data and for incrementally building structures for knowledge representation, of both relationships and processes. Several such algorithms invented by the Chair's research group are the domain leaders in areas such as cybersecurity and -warfare, social network analysis (SNA), complex event processing for SmartCities and lightweight IoT, computational linguistics, bioinformatics, etc. The Chair's research experience extends to related areas such as blockchain and post-quantum issues.
Ongoing and planned future research revolves around simple observations: our group has a successful and unexhausted methodology (Taxonomy Based Software Construction – TABASCO), which is built upon refinement-based “correctness-by-construction" (CbC) of algorithms. TABASCO is used to explore a particular algorithmic field, classifying all of the algorithms while identifying commonalities and variance points. The resulting taxonomy is used to directly obtain a software architecture and a toolkit implementing all of the algorithms – where the taxonomy structure results in a software product line (SPL) for optimal code size and performance. The taxonomy additionally provides insight into the relative performance of the algorithms and yields a software configurator for selecting algorithms. Lastly, apparent gaps in the taxonomy are opportunities for inventing new algorithms using CbC. This is the only known methodology for directly arriving at correct new algorithms.
The following research areas are in order of increasing complexity and time-horizon:
New problem domains
There are several highly popular areas of computation where efforts to convincingly show algorithm correctness have not kept up with the variety of algorithms. In these areas, TABASCO (or at least CbC) will be applied to invent new proven-correct algorithms. Topical examples include: the basic machine learning algorithms (such as back-propagation, SVMs); cryptographic primitives used in blockchain; algorithms in big science (such as those used in radio telescopes, particle accelerators, and genomics); social network analysis; and post-quantum cryptography. Previous experiences with TABASCO indicate the potential for breakthroughs in these areas.
X-by-construction
CbC is being extended to X-by-construction for a variety of interesting “X properties," such as: ethical/fair; privacy-safe; secure; power-saving, safety-constrained, etc. An algorithm design tool to support TABASCO is under development. Such tools will be adapted to support X-by-construction.
Computational models
Two new models are suitable for CbC and TABASCO: graph computing, and quantum computing. The former has been made popular with graph databases, and an adapted TABASCO will allow us to develop new algorithms (e.g. for pattern matching) purely in the graph domain. While access to quantum computing is still below the horizon, the computational foundations are clear enough to also adapt CbC for quantum – thereby bringing a systematic approach to quantum algorithmics. Appropriate CbC support in these domains will be key to inventing new algorithms.
“Implicit algorithms"
Almost all traditional algorithm design work is for statically expressible algorithms (the structure is written out), and not for “learned" algorithms as they arise in machine learning. As machine learning algorithms become more dominant (via data-science and AI), the same standards of correctness are required – though the algorithms themselves are far more opaque and difficult to reason about. CbC (and related verification approaches) will be extended to this meta problem.
Algorithmics for societal impact
Popular science books such as “Algorithms to live by" have highlighted the pervasiveness of algorithms, and COVID-19 has shown their brittleness as they are used in government and business processes. Our expertise in CbC will be applied to designing robust and broadly applicable algorithms for societal settings such as decision making, supply chain management, information security, social network analysis etc.
.png)
Contact:
Prof Bruce (William) Watson