Understanding Time Complexity in Machine Learning: Training vs. Testing Phases

Machine Learning (ML) algorithms are the foundation of modern artificial intelligence applications, ranging from image recognition to predictive modeling. Whether you're building a machine learning model to recommend products or forecast energy consumption, every ML algorithm goes through two critical phases: the training phase and the testing (or inference) phase. The time it takes for an algorithm to complete these phases can vary greatly, and this is where time complexity comes into play. In this blog post, we will break down these two phases and delve into how to interpret time complexity formulas for common ML algorithms using Big "O" notation.

1. The Training Phase vs. the Testing Phase in Machine Learning

In any supervised machine learning workflow, we can identify two main phases: training and testing. These phases are distinct but complementary, each playing a vital role in building and using a predictive model.

• Training Phase: This is where the algorithm learns from the data. During training, the model is fed data (input) along with the corresponding labels (output), and it optimizes its parameters to minimize the error between predicted and actual outputs. This phase can be computationally expensive as it requires the algorithm to process a large amount of data and adjust its internal parameters accordingly. The training complexity refers to how long it takes the algorithm to build this model.

• Testing Phase (Inference): Once the model is trained, it is tested on new, unseen data to evaluate its performance. The goal of the testing phase is to use the trained model to make predictions. The complexity of the testing phase often determines how fast the model can provide predictions in real-time.

Understanding the computational complexity in both phases helps in optimizing the choice of algorithm depending on the problem at hand, the size of the data, and the need for real-time predictions.

2. What is Complexity? Big "O" Notation Explained

Time complexity is a way to describe how the computational resources required for an algorithm scale as the size of the input increases. The most common notation to describe time complexity is Big "O" notation. Big "O" focuses on the upper bound, describing the worst-case scenario for how an algorithm behaves as the input size increases.

• n: Typically represents the size of the dataset, i.e., the number of training examples.
• p: Represents the number of features (or dimensions) in each data point.
• T: The number of trees in ensemble methods like Random Forest or Gradient Boosting.
• l: The number of iterations (often seen in iterative algorithms like K-Means or neural networks).
• k: The number of clusters (for K-Means) or the number of neighbors (for K-Nearest Neighbors).
• m: The number of components (for methods like Principal Component Analysis).

For example, if an algorithm has a time complexity of $O(n^2)$, it means that doubling the size of the input data approximately quadruples the time it will take to run.

3. Complexity of Common Machine Learning Algorithms

Let's now explore the time complexity of several popular machine learning algorithms, both for the training and testing phases, to give you a clearer understanding of how to interpret these complexities.

Linear Regression

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(p)$

Explanation: During training, Linear Regression solves a system of linear equations, often by inverting a matrix. Matrix inversion contributes to the $O(p^3)$ complexity, while calculating the normal equations requires $O(np^2)$, which depends on the number of data points $n$ and features $p$. Once the model is trained, making predictions (inference) only requires a dot product between the input features and learned weights, which has a complexity of $O(p)$.

Logistic Regression

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(p)$

Explanation: Logistic Regression uses iterative methods like gradient descent or the Newton-Raphson method to optimize its cost function. The complexity is similar to Linear Regression because each iteration requires $O(np^2)$, and solving the normal equations can take $O(p^3)$. For inference, the complexity remains $O(p)$, as predicting the class probability also involves a dot product.

Naive Bayes

• Training Time: $O(np)$
• Inference Time: $O(p)$

Explanation: Naive Bayes assumes conditional independence among features, making the training process very efficient. Each feature's probability is calculated individually, resulting in a linear complexity of $O(np)$. For inference, it computes the posterior probabilities for each class, which requires iterating over all features, hence the complexity $O(p)$.

Decision Tree

• Training Time: $O(T \cdot n \log n)$ (average), $O(n^2)$ (worst)
• Inference Time: $O(T \cdot \log n)$ (average), $O(n)$ (worst)

Explanation: Building a Decision Tree involves splitting the data recursively, where each split requires sorting the data, which has an average complexity of $O(n \log n)$. For balanced trees, this results in $O(n \log n)$ complexity, but in the worst case (unbalanced trees), the complexity can degrade to $O(n^2)$. During inference, making a prediction involves traversing the tree, which takes $O(\log n)$ for balanced trees but could be as bad as $O(n)$ for unbalanced trees.

Random Forest

• Training Time: $O(T \cdot n \log n)$
• Inference Time: $O(T \cdot \log n)$

Explanation: Random Forest is an ensemble of decision trees, and each tree is built with complexity $O(n \log n)$. Since there are $T$ trees in the forest, the overall complexity is $O(T \cdot n \log n)$. Inference time is also proportional to the number of trees, as predictions need to be aggregated from each tree, giving $O(T \cdot \log n)$.

Gradient Boosted Trees

• Training Time: $O(T \cdot n \log n)$
• Inference Time: $O(T \cdot \log n)$

Explanation: Similar to Random Forest, Gradient Boosted Trees iteratively train $T$ decision trees. However, each tree is trained on the residuals of the previous one. The complexity remains $O(T \cdot n \log n)$, and inference also involves traversing each of the $T$ trees, resulting in $O(T \cdot \log n)$.

Principal Component Analysis (PCA)

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(pm)$

Explanation: PCA computes the covariance matrix, which has complexity $O(np^2)$, and then performs eigenvalue decomposition, which costs $O(p^3)$. After training, projecting a data point onto the top $m$ principal components requires $O(pm$), making inference relatively efficient.

K-Nearest Neighbors (K-NN)

• Training Time: $O(1)$
• Inference Time: $O(np)$

Explanation: K-NN does not have an explicit training phase; it simply stores the dataset. For inference, K-NN computes the distance between the query point and all $n$ data points, with each distance calculation requiring $O(p)$ operations, leading to a total complexity of $O(np)$.

K-Means

• Training Time: $O(l \cdot k \cdot n \cdot p)$
• Inference Time: $O(k \cdot p)$

Explanation: K-Means is an iterative clustering algorithm where $l$ is the number of iterations, $k$ is the number of clusters, $n$ is the number of data points, and $p$ is the number of features. Each iteration involves calculating distances and updating the cluster centroids, resulting in $O(l \cdot k \cdot n \cdot p)$ complexity. Inference involves assigning new points to the nearest cluster, which has complexity $O(k \cdot p)$.

Dense Neural Networks

• Training Time: $O(l \cdot n \cdot p \cdot h)$
• Inference Time: $O(p \cdot h)$

Explanation: Training a dense neural network involves multiple forward and backward passes through the network, with $h$ representing the number of hidden units. Each pass involves calculating activations and gradients, giving $O(l \cdot n \cdot p \cdot h)$ complexity. During inference, only the forward pass is required, leading to $O(p \cdot h)$ complexity.

 

Reading&watching

Andrew Ng - An Introduction to Machine Learning

GeeksforGeeks Team - Understanding Time Complexity in Algorithms

Dheeraj Singh Tomar - Big O Notation in Machine Learning

Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong - Mathematics for Machine Learning

Analytics Vidhya Team - Understanding Random Forest

Scikit-learn Documentation - K-Means Clustering Explained

Artificial Intelligence and Complex Systems series: Intelligence at the Edge of Chaos — Featured paper

Authors: Shiyang Zhang, Aakash Patel, Syed A Rizvi, Nianchen Liu, Sizhuang He, Amin Karbasi, Emanuele Zappala, and David van Dijk.

The paper "Intelligence at the Edge of Chaos" by Zhang et al. (link) explores how intelligence in artificial systems may emerge not from exposure to inherently intelligent data but through interactions with complex environments. By studying Elementary Cellular Automata (ECA), a class of rule-based systems capable of generating diverse behaviors, the authors investigate how system complexity influences the performance of large language models (LLMs) in reasoning and prediction tasks.

The key finding of the paper is the identification of an "edge of chaos" — a critical point between complete order and randomness — where models trained on systems with moderate complexity exhibit superior intelligence. When LLMs are exposed to data generated by ECA rules that balance structure and unpredictability, the models develop more sophisticated reasoning abilities compared to those trained on simple or highly chaotic systems. This finding suggests that complex systems can foster the emergence of intelligence even when the data itself lacks inherent cognitive structure.

The research demonstrates that complexity plays a critical role in shaping the learning process. Models trained on systems with optimal complexity learn to leverage historical information, displaying non-trivial solutions to problems. This principle could be applied across various domains in AI, highlighting the importance of complexity analysis in understanding how intelligence emerges both in machines and natural systems.

The paper contributes to our understanding of emergent intelligence in AI, suggesting that a balanced exposure to complexity is key for developing models that can generalize, reason, and perform effectively on tasks that require adaptability. It provides a framework for further research on how computational systems can replicate cognitive-like behaviors, making it a significant work for those interested in complexity theory, cognitive science, and artificial intelligence.

Bibliography

1. Zhang, S., Patel, A., Rizvi, S.A., Liu, N., He, S., Karbasi, A., Zappala, E., van Dijk, D. (2024). Intelligence at the Edge of Chaos. arXiv.
2. Langton, C.G. (1990). Computation at the edge of chaos. Physica D: Nonlinear Phenomena.

AI's Cognitive Revolution: A Nobel Prize for Deep Learning Pioneers

 

In 2024, a profound moment in the history of artificial intelligence was marked by the awarding of the Nobel Prize in Physics to two pioneers in the field: Geoffrey Hinton and John Hopfield. Their recognition signals both the impact of their work and the broader "cognitive revolution" that AI has catalyzed in recent years. This revolution involves a paradigm shift in how we understand intelligence, cognition, and the potential of machines to replicate—or even surpass—human intellectual abilities.

 

The Cognitive Revolution and the Nobel Prize

The awarding of the Nobel Prize in Physics to Hinton and Hopfield represents a deep acknowledgment of how AI is transforming fields traditionally associated with human cognition. For centuries, physics was viewed as the study of the material universe. Today, with the incorporation of machine learning and neural networks into various scientific disciplines, the boundaries of physics have expanded to include the study of artificial systems that mimic cognitive processes.

The contributions of Hinton and Hopfield have driven this revolution forward. John Hopfield, who is primarily recognized as a statistical physicist, created the Hopfield network in 1982—a system that uses physical concepts like energy minimization to model associative memory and pattern recognition. This breakthrough demonstrated that neural networks could be used to simulate cognitive functions, such as memory retrieval, and allowed physicists and AI researchers to view brain-like computation from a physical and energetic perspective.

Meanwhile, Geoffrey Hinton, often referred to as the "Godfather of AI," is known for revolutionizing deep learning. Hinton’s work on backpropagation, a learning algorithm that enables multi-layer neural networks to adjust their internal parameters, has been one of the most influential in modern AI. His innovations, particularly in convolutional neural networks and the later development of capsule networks, have enabled machines to achieve remarkable performance in image recognition, language understanding, and many other tasks​. These systems, built upon functional models of biological neural networks, now outperform classical AI systems, which relied on more rigid, rule-based algorithms.

The recognition of AI through the lens of the Nobel Prize symbolizes its critical role in reshaping both science and society. As Geoffrey Hinton stated after winning the award, advancements in neural networks will likely have an influence on humanity comparable to the Industrial Revolution​.

 

The Careers and Contributions of Hinton and Hopfield

The lives and careers of both Geoffrey Hinton and John Hopfield are deeply intertwined with the development of modern AI, though they approach it from distinct scientific disciplines.

Geoffrey Hinton was born in London in 1947 into a family of intellectuals. He pursued his studies in cognitive psychology before transitioning into computer science, a journey that ultimately led him to work on artificial neural networks. Hinton’s early work on distributed representations laid the groundwork for representing concepts within neural networks as patterns of activity across many units. His development of backpropagation in the 1980s, along with David Rumelhart and Ronald Williams, allowed neural networks to be trained on large datasets by adjusting internal weights—a method that became the cornerstone of deep learning​.

One of Hinton’s most significant contributions came in the 2010s with the success of AlexNet, a deep neural network developed by his student Alex Krizhevsky, which won the 2012 ImageNet competition. AlexNet’s success demonstrated the power of deep learning to solve complex tasks in computer vision. This breakthrough, in turn, inspired a wave of research that advanced both AI technology and applications​.

Hinton’s work in deep learning goes beyond technical advances; it represents a shift from classical AI approaches based on logic and rules to systems that learn from experience. More recently, Hinton has worked on Capsule Networks and the Forward-Forward Algorithm, innovations that address some of the limitations of current deep learning models by improving how neural networks handle spatial hierarchies and learn in more biologically plausible ways​.

 Backpropagation scheme

Hinton contributed also to the development and popularization of the backpropagation algorithm, a fundamental method for training multi-layer neural networks. This algorithm, introduced in the influential 1986 paper "Learning Representations by Back-Propagating Errors" co-authored with David Rumelhart and Ronald J. Williams, revolutionized machine learning by enabling networks to adjust their weights based on the error of their predictions. This breakthrough laid the foundation for modern deep learning techniques and has been essential in advancing artificial intelligence applications.

 

John Hopfield, born in 1933, trained as a physicist but became a leader in computational neuroscience. His 1982 paper, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” introduced the Hopfield network, a recurrent neural network that could store memories and retrieve them based on incomplete information. His approach, rooted in statistical physics, introduced the idea that memory retrieval could be framed as an energy minimization problem, where the system seeks the state of lowest energy that corresponds to a stored memory​.

Hopfield’s contributions are essential to understanding how physical systems, like the brain, can perform complex computational tasks. His work laid the groundwork for many models of neural computation that are still in use today, influencing both AI and neuroscience.

Example of Hopfield network

Hopfield networks are a form of recurrent neural network designed to model associative memory. These networks consist of a set of neurons that are fully connected to each other and use binary threshold units. Hopfield's key insight was to apply concepts from statistical physics to demonstrate that the network could store and retrieve memories as stable states, known as attractors, through a process of energy minimization. When presented with partial or noisy inputs, the network can converge to a stored memory by minimizing its energy function, simulating how the brain might retrieve incomplete memories. This model provided foundational insights into both neural computation and machine learning and remains influential in studying memory, optimization problems, and collective computation

Understanding Complex Systems

The contributions of Geoffrey Hinton and John Hopfield have significantly advanced our understanding of complex systems by providing models that capture the emergent behavior of neural networks, which are key examples of such systems. Hopfield's work on associative memory networks, grounded in statistical physics, revealed how collective computational abilities emerge from interconnected neurons, pushing the boundaries of neuroscience and computational modeling. Similarly, Hinton’s breakthroughs in deep learning have shown how complex patterns can be learned and generalized from data, reflecting the dynamic nature of biological cognition. These models, inspired by the brain’s neural architecture, have paved the way for AI to solve complex tasks, from image recognition to decision-making.

The multidisciplinary approaches of both scientists are crucial to their success. Hopfield’s background in physics, combined with computational and biological insights, and Hinton’s expertise in psychology, cognitive science, and computer science, exemplify the power of integrating knowledge across fields. This cross-disciplinary perspective has allowed them to bridge abstract theory with practical applications, transforming AI into a field that addresses complex, real-world problems.

 

The Sapienza School of Neural Networks

The history of neural networks is not only a global story but also has deep roots in specific academic institutions. For example, Sapienza University of Rome—where CIPAR LABS are located—played a pioneering role in neural network research, thanks to Prof. Giuseppe Martinelli, who spearheaded work on neural networks in the 1980s. Under his guidance, the circuital approach to neural networks was continued to be developed, treating these systems not as abstract algorithms but as models of electrical circuits with nonlinear components. This approach predated the widespread use of neural networks in computer science and laid the foundation for viewing AI through the lens of electrical engineering​.

The circuital approach emphasizes the physical realizability of neural networks, focusing on how circuits can model the behavior of neurons in a way that is both efficient and scalable. In this tradition, the Department of Information Engineering, Electronics, and Telecommunications (DIET) at Sapienza continues to produce leading research in AI and neural networks. Many of the current professors in the department were trained by Martinelli, and they continue to carry forward this tradition of blending theoretical advances with practical, circuit-based models of neural computation​.

This tradition underscores the idea that before neural networks became algorithmic abstractions, they were rooted in models of real-world systems, providing a physical grounding for what has since become a dominant paradigm in computer science and AI.

 

  Fondamenti di Reti Neurali - Giuseppe Martinelli (with courtesy of the Prof. Fabio Massimo Frattale Mascioli)

Key Papers and Video Materials of Hinton and Hopfield

While both Hinton and Hopfield have written extensively on AI and neural networks, some of their most influential works include:

• Geoffrey Hinton’s "Learning Representations by Back-Propagating Errors" (1986), co-authored with Rumelhart and Williams, which popularized backpropagation​.
• Hinton’s "Dynamic Routing Between Capsules" (2017), which introduced Capsule Networks​.
• "Neural Networks and Physical Systems with Emergent Collective Computational Abilities" (1982) by John Hopfield, introducing the Hopfield Network​.
• Hinton’s course on Coursera (YouTube) "Neural Networks for Machine Learning", an influential online course and foundational text in deep learning​.

 

Bibliography

• Nobel Prize.org: Geoffrey Hinton – Facts​(NobelPrize.org)
• DW: Nobel Prize Announcement
• Encyclopedia Britannica: Geoffrey Hinton Biography
• Wikipedia: Geoffrey Hinton​
• Leader Biography: Hinton's Deep Learning Innovations​
• Profolus: Capsule Networks and AlexNet ​ Wikipedia: John Hopfield​
  Profolus: Hopfield Network Overview

A summary of the European AI Act

 

 

Image source

The advent of generative AI marks a profound "cognitive revolution", transforming how we interact with technology and unlocking new possibilities across various domains. As a game-changing technology, generative AI, exemplified by models like GPT and DALL-E, has captured public attention by demonstrating capabilities in generating text, images, and even complex problem-solving that mimic human creativity. This surge in public awareness was fueled by several high-profile developments, including the release of ChatGPT, which showcased AI's potential in everyday applications and sparked widespread discussions about its implications.

Generative AI differs from traditional AI in its ability to create novel content rather than simply analyzing or categorizing existing data. While traditional AI focuses on recognizing patterns and making decisions based on predefined rules or data, generative AI uses complex algorithms, such as deep learning and neural networks, to produce new, original outputs, such as text, images, or music, that were not explicitly programmed.

The impact of generative AI is expected to be vast, influencing fields such as education, healthcare, entertainment, and content creation. It will drive innovation in these sectors, but also raises important questions about ethics, ownership, and the potential for misuse. Given its transformative power, it is crucial to establish a robust governance framework to guide the responsible development and deployment of generative AI technologies, ensuring they benefit society while minimizing risks.

 Governing the development and deployment of AI through regulatory institutions like the EU is essential to ensuring that these powerful technologies are aligned with public interest, ethical standards, and human rights. Regulatory oversight helps mitigate risks such as bias, misuse, and privacy violations, which can have far-reaching consequences in an AI-driven society. By setting clear guidelines and standards, institutions like the EU can foster innovation while ensuring that AI systems are transparent, accountable, and safe. This governance is crucial not only for protecting citizens but also for maintaining global competitiveness and leadership in the responsible development of AI technologies.

The European AI Act, which officially came into force on August 1, 2024, marks a significant milestone in the global regulation of artificial intelligence. As the first comprehensive AI regulation worldwide, this Act aims to establish a harmonized legal framework across the European Union, addressing the potential risks associated with AI while fostering innovation.

Motivation and Objectives

The AI Act was motivated by the need to manage the dual challenges of promoting AI's economic benefits while safeguarding fundamental rights, health, and safety. The regulation adopts a risk-based approach, classifying AI systems into categories such as minimal risk, high risk, and unacceptable risk. This classification determines the level of regulatory scrutiny and compliance required.

Key Features

1. Risk-Based Regulation: AI systems are categorized based on the potential risk they pose. High-risk systems, such as those used in critical infrastructure or law enforcement, must meet strict requirements, including transparency, human oversight, and rigorous testing. Unacceptable risk AI systems, such as those enabling social scoring by governments, are outright banned.

2. Transparency and Accountability: The Act requires that AI systems provide clear information to users, particularly when the AI interacts directly with individuals, ensuring users are aware they are engaging with AI and can understand the decision-making process.

3. Support for Innovation: To balance regulation with innovation, the Act includes provisions for regulatory sandboxes, where developers can test AI technologies under the supervision of regulatory bodies. This fosters innovation while ensuring compliance with EU standards.

4. Global Impact: The AI Act's extraterritorial application ensures that any AI system used within the EU, regardless of where it was developed, must comply with EU regulations. This positions the EU as a global leader in AI governance, influencing international standards and practices.

The Act's phased implementation, with key obligations for high-risk AI systems becoming enforceable by 2026, provides time for businesses and governments to adapt. This legislation is seen as a crucial step in ensuring that AI development is both innovative and aligned with fundamental European values​.

For further information, please consult the following sources:

European Commission, Goodwin.

We will now provide a summary of the main parts of the document (“AI Act”) issued by the European institutions.

1. Title and Preamble

Title:

• The document is titled the "Artificial Intelligence Act," officially labeled as "Regulation (EU) 2024/... of the European Parliament and of the Council laying down harmonized rules on artificial intelligence (AI) and amending certain Union Legislative Acts."

Preamble:

• The preamble provides the legal basis and the motivation for the regulation. It states that the purpose of the Act is to establish a uniform legal framework within the EU for the development, deployment, and use of AI systems. The regulation aims to promote AI uptake while ensuring that AI systems are aligned with EU values, such as fundamental rights, democracy, the rule of law, and environmental protection.
• It emphasizes the importance of AI systems being human-centric, trustworthy, and safe, and it underlines the need to prevent fragmentation of the internal market due to divergent national regulations.
• The preamble also highlights the balance the regulation seeks to achieve between fostering innovation and protecting public interests like health, safety, and fundamental rights.

2. Recitals

The recitals provide detailed reasoning and context behind the specific provisions of the AI Act. Here is a summary of the key points covered in the recitals:

• Objective of the Regulation: The regulation aims to improve the functioning of the internal market by establishing harmonized rules for AI systems in the EU, promoting innovation while ensuring the protection of health, safety, and fundamental rights.

• Scope and Application: The regulation is designed to apply across different sectors and industries, given the broad applicability of AI systems. It also takes into account the rapid evolution of AI technologies, ensuring that the legal framework remains relevant and adaptable.

• Human-Centric AI: The regulation emphasizes that AI systems should be developed and used in a way that enhances human well-being, with a focus on human dignity, autonomy, and fundamental rights.

• Risk-Based Approach: A core principle of the regulation is the risk-based approach, where AI systems are classified based on the level of risk they pose to public interests and fundamental rights. This approach dictates the level of regulatory scrutiny and obligations imposed on AI providers and users.

• Prohibited AI Practices: The recitals identify certain AI practices that are deemed unacceptable, such as those that manipulate human behavior, exploit vulnerabilities, or involve social scoring by public authorities.

• High-Risk AI Systems: The recitals outline the rationale for categorizing certain AI systems as high-risk, particularly those that could significantly impact health, safety, or fundamental rights. These systems are subject to stricter requirements to ensure their safe and ethical use.

• Transparency and Accountability: The regulation requires transparency in AI systems, ensuring that users and affected individuals are aware of when they are interacting with AI and understanding the decision-making processes involved.

• Governance and Oversight: The recitals stress the need for strong governance mechanisms, including the establishment of supervisory authorities and the European Artificial Intelligence Board, to ensure compliance with the regulation.

• International Cooperation: The regulation also addresses the international dimension, ensuring that AI systems used in the EU, even if developed outside, comply with EU standards. This aims to prevent regulatory evasion and protect EU citizens from harmful AI practices.

   

  3. General Provisions

  The General Provisions section of the AI Act sets the foundational elements of the regulation, including its scope, definitions, and overarching principles. This section is crucial as it establishes the framework within which the entire regulation operates.

  Key Points:

  Scope (Article 1):

• The regulation applies to the development, placement on the market, and use of AI systems within the EU. It covers AI systems regardless of whether they are standalone or embedded within other products.
• The regulation aims to ensure that AI systems are safe, transparent, and align with EU values, particularly concerning fundamental rights and public interests like health and safety.
• Exemptions are provided for AI systems developed and used exclusively for military, defense, or national security purposes, as these areas are outside the regulation's scope.

Definitions (Article 2):

• The regulation provides clear definitions of key terms used throughout the document, such as "AI system," "provider," "user," "high-risk AI system," and "biometric data."
• AI System: Defined as software developed using machine learning, logic-based, or knowledge-based approaches that can, for a given set of human-defined objectives, generate outputs such as predictions, recommendations, or decisions influencing the environments they interact with.
• Provider: Refers to any person or entity that develops, places on the market, or puts into service an AI system.
• User: Any person or entity using an AI system under their authority, except for personal, non-professional use.

Risk Classification (Article 3):

• The regulation adopts a risk-based approach to classify AI systems into different categories: unacceptable risk, high risk, and minimal risk. The level of regulation and obligations imposed depends on the risk classification:
  • Unacceptable Risk: AI systems that pose a clear threat to safety, livelihood, and rights of people are banned outright.
  • High-Risk AI Systems: Systems that could significantly affect individuals' safety or rights are subject to strict requirements, including mandatory conformity assessments, transparency obligations, and human oversight.
  • Minimal Risk AI Systems: These are subject to minimal regulation, primarily focusing on transparency.

General Obligations (Article 4):

• AI providers must ensure that their systems comply with the requirements laid down in the regulation before placing them on the market or putting them into service.
• Providers are responsible for ensuring that their AI systems undergo conformity assessments, are accompanied by the necessary documentation, and meet the required safety, transparency, and robustness standards.
• Providers must also establish and maintain risk management systems throughout the lifecycle of the AI systems to ensure continued compliance with the regulation.

Union-Level Cooperation (Article 5):

• The regulation mandates the establishment of the European Artificial Intelligence Board (EAIB), which will coordinate and support the consistent application of the AI Act across the EU.
• The EAIB will work closely with national authorities to ensure that AI systems deployed within the EU comply with the regulation, fostering a harmonized approach across Member States.

4. Prohibited AI Practices

This section outlines the AI practices that are explicitly banned under the regulation due to their potential to harm individuals or society at large. These prohibitions are essential to ensure that AI technologies do not undermine fundamental rights, democracy, or public safety.

Key Points:

Prohibited AI Practices (Article 6):

• Manipulative AI Systems: AI systems that deploy subliminal techniques beyond an individual's conscious perception to materially distort their behavior in a way that may cause physical or psychological harm are prohibited.
• Exploitation of Vulnerabilities: AI systems that exploit vulnerabilities of specific groups, such as children, disabled individuals, or economically disadvantaged persons, to materially distort their behavior in a way that causes harm, are banned.
• Social Scoring: The use of AI systems by public authorities or private entities to evaluate or classify individuals based on their social behavior, known or inferred personal characteristics, or other subjective factors over a period, which leads to detrimental or unfair treatment, is prohibited.
• Biometric Surveillance: Real-time remote biometric identification systems in publicly accessible spaces for law enforcement purposes are generally prohibited, with narrowly defined exceptions (e.g., for severe public safety threats).

Exceptions and Specific Conditions (Article 7):

• The regulation does provide certain exceptions where the use of otherwise prohibited AI practices may be justified. For instance, the use of real-time biometric identification systems by law enforcement is permitted in cases of significant public interest, such as the prevention of terrorism or the search for missing children, but only under strict conditions and oversight.

   

  5. High-Risk AI Systems

  The section on High-Risk AI Systems is one of the most critical parts of the AI Act. It outlines the specific obligations and requirements for AI systems that are classified as high risk due to their potential impact on people's safety, rights, or significant public interest.

  Key Points:

  Classification of High-Risk AI Systems (Article 8):

• High-risk AI systems are identified based on their intended purpose, the context of their use, and their potential impact on health, safety, and fundamental rights.
• The regulation provides a list of high-risk AI systems in an annex, which includes AI systems used in critical infrastructure (like energy and transport), educational settings, employment, law enforcement, and biometric identification.

Obligations for Providers of High-Risk AI Systems (Article 9):

• Risk Management: Providers must implement a comprehensive risk management system throughout the lifecycle of the AI system. This includes identifying, analyzing, and mitigating risks associated with the AI system before it is placed on the market and continuously during its use.
• Data Governance: High-risk AI systems must be developed using high-quality, relevant, and representative data sets. Providers are required to establish data governance practices that ensure data quality, relevance, and traceability, with a focus on minimizing bias and inaccuracies.
• Technical Documentation: Providers must create and maintain detailed technical documentation that demonstrates the AI system’s compliance with the AI Act. This documentation must include a description of the system’s architecture, data, algorithms, and performance metrics.
• Record-Keeping: Providers must keep logs of the AI system's operations, particularly when the system makes decisions that impact individuals’ rights or safety. These records should be available for audit by regulatory authorities.
• Transparency and Provision of Information: Providers must ensure that their AI systems are transparent, meaning that users can understand how the system operates and how decisions are made. This includes providing clear instructions for use, limitations, and any risks associated with the system.

Obligations for Users of High-Risk AI Systems (Article 10):

• Monitoring and Reporting: Users of high-risk AI systems must monitor the operation of these systems and report any incidents or malfunctions that could affect compliance with the AI Act to the provider or relevant authorities.
• Human Oversight: Users must ensure that AI systems are used under human oversight. This includes setting up mechanisms for intervention when the AI system operates unexpectedly or in a way that could lead to harm.
• Use in Accordance with Instructions: Users must operate high-risk AI systems strictly according to the instructions provided by the system's provider, especially regarding safety and performance limitations.

Conformity Assessment (Article 11):

• High-risk AI systems must undergo a conformity assessment before they can be placed on the market or put into service. This assessment can be conducted either by the provider (for some types of systems) or by a third-party conformity assessment body.
• The conformity assessment includes evaluating the system’s compliance with the AI Act’s requirements, particularly in terms of risk management, data governance, and technical documentation.
• Post-Market Surveillance: Providers must establish and implement a post-market surveillance plan to monitor the performance of high-risk AI systems after they have been deployed. This ensures ongoing compliance with the AI Act and addresses any emerging risks or non-compliances.

Registration of High-Risk AI Systems (Article 12):

• Providers of high-risk AI systems must register their systems in an EU-wide database managed by the European Artificial Intelligence Board (EAIB). This database is intended to ensure transparency and facilitate monitoring and enforcement by authorities.
  

 

6. Transparency Requirements

This section focuses on the obligations related to transparency, which is crucial for ensuring that AI systems are understandable and accountable, particularly for users and those affected by AI decisions.

Key Points:

Transparency Obligations (Article 13):

• Disclosure to Users: Providers must ensure that users are informed that they are interacting with an AI system, especially in cases where it may not be obvious. This is particularly relevant for AI systems that generate or manipulate content, like chatbots or deepfakes.
• Explainability: AI systems must be designed and deployed in a way that allows users to understand the rationale behind the decisions made by the AI. This is essential for maintaining trust and accountability, especially in high-risk applications.
• Disclosure of Capabilities and Limitations: Providers must clearly communicate the capabilities and limitations of the AI system, including any conditions under which the system might fail or produce biased results.

Human-Machine Interaction (Article 14):

• AI systems that interact with humans must be designed to clearly indicate when the user is interacting with a machine, not a human. This is intended to prevent deception and ensure that users are fully aware of the nature of their interaction.
• Feedback Mechanisms: Providers must include mechanisms within the AI system that allow users to provide feedback or report issues. This feedback is crucial for continuous improvement and addressing any unintended consequences or errors in the system’s operation.

 

7. Governance and Oversight

The Governance and Oversight section of the AI Act outlines the structures and mechanisms put in place to ensure compliance with the regulation across the European Union. This section is crucial for maintaining the integrity and effectiveness of the AI Act through coordinated supervision, enforcement, and cooperation between various authorities.

Key Points:

European Artificial Intelligence Board (EAIB) (Article 15):

• The AI Act establishes the European Artificial Intelligence Board (EAIB) to oversee the implementation and enforcement of the regulation across the EU.
• Composition: The EAIB will be composed of representatives from each Member State's national supervisory authority, the European Commission, and other relevant EU bodies. It will be chaired by a representative from the European Commission.
• Functions: The EAIB will play a central role in ensuring a consistent application of the AI Act across the EU. Its duties include:
  • Guidance: Providing guidelines, recommendations, and best practices for the implementation of the AI Act.
  • Coordination: Facilitating cooperation between national supervisory authorities and ensuring consistent enforcement of the AI Act across Member States.
  • Advisory Role: Advising the European Commission on matters related to AI, including updates to the list of high-risk AI systems and other regulatory aspects.
  • Monitoring: Overseeing the operation of the EU-wide database of high-risk AI systems and ensuring that the registration and reporting requirements are met.

National Supervisory Authorities (Article 16):

• Each Member State is required to designate one or more national supervisory authorities responsible for enforcing the AI Act within their jurisdiction.
• Powers: These authorities are granted wide-ranging powers to investigate AI systems, conduct audits, require the disclosure of documentation, and impose penalties for non-compliance.
• Responsibilities: National authorities must monitor AI systems' compliance with the regulation, particularly in relation to high-risk AI systems. They are also responsible for ensuring that providers and users adhere to their obligations under the AI Act.
• Cooperation: National supervisory authorities are required to cooperate closely with the EAIB and other national authorities to ensure uniform enforcement of the regulation across the EU.

Market Surveillance and Enforcement (Article 17):

• The regulation empowers national market surveillance authorities to take necessary actions to ensure that AI systems placed on the market or put into service comply with the AI Act.
• Enforcement Actions: Authorities can:
  • Conduct Inspections: Inspect premises, products, and documentation related to AI systems.
  • Issue Corrective Measures: Require providers to bring non-compliant AI systems into conformity with the regulation, withdraw them from the market, or recall them.
  • Penalties: Impose administrative fines and other penalties on providers or users who fail to comply with the AI Act.
• Complaint Mechanism: Individuals or organizations can lodge complaints with national supervisory authorities if they believe that an AI system violates the AI Act. Authorities are required to investigate such complaints and take appropriate action.

Reporting Obligations (Article 18):

• Providers of high-risk AI systems must report any serious incidents or malfunctions to the relevant national supervisory authority. These reports help authorities monitor the ongoing compliance of AI systems and address any emerging risks.
• Annual Reports: National authorities must submit annual reports to the EAIB on the use, risks, and incidents related to AI systems within their jurisdiction. This information helps the EAIB in its coordination and monitoring role.

Regulatory Sandboxes (Article 19):

• The AI Act encourages Member States to establish regulatory sandboxes for AI systems, which are controlled environments where AI providers can test innovative solutions under the supervision of regulatory authorities.
• Purpose: Sandboxes allow providers to experiment with new AI technologies in a way that ensures compliance with the AI Act, while also fostering innovation and allowing regulators to gain insights into emerging technologies.
• Conditions: Participation in regulatory sandboxes is voluntary and subject to specific conditions, including requirements related to risk management, transparency, and human oversight.

 

8. International Aspects

This section addresses the international dimension of the AI Act, particularly how it applies to AI systems developed or operated outside the EU but used within its borders. The AI Act has a global reach, ensuring that AI systems affecting EU citizens comply with EU standards, even if they originate elsewhere.

Key Points:

Extraterritorial Application (Article 20):

• The AI Act applies to providers and users of AI systems that are established outside the EU but place AI systems on the EU market or use them within the EU. This provision ensures that AI systems developed abroad are subject to the same rules as those developed within the EU if they have an impact on EU citizens.
• Responsibility of EU-Based Entities: EU-based entities that import or distribute AI systems developed outside the EU are responsible for ensuring that these systems comply with the AI Act.

International Cooperation (Article 21):

• The regulation encourages international cooperation on AI standards and governance, promoting the EU’s approach to trustworthy AI on a global scale.
• Bilateral and Multilateral Agreements: The European Commission is empowered to negotiate agreements with third countries and international organizations to facilitate the exchange of information, cooperation on enforcement, and alignment of AI standards.

Transfer of AI Systems (Article 22):

• The AI Act regulates the transfer of AI systems to third countries, ensuring that such transfers do not compromise the protection of fundamental rights as outlined in the regulation.
• Conditions for Transfer: AI systems can only be transferred to third countries if the receiving entity ensures equivalent levels of protection for fundamental rights and complies with the requirements of the AI Act.

 

9. Annexes

The Annexes of the AI Act provide detailed supplementary information that is critical for the practical implementation and enforcement of the regulation. These sections often include specific lists, technical standards, and procedural guidelines that help clarify and operationalize the broader provisions laid out in the main body of the regulation.

Key Points:

Annex I: List of High-Risk AI Systems

• Classification: This annex provides a detailed list of AI systems that are classified as high-risk under the regulation. These are systems that have a significant impact on individuals' safety, rights, or well-being and thus require strict compliance with the AI Act.
• Examples:
  • Critical Infrastructure: AI systems used in managing critical infrastructure, such as energy or transport networks, where failures could have severe consequences.
  • Educational and Vocational Training: AI systems used to evaluate students or applicants, which could determine access to education or employment.
  • Employment, Workers Management, and Access to Self-Employment: AI systems that make decisions about hiring, performance evaluation, promotion, and termination of employment.
  • Law Enforcement: AI systems used in predictive policing, criminal risk assessments, or surveillance.
  • Biometric Identification and Categorization: AI systems used for biometric identification (e.g., facial recognition) in public spaces.
  • Access to and Use of Essential Private and Public Services: AI systems that determine access to credit, public benefits, or emergency services.

Annex II: Requirements for High-Risk AI Systems

• Technical Documentation: Detailed requirements for the technical documentation that providers must prepare for high-risk AI systems. This includes descriptions of the system's architecture, algorithms, data management processes, and risk management strategies.
• Risk Management: Specific guidelines for implementing a risk management framework throughout the AI system’s lifecycle, including the identification, analysis, and mitigation of potential risks.
• Data Governance: Standards for ensuring data quality, relevance, and representativeness, particularly to avoid bias and ensure the fairness and accuracy of AI systems.
• Transparency and Information Provision: Requirements for making AI systems transparent to users, including clear instructions on the system's capabilities, limitations, and conditions of use.
• Human Oversight: Guidelines for implementing human oversight mechanisms to ensure that AI systems can be monitored and intervened with when necessary, preventing harmful outcomes.

Annex III: Conformity Assessment Procedures

• Self-Assessment: For certain high-risk AI systems, providers are allowed to conduct internal conformity assessments to verify compliance with the AI Act’s requirements.
• Third-Party Assessment: For other high-risk AI systems, an external conformity assessment by a notified body is mandatory. This annex outlines the procedures for such assessments, including the roles and responsibilities of the notified bodies.
• Post-Market Surveillance: Detailed procedures for the ongoing monitoring and surveillance of AI systems after they have been placed on the market. This includes guidelines for reporting incidents and updating the AI system in response to new risks or regulatory changes.

Annex IV: Standards and Specifications

• Harmonized Standards: This annex lists the harmonized European standards that AI systems should comply with to meet the requirements of the AI Act. These standards are developed by recognized European standardization organizations and cover various aspects of AI system development, such as safety, transparency, and data governance.
• Technical Specifications: In the absence of harmonized standards, this annex provides technical specifications that can be used as a reference for compliance. These may include guidelines on algorithm design, data handling, and system security.

Annex V: Registration of High-Risk AI Systems

• EU-Wide Database: This annex details the process for registering high-risk AI systems in the EU-wide database managed by the European Artificial Intelligence Board (EAIB). It includes the information that must be provided during registration, such as the system’s purpose, risk classification, and conformity assessment results.
• Reporting Obligations: Guidelines on the reporting obligations for providers and users of high-risk AI systems, including how to report serious incidents or breaches of compliance.

Annex VI: List of Prohibited Practices

• Detailed Description: This annex provides a comprehensive list of AI practices that are banned under the AI Act. Each prohibited practice is described in detail, including the rationale for its prohibition and the specific risks it poses to individuals or society.
• Examples:
  • AI systems that manipulate human behavior in ways that are harmful or deceptive.
  • AI systems that exploit vulnerabilities of specific groups (e.g., children, disabled persons).
  • AI systems used for social scoring by public authorities or private entities, leading to discriminatory outcomes.

 We remark that, The AI Act represents a significant regulatory framework aimed at ensuring that AI systems developed, marketed, or used within the EU are safe, transparent, and aligned with fundamental European values, including the protection of human rights and the promotion of trustworthy AI.

 

AI Act: A Citizen's Perspective

The European AI Act represents a significant step towards safeguarding the rights, freedoms, and safety of citizens in the face of rapidly advancing artificial intelligence technologies. From a citizen's point of view, the AI Act provides several important protections and assurances:

1. Protection of Fundamental Rights

• Human-Centric AI: The AI Act is grounded in the principle that AI systems must serve people, not the other way around. This ensures that AI technologies are designed and used in ways that respect human dignity, autonomy, and the fundamental rights enshrined in the European Union’s legal framework.
• Prohibition of Harmful AI Practices: The Act explicitly bans AI systems that can manipulate or exploit individuals in harmful ways. For example, AI systems that use subliminal techniques to influence behavior without a person’s conscious awareness, or those that exploit vulnerable groups such as children, are strictly prohibited. This ensures that citizens are protected from technologies that could otherwise harm their physical or psychological well-being.

2. Transparency and Awareness

• Right to Know: Citizens are given the right to know when they are interacting with an AI system. Whether it’s through online platforms, customer service, or automated decision-making tools, the AI Act mandates that these systems must clearly disclose their nature as AI. This transparency empowers individuals to make informed decisions about their interactions and engagements with AI technologies.
• Explainability of AI Decisions: In scenarios where AI systems make decisions that impact individuals—such as determining eligibility for services, loans, or even employment—citizens are entitled to understand the reasoning behind these decisions. The AI Act requires that these systems be designed to provide clear, understandable explanations, thereby reducing the risk of opaque or biased decision-making.

3. Safety and Accountability

• High-Risk AI Systems: For AI systems deemed high-risk—such as those used in healthcare, law enforcement, or critical infrastructure—the AI Act imposes stringent safety and accountability measures. Citizens can feel assured that these systems are subject to rigorous testing, ongoing monitoring, and strict oversight to ensure they operate safely and fairly.
• Recourse and Redress: If an AI system causes harm or operates in a way that infringes on a person’s rights, the AI Act ensures that citizens have clear avenues for recourse. Individuals can report incidents, lodge complaints, and seek redress through national supervisory authorities, which are empowered to take corrective actions and impose penalties on non-compliant entities.

4. Privacy and Data Protection

• Safeguarding Personal Data: AI systems often rely on vast amounts of data, including personal information. The AI Act reinforces existing EU data protection laws by ensuring that AI systems processing personal data do so in a way that respects privacy rights. Citizens can expect that their data will be handled with care, security, and integrity, minimizing risks such as unauthorized access or misuse.
• Biometric Data Protections: Given the sensitivity of biometric data, the AI Act places specific restrictions on AI systems that use such data for identification or categorization purposes. This includes stringent controls on the use of facial recognition technologies in public spaces, limiting their application to exceptional cases of significant public interest, such as preventing terrorism.

5. Empowerment Through AI Literacy

• AI Literacy Initiatives: The AI Act encourages the development of AI literacy programs, ensuring that citizens are equipped with the knowledge to understand, interact with, and critically assess AI systems. These initiatives aim to empower individuals by providing them with the tools to navigate the AI-driven aspects of modern life, from understanding AI in consumer products to recognizing their rights in digital environments.

6. Public Consultation and Engagement

• Involvement in AI Governance: The AI Act promotes the idea that citizens should have a voice in how AI technologies are governed. Through public consultations and participatory mechanisms, individuals can contribute to shaping the policies and standards that will influence the development and deployment of AI systems. This ensures that the governance of AI is not solely in the hands of technologists and policymakers but reflects the broader societal values and concerns.

This comprehensive framework established by the AI Act is designed to protect and empower citizens as they navigate an increasingly AI-driven world. It ensures that while AI technologies continue to advance, they do so in ways that are safe, transparent, and aligned with the values of European society.

 

AI Act: A Government and Institutional Perspective

From the viewpoint of governments and institutions, the European AI Act serves as a robust regulatory framework designed to manage the development, deployment, and oversight of artificial intelligence across the European Union. The Act provides a structured approach to ensure that AI technologies align with public policy objectives, safeguard citizens' rights, and promote innovation within a controlled and ethical environment.

1. Regulatory Framework and Compliance

• Harmonization Across Member States: One of the primary objectives of the AI Act is to establish a uniform regulatory environment across the EU. This harmonization prevents fragmentation within the internal market, ensuring that AI systems can be developed, marketed, and used under consistent rules, regardless of the Member State. For governments, this facilitates easier cross-border cooperation and reduces the complexity of enforcing AI regulations.
• Conformity Assessments: Governments are tasked with ensuring that high-risk AI systems undergo rigorous conformity assessments. These assessments, either conducted internally by providers or through third-party bodies, ensure that AI systems comply with the strict safety, transparency, and ethical standards mandated by the AI Act. This system helps maintain public trust in AI technologies and ensures that only compliant and safe AI systems enter the market.

2. Institutional Oversight and Enforcement

• National Supervisory Authorities: Each Member State is required to establish or designate one or more national supervisory authorities responsible for enforcing the AI Act. These authorities are empowered to monitor AI systems, conduct investigations, and impose penalties for non-compliance. The role of these authorities is crucial in maintaining the integrity of AI deployments and ensuring that providers and users adhere to the regulations.
• European Artificial Intelligence Board (EAIB): The AI Act establishes the EAIB as a central body to coordinate the enforcement of the Act across the EU. The EAIB ensures consistency in the application of the regulation, provides guidance to national authorities, and facilitates cooperation between Member States. For governments, the EAIB serves as a vital resource and partner in managing the challenges associated with AI governance.
• Market Surveillance: Governments are responsible for market surveillance to ensure that AI systems placed on the market are safe and compliant. This includes the authority to conduct inspections, mandate corrective actions, and, if necessary, remove non-compliant AI systems from the market. Effective market surveillance protects citizens and reinforces the credibility of the regulatory framework.

3. Promotion of Innovation and Ethical AI

• Regulatory Sandboxes: To foster innovation while ensuring compliance, the AI Act encourages the creation of regulatory sandboxes. These controlled environments allow AI providers to test and develop new technologies under the supervision of regulatory authorities. For governments, these sandboxes are instrumental in balancing the need for technological advancement with the obligation to protect public interests. They also provide insights into emerging technologies and help refine regulatory approaches.
• Support for SMEs and Startups: Recognizing the role of small and medium-sized enterprises (SMEs) and startups in AI innovation, the AI Act includes provisions that offer these entities specific support. This includes tailored guidance on compliance and easier access to regulatory sandboxes. Governments are encouraged to provide additional resources and support to these enterprises, ensuring that they can compete in the AI market while adhering to the highest standards of safety and ethics.

4. International Cooperation and Global Leadership

• Extraterritorial Application: The AI Act has a global reach, applying not only to AI systems developed within the EU but also to those that are marketed or used within the EU, regardless of their origin. For governments, this extraterritorial application ensures that AI systems affecting EU citizens are subject to EU standards, thereby preventing regulatory arbitrage and protecting citizens from potentially harmful technologies developed abroad.
• Global Standards and Diplomacy: The AI Act positions the EU as a global leader in AI governance. Governments and institutions are encouraged to engage in international dialogues and negotiations to promote the EU’s approach to AI regulation globally. This not only helps in setting international AI standards but also ensures that European values, such as human rights and ethical AI use, are reflected in global AI governance frameworks.

5. Data Governance and Privacy Protection

• Alignment with GDPR: The AI Act reinforces existing data protection laws, particularly the General Data Protection Regulation (GDPR). Governments and institutions must ensure that AI systems handling personal data do so in compliance with GDPR. This includes overseeing the use of biometric data and ensuring that AI systems respect individuals’ privacy rights.
• Biometric Data Regulation: Specific provisions within the AI Act regulate the use of biometric data, especially in high-risk scenarios such as biometric identification in public spaces. Governments are responsible for enforcing these provisions, ensuring that the use of such technologies is strictly controlled and limited to scenarios that serve significant public interests.

6. Public Engagement and AI Literacy

• Public Consultation: The AI Act promotes the involvement of citizens in AI governance through public consultations. Governments are encouraged to facilitate these consultations, ensuring that the development and deployment of AI systems are informed by public opinion and societal values. This helps in building public trust and ensuring that AI policies are responsive to the concerns of citizens.
• AI Literacy Programs: Governments are also encouraged to implement AI literacy programs, helping citizens understand and engage with AI technologies. These programs aim to equip individuals with the knowledge to navigate an AI-driven world, making informed decisions and understanding their rights in the digital age.

Conclusion

From a government and institutional perspective, the European AI Act provides a comprehensive framework for managing the opportunities and challenges presented by AI technologies. It empowers national authorities, fosters innovation, and ensures that AI systems are developed and deployed in ways that align with European values and public policy objectives. By implementing the AI Act effectively, governments can protect citizens, promote ethical AI use, and position the EU as a global leader in AI governance.

 

 

 Image source: Goodwin

 

 For a deeper understanding of the European AI Act:

High-level summary of the AI Act

What is the Artificial Intelligence Act of the European Union (EU AI Act)?

Analyzing the European Union AI Act: What Works, What Needs Improvement

AI and Product Safety Standards Under the EU AI Act