4IZ232 — Umělá inteligence a její aplikace

O předmětu

Předmět pokrývá celé spektrum umělé inteligence — od klasických algoritmů prohledávání přes strojové učení až po moderní aplikace v NLP a etiku AI. Kombinuje teorii s praktickými příklady v Pythonu pomocí knihovny scikit-learn.

1. Prohledávání stavového prostoru

Základní pojmy

Stavový prostor je čtveřice (S, A, s₀, G), kde:

• S = množina všech stavů
• A = množina akcí (přechodů)
• s₀ = počáteční stav
• G = množina cílových stavů

Kritéria hodnocení algoritmů:

Kritérium	Popis
Úplnost	Najde řešení, pokud existuje?
Optimálnost	Najde nejlevnější řešení?
Časová složitost	Kolik uzlů prozkoumá?
Prostorová složitost	Kolik uzlů drží v paměti?

BFS — prohledávání do šířky

Prochází strom po vrstvách, používá frontu (FIFO). Garantuje nejkratší cestu (pokud jsou všechny hrany stejně drahé).

from collections import deque

def bfs(graph, start, goal):
    queue = deque([(start, [start])])
    visited = set([start])
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

• Časová složitost: O(b^d), kde b = větvící faktor, d = hloubka řešení
• Prostorová složitost: O(b^d) — drží celou vrstvu v paměti
• Úplný: ANO | Optimální: ANO (stejné ceny hran)

DFS — prohledávání do hloubky

Používá zásobník (LIFO), prochází co nejhlouběji.

def dfs(graph, start, goal, visited=None, path=None):
    if visited is None:
        visited = set()
        path = [start]
    visited.add(start)
    if start == goal:
        return path
    for neighbor in graph[start]:
        if neighbor not in visited:
            result = dfs(graph, neighbor, goal, visited, path + [neighbor])
            if result:
                return result
    return None

• Časová složitost: O(b^m), kde m = maximální hloubka
• Prostorová složitost: O(b·m) — výhoda oproti BFS!
• Úplný: NE (může zacyklit) | Optimální: NE

A* — informované prohledávání

Kombinuje skutečnou cenu g(n) a heuristiku h(n): f(n) = g(n) + h(n)

Heuristika musí být přípustná (nepřeceňuje skutečnou cenu) a konzistentní (h(n) ≤ c(n,n') + h(n')).

import heapq

def astar(graph, start, goal, heuristic):
    # (f_score, node, path, g_score)
    open_set = [(heuristic(start, goal), start, [start], 0)]
    visited = {}
    while open_set:
        f, node, path, g = heapq.heappop(open_set)
        if node in visited:
            continue
        visited[node] = g
        if node == goal:
            return path, g
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                new_g = g + cost
                new_f = new_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (new_f, neighbor, path + [neighbor], new_g))
    return None, float('inf')

# Příklad heuristiky — Manhattanská vzdálenost pro grid
def manhattan(pos, goal):
    return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])

Porovnání algoritmů

Algoritmus	Úplný	Optimální	Čas	Prostor
BFS	ANO	ANO	O(b^d)	O(b^d)
DFS	NE	NE	O(b^m)	O(bm)
DFS s omez. hloubkou	NE	NE	O(b^l)	O(bl)
Iterativní prohlubo.	ANO	ANO	O(b^d)	O(bd)
A*	ANO	ANO	O(b^d)	O(b^d)

2. Reprezentace znalostí

Výroková logika

Logické spojky: ¬ (negace), ∧ (konjunkce), ∨ (disjunkce), → (implikace), ↔ (ekvivalence)

Inferenční pravidla:

• Modus ponens: (A → B) ∧ A ⊢ B
• Modus tollens: (A → B) ∧ ¬B ⊢ ¬A
• Resolution: (A ∨ B) ∧ (¬A ∨ C) ⊢ (B ∨ C)

Predikátová logika (logika prvního řádu)

Rozšiřuje výrokovou logiku o kvantifikátory a predikáty:

• ∀x P(x) — pro všechna x platí P(x)
• ∃x P(x) — existuje x, pro které platí P(x)

# Příklad: Sokrates je smrtelný
∀x (Člověk(x) → Smrtelný(x))
Člověk(Sokrates)
⊢ Smrtelný(Sokrates)        # Modus ponens

Ontologie a sémantický web

Ontologie = formální popis pojmů a jejich vztahů v doméně.

Komponenty ontologie:

• Třídy (koncepty) — např. Osoba, Zvíře
• Vlastnosti (role) — např. máRodiče, pracujeV
• Instance — konkrétní objekty
• Axiomy — omezení a pravidla

OWL (Web Ontology Language) — standard W3C pro ontologie na webu.

Expertní systémy

Architektura: báze znalostí + inferenční engine + uživatelské rozhraní

Typy inference:

• Dopředné řetězení (forward chaining) — z faktů odvozujeme závěry (data-driven)
• Zpětné řetězení (backward chaining) — od cíle k faktům (goal-driven)

# Jednoduchý expertní systém s pravidly
rules = [
    {"if": ["horečka", "kašel"], "then": "chřipka"},
    {"if": ["horečka", "bolest_hlavy"], "then": "chřipka"},
    {"if": ["chřipka"], "then": "doporučit_antipyretika"},
]

def forward_chain(facts, rules):
    new_facts = set(facts)
    changed = True
    while changed:
        changed = False
        for rule in rules:
            if all(p in new_facts for p in rule["if"]):
                if rule["then"] not in new_facts:
                    new_facts.add(rule["then"])
                    changed = True
    return new_facts

3. Strojové učení — Supervised Learning

Lineární regrese

Hledáme parametry θ tak, aby ŷ = θ₀ + θ₁x₁ + ... + θₙxₙ minimalizovalo MSE.

Funkce ztráty (MSE): MSE = (1/m) · Σᵢ (ŷᵢ - yᵢ)²

Normální rovnice (analytické řešení): θ = (XᵀX)⁻¹ · Xᵀ · y

Gradientní sestup: θⱼ := θⱼ - α · (∂J/∂θⱼ)

kde α = learning rate, J = cost function

from sklearn.linear_model import LinearRegression, Ridge, Lasso
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# Příprava dat
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Model
model = LinearRegression()
model.fit(X_train_scaled, y_train)
y_pred = model.predict(X_test_scaled)

print(f"R² = {r2_score(y_test, y_pred):.4f}")
print(f"RMSE = {np.sqrt(mean_squared_error(y_test, y_pred)):.4f}")
print(f"Koeficienty: {model.coef_}")

Regularizace:

• Ridge (L2): J(θ) = MSE + α·Σθⱼ² — zmenšuje koeficienty
• Lasso (L1): J(θ) = MSE + α·Σ

  θⱼ

  — provádí výběr příznaků (nuluje koeficienty)
• Elastic Net: kombinace L1 + L2

Rozhodovací stromy

Rekurzivně dělí prostor příznaků. Kritéria dělení:

• Gini index: G = 1 - Σₖ pₖ² (pro klasifikaci)
• Entropie: H = -Σₖ pₖ · log₂(pₖ)
• MSE (pro regresi)

from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

# Rozhodovací strom
dt = DecisionTreeClassifier(max_depth=5, min_samples_leaf=10, random_state=42)
dt.fit(X_train, y_train)
print(export_text(dt, feature_names=feature_names))

# Random Forest (ensemble bagging)
rf = RandomForestClassifier(n_estimators=100, max_features="sqrt", random_state=42)
rf.fit(X_train, y_train)

# Důležitost příznaků
importances = pd.Series(rf.feature_importances_, index=feature_names)
print(importances.sort_values(ascending=False))

Ensemblové metody:

Metoda	Princip	Výhoda
Bagging	Paralelní trénink na bootstrap vzorcích	Snižuje variance
Random Forest	Bagging + náhodný výběr příznaků	Robustní, málokdy přetrénuje
Boosting	Sekvenční — každý model opravuje chyby předchozího	Nízký bias
Gradient Boosting	Boosting s gradientním sestupem	Velmi přesný (XGBoost, LightGBM)

Support Vector Machine (SVM)

Hledá hyperrovinu maximalizující margin (vzdálenost mezi třídami).

Tvrdý margin: min ½‖w‖² s.t. yᵢ(w·xᵢ + b) ≥ 1 Měkký margin: min ½‖w‖² + C·Σξᵢ s.t. yᵢ(w·xᵢ + b) ≥ 1 - ξᵢ

Kernel trick — transformace do vyšší dimenze:

• Lineární: K(x,y) = x·y
• RBF (Gaussovský): K(x,y) = exp(-γ‖x-y‖²)
• Polynomiální: K(x,y) = (x·y + c)^d

from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV

svm = SVC(kernel="rbf", C=1.0, gamma="scale")
# Grid search pro hyperparametry
param_grid = {"C": [0.1, 1, 10, 100], "gamma": [0.001, 0.01, 0.1, 1]}
grid_search = GridSearchCV(SVC(kernel="rbf"), param_grid, cv=5, scoring="accuracy")
grid_search.fit(X_train_scaled, y_train)
print(f"Nejlepší parametry: {grid_search.best_params_}")

Neuronové sítě

Perceptron — základní stavební blok: ŷ = σ(w·x + b)

Aktivační funkce:

• Sigmoid: σ(z) = 1/(1+e⁻ᶻ) — výstup (0,1), vhodné pro výstup
• ReLU: f(z) = max(0,z) — skryté vrstvy, zabraňuje vanishing gradient
• Tanh: tanh(z) = (e^z - e⁻ᶻ)/(e^z + e⁻ᶻ) — výstup (-1,1)
• Softmax: pro víceté třídění

Backpropagation — výpočet gradientů pomocí chain rule: ∂L/∂wᵢⱼ = ∂L/∂aⱼ · ∂aⱼ/∂zⱼ · ∂zⱼ/∂wᵢⱼ

from sklearn.neural_network import MLPClassifier

mlp = MLPClassifier(
    hidden_layer_sizes=(100, 50),  # 2 skryté vrstvy
    activation="relu",
    solver="adam",
    alpha=0.001,          # L2 regularizace
    max_iter=500,
    random_state=42
)
mlp.fit(X_train_scaled, y_train)

4. Strojové učení — Unsupervised Learning

K-means clustering

Algoritmus:

1. Inicializuj k centroidů (náhodně nebo K-means++)
2. Přiřaď každý bod k nejbližšímu centroidu
3. Přepočítej centroidy jako průměr přiřazených bodů
4. Opakuj 2-3 do konvergence

Inertia = Σᵢ Σⱼ∈Cᵢ ‖xⱼ - μᵢ‖² (minimalizujeme)

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt

# Elbow method — výběr k
inertias = []
for k in range(1, 11):
    km = KMeans(n_clusters=k, random_state=42, n_init=10)
    km.fit(X)
    inertias.append(km.inertia_)

# Silhouette score — kvalita clusterů
km = KMeans(n_clusters=4, random_state=42, n_init=10)
labels = km.fit_predict(X)
score = silhouette_score(X, labels)
print(f"Silhouette score: {score:.4f}")  # blíže 1 = lepší

PCA — analýza hlavních komponent

Redukce dimenzionality hledáním směrů maximální variance.

Kroky:

1. Standardizuj data
2. Vypočítej kovarianční matici: C = (1/n)XᵀX
3. Eigen-dekompozice: C·v = λ·v
4. Seřaď vlastní vektory dle vlastních čísel
5. Promítni data: Z = X·W (W = matice k hlavních komponent)

from sklearn.decomposition import PCA

pca = PCA(n_components=0.95)  # zachovat 95% variance
X_reduced = pca.fit_transform(X_scaled)
print(f"Původní dimenze: {X.shape[1]}")
print(f"Redukovaná dimenze: {X_reduced.shape[1]}")
print(f"Vysvětlená variance: {pca.explained_variance_ratio_}")

5. Zpracování přirozeného jazyka (NLP)

Základní kroky předzpracování

1. Tokenizace — rozdělení textu na tokeny (slova, věty)
2. Stop words — odstranění neinformativních slov
3. Stemming — redukce na kořen slova (run, running → run)
4. Lemmatizace — morfologická normalizace (běžel → běžet)
5. TF-IDF — váhování slov dle důležitosti

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.naive_bayes import MultinomialNB
from sklearn.pipeline import Pipeline

# Pipeline pro klasifikaci textu
pipeline = Pipeline([
    ("tfidf", TfidfVectorizer(
        max_features=10000,
        ngram_range=(1, 2),    # unigramy + bigramy
        stop_words="english"
    )),
    ("clf", MultinomialNB(alpha=0.1))
])

pipeline.fit(X_train_texts, y_train)

TF-IDF: TF(t,d) = počet výskytů t v d / celkový počet slov v d IDF(t) = log(N / df(t)) TF-IDF(t,d) = TF(t,d) · IDF(t)

Word Embeddings

Word2Vec — slova reprezentovaná jako vektory v kontinuálním prostoru, kde podobná slova jsou si blízká. Král - Muž + Žena ≈ Královna.

Architektury: CBOW (předpovídá slovo z kontextu) a Skip-gram (z jednoho slova předpovídá kontext).

Transformer modely: BERT, GPT — attention mechanismus zachycuje kontext celé věty.

6. Etika AI

Hlavní principy

Princip	Popis
Transparentnost	AI musí být vysvětlitelná (XAI)
Spravedlnost	Absence diskriminace (bias v datech)
Soukromí	GDPR, ochrana osobních dat
Bezpečnost	Robustnost vůči adversariálním útokům
Odpovědnost	Kdo nese odpovědnost za rozhodnutí AI?

Typy biasu v AI:

• Historical bias — data reflektují minulé nerovnosti
• Representation bias — podreprezentované skupiny v trénovacích datech
• Measurement bias — chybné měření pro různé skupiny
• Algorithmic bias — model zesiluje existující nerovnosti

EU AI Act (2024) — regulace AI dle rizika:

• Nepřijatelné riziko: ban (sociální scoring státem)
• Vysoké riziko: přísné požadavky (zdravotnictví, doprava)
• Omezené riziko: povinnost transparentnosti (chatboti)
• Minimální riziko: volné použití

Tipy pro zkoušku

1. Prohledávání: Umět nakreslit strom stavového prostoru a simulovat BFS/DFS/A. Pro A vždy spočítat f(n) = g(n) + h(n) pro každý uzel.
2. Logika: Procvičit rezoluci — převod do klauzální formy a aplikace resolution rule.
3. ML — bias vs. variance tradeoff: Underfitting = vysoký bias, overfitting = vysoká variance. Řešení: regularizace, více dat, cross-validation.
4. K-means: Pamatovat omezení — citlivost na odlehlé hodnoty, nutnost zadat k předem, lokální optima (proto více inicializací).
5. Evaluace modelů: Rozdíl přesnost vs. recall vs. F1 — kdy který použít (imbalanced dataset → F1 nebo AUC-ROC).
6. PCA: Standardizace dat je povinná před PCA! Jinak dominují příznaky s velkým rozptylem.
7. Etika: EU AI Act — kategorie rizik a požadavky pro vysoké riziko.

Doporučené zdroje

• Russell, S. & Norvig, P.: Artificial Intelligence: A Modern Approach (4. vydání) — Bible AI
• Géron, A.: Hands-On Machine Learning with Scikit-Learn, Keras & TensorFlow — praktická část
• Přednáškové slidy FIS VŠE (ISIS)
• Sklearn dokumentace: https://scikit-learn.org/stable/user_guide.html
• Kaggle kurzy: ML, NLP (zdarma, s certifikátem)
• 3Blue1Brown YouTube: Neural Networks series (vizuální vysvětlení)
• fast.ai: Practical Deep Learning for Coders (zdarma)