Kursus Matematika untuk AI · Pelajaran 47 dari 180

Gram–Schmidt Membangun Arah Ortogonal

Jalankan Gram–Schmidt dengan tangan dan di NumPy, baca ukuran residual sebagai diagnosis tumpang tindih, serta kenali ketidakstabilan akibat urutan dan floating point.

Bagikan artikel ini

Dua arah fitur dapat terlihat berbeda tetapi membawa hampir seluruh informasi yang sama. Menormalisasi masing-masing arah hanya memperbaiki panjangnya; langkah itu tidak menghapus tumpang tindih. Gram–Schmidt menghapus bagian dari setiap vektor baru yang sudah dijelaskan oleh arah sebelumnya, lalu menormalisasi sisanya. Panjang sisa tersebut menjadi diagnosis yang berguna: nilai nol berarti ketergantungan, sedangkan nilai yang sangat kecil memperingatkan bahwa arah baru hampir redundan atau rapuh secara numerik.

Di akhir pelajaran ini, Anda akan dapat menjalankan Gram–Schmidt pada dua atau tiga vektor, memverifikasi keluaran ortonormal, dan menafsirkan ukuran residual sebagai sinyal tumpang tindih yang bergantung pada skala. Anda juga akan tahu mengapa urutan masukan dan toleransi floating point yang dipilih memengaruhi hasil.

Hasil belajar: Jalankan Gram–Schmidt pada dua atau tiga vektor dan identifikasi ketidakstabilan.

Pelajaran 046: Basis Ortonormal Menyederhanakan Koordinat menunjukkan mengapa inner product dapat membaca koordinat dengan bersih ketika arah-arahnya ortonormal. Pelajaran ini menjelaskan cara membangun arah tersebut dari daftar yang bebas linear. Buku resmi Mathematics for Machine Learning memetakan gagasan ini ke Bagian 3.5. Vektor yang dihitung, visual, implementasi NumPy, hubungan dengan AI, dan penilaian di sini adalah karya orisinal.

Setiap arah baru hanya menyimpan bagian yang belum dijelaskan

Misalkan a1,…,aka_1,\ldots,a_k adalah vektor di Rd\mathbb{R}^d. Vektor masukan tidak harus saling tegak lurus atau memiliki panjang satu. Gram–Schmidt membangun vektor satuan q1,…,qkq_1,\ldots,q_k pada span yang sama, selama setiap masukan baru menyumbangkan arah tak nol setelah arah sebelumnya dihapus.

Vektor pertama tidak memiliki apa pun untuk dikurangkan. Untuk vektor berikutnya, gunakan inner product dengan setiap arah satuan sebelumnya untuk mengukur seberapa besar vektor baru menunjuk ke arah itu. Karena setiap qjq_j memiliki panjang satu, ⟨qj,ai⟩qj\langle q_j,a_i\rangle q_j tepat merupakan proyeksi aia_i ke arah tersebut.

Kata residual memiliki peran penting. Residual bukan sekadar vektor perantara yang boleh dibuang setelah normalisasi. Normanya, ∥ri∥2\lVert r_i\rVert_2, adalah jarak dari aia_i ke span arah sebelumnya. Residual besar berarti masukan menyumbangkan komponen baru yang cukup besar relatif terhadap urutan yang dipilih. Residual kecil berarti masukan dekat dengan span sebelumnya. Residual nol sama sekali tidak dapat dinormalisasi.

Konstruksinya berurutan, jadi urutan merupakan bagian dari perhitungan. Jika masukan bebas linear, urutan yang berbeda tetap menggambarkan span yang sama dalam aritmetika eksak, tetapi arah, tanda, dan ukuran residual pada setiap langkah dapat berbeda. Hal ini penting ketika residual mendekati batas presisi atau lantai noise.

Perhitungan tiga vektor, satu proyeksi setiap kali

Gunakan tiga vektor di R3\mathbb{R}^3:

a1=[110],a2=[101],a3=[011].a_1=\begin{bmatrix}1\\1\\0\end{bmatrix}, \qquad a_2=\begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad a_3=\begin{bmatrix}0\\1\\1\end{bmatrix}.

Koordinat ini tidak memiliki satuan fisik; ketiganya adalah tiga komponen dari arah fitur mainan. Angkanya dibuat kecil agar proyeksi dan normalisasi mudah terlihat.

Visual di bawah mengubah urutan tersebut menjadi penelusuran yang dikendalikan pembaca. Setiap panel menampilkan masukan, total proyeksi yang dihapus, residual, dan arah satuan untuk satu tahap. Tabelnya bukan duplikat dekoratif: tabel adalah fallback numerik yang dirender server dan mempertahankan perbandingan lengkap bagi pengguna keyboard dan teknologi bantu.

Ikuti residual melalui Gram–Schmidt

Gunakan tombol atau menu pilihan. Tahap yang dipilih akan diumumkan, dan tabel di bawah tetap tersedia tanpa interaksi.

1 dari 3: mulai dari a₁
Ikuti residual melalui Gram–Schmidtmulai dari a₁. Empat panel menampilkan masukan aᵢ, proyeksi yang dihapus, residual rᵢ, dan arah satuan qᵢ; setiap vektor juga ditulis secara eksak dalam tabel di bawah.Masukan aᵢx₁x₂x₃(1, 1, 0)Proyeksi yang dihapusx₁x₂x₃(0, 0, 0)Residual rᵢx₁x₂x₃(1, 1, 0)Arah satuan qᵢx₁x₂x₃(0.71, 0.71, 0)
Vektor masukan
(1, 1, 0)
Proyeksi yang dihapus
(0, 0, 0)
Residual sebelum normalisasi
(1, 1, 0)
Arah ternormalisasi
(0.71, 0.71, 0)
Semua tahap Gram–Schmidt dan vektor tiga dimensinya.
TahapMasukan aᵢProyeksi yang dihapusResidual rᵢArah satuan qᵢ
mulai dari a₁(1, 1, 0)(0, 0, 0)(1, 1, 0)(0.71, 0.71, 0)
hapus q₁ dari a₂(1, 0, 1)(0.5, 0.5, 0)(0.5, −0.5, 1)(0.41, −0.41, 0.82)
hapus q₁ dan q₂ dari a₃(0, 1, 1)(0.67, 0.33, 0.33)(−0.67, 0.67, 0.67)(−0.58, 0.58, 0.58)

Diagram membulatkan nilai hingga dua angka desimal; perhitungan dalam pelajaran mempertahankan akar dan pecahan eksak.

Pilih tahap untuk melihat masukan, bagian yang sudah dijelaskan oleh arah sebelumnya, residual yang tersisa, dan arah ternormalisasinya. Tabel adalah alternatif numerik lengkap untuk diagram.

NumPy mencerminkan derivasi dan memperlihatkan pemeriksaannya

Implementasi dapat menyimpan arah sebagai baris. Untuk setiap masukan, implementasi memulai dari salinan vektor asli, mengurangi satu proyeksi setiap kali, mengukur norm residual, dan hanya menormalisasi ketika norm tersebut melewati toleransi. numpy.linalg.norm menyediakan panjang Euclidean yang dipakai di sini. Bentuk satu-per-satu ini sering disebut modified Gram–Schmidt; dalam aritmetika eksak, pengurangannya sama dengan jumlah yang ditampilkan, sementara urutan pembaruan membuat residual saat ini terlihat jelas.

import numpy as np


def gram_schmidt(vectors, rtol=1e-12):
    directions = []
    residual_norms = []

    for index, vector in enumerate(vectors, start=1):
        original = np.asarray(vector, dtype=float)
        if original.ndim != 1:
            raise ValueError(f"vector {index} must be one-dimensional")

        residual = original.copy()
        for q in directions:
            coefficient = q @ residual
            residual -= coefficient * q

        residual_norm = np.linalg.norm(residual)
        residual_norms.append(residual_norm)
        scale = max(1.0, np.linalg.norm(original))
        if residual_norm <= rtol * scale:
            raise ValueError(
                f"vector {index} is dependent at rtol={rtol:g}"
            )

        directions.append(residual / residual_norm)

    return np.array(directions), np.array(residual_norms)


A = np.array([
    [1.0, 1.0, 0.0],
    [1.0, 0.0, 1.0],
    [0.0, 1.0, 1.0],
])

Q, residual_norms = gram_schmidt(A)
np.set_printoptions(precision=8, suppress=True)
print(Q)
print(residual_norms)
print(Q @ Q.T)
print(np.allclose(Q @ Q.T, np.eye(3), rtol=1e-12, atol=1e-12))

Keluaran yang telah diverifikasi adalah:

[[ 0.70710678  0.70710678  0.        ]
 [ 0.40824829 -0.40824829  0.81649658]
 [-0.57735027  0.57735027  0.57735027]]
[1.41421356 1.22474487 1.15470054]
[[ 1.  0.  0.]
 [ 0.  1.  0.]
 [ 0.  0.  1.]]
True

Karena arah disimpan sebagai baris, Q @ Q.T adalah matriks Gram keluaran. Matriks identitas mengonfirmasi panjang satu pada diagonal dan inner product silang nol di tempat lain. Jika implementasi menyimpan arah sebagai kolom, pemeriksaan yang sesuai adalah Q.T @ Q; konvensi bentuk harus ditentukan sebelum menulis perkalian.

np.allclose membandingkan nilai floating point dengan toleransi relatif dan absolut yang eksplisit, bukan menuntut kesamaan desimal yang persis. Ini adalah pengujian hasil perhitungan, bukan izin untuk menganggap setiap angka kecil sebagai nol. Toleransi harus sesuai dengan skala dan noise data fitur.

Ukuran residual adalah peringatan tumpang tindih, bukan vonis

Pertimbangkan pasangan yang hampir duplikat:

a1=(1,1,0),a2=(1,1+10−10,0).a_1=(1,1,0), \qquad a_2=(1,1+10^{-10},0).

Setelah komponen q1q_1 dihapus, residual kedua kira-kira

r2≈(−5×10−11, 5×10−11, 0),∥r2∥2≈7.07×10−11.r_2\approx(-5\times10^{-11},\,5\times10^{-11},\,0), \qquad \lVert r_2\rVert_2\approx7.07\times10^{-11}.

Dengan rtol=1e-12, residual melewati ambang untuk skala masukan ini dan kode menerima arah baru yang sangat kecil. Dengan rtol=1e-9, residual ditandai sebagai dependen. Tidak ada pengaturan yang menemukan kebenaran universal tentang fitur: pengaturan pertama meminta pemisahan yang lebih halus, sedangkan yang kedua menganggap pemisahan itu berada di bawah resolusi yang berguna bagi aplikasi.

Vektor yang benar-benar dependen lebih jelas. Jika a2=2a1a_2=2a_1, pengurangan proyeksinya meninggalkan r2=0r_2=0. Pembagian dengan ∥r2∥2\lVert r_2\rVert_2 berarti pembagian dengan nol, jadi implementasi yang kuat harus berhenti, membuang vektor tersebut, atau melaporkan redundansi. Implementasi tidak boleh menghasilkan nan lalu melanjutkan seolah-olah arah baru ada.

Pemeriksaan yang memperhitungkan skala dalam kode menggunakan ∥ri∥2≤rtol max⁡(1,∥ai∥2)\lVert r_i\rVert_2\le\texttt{rtol}\,\max(1,\lVert a_i\rVert_2) sebagai aturan keputusan. Dalam pipeline fitur nyata, pilih ambang dari noise pengukuran yang diharapkan, penskalaan fitur, dan keputusan downstream. Catat pilihan itu bersama diagnosis. Toleransi tanpa skala sulit ditafsirkan.

Urutan mengubah basis dan cerita stabilitasnya

Gram–Schmidt adalah konstruksi yang mempertahankan span, bukan operasi pengurutan yang bebas urutan. Menata ulang masukan bebas linear mengubah arah yang dibangun pertama, sehingga proyeksi dan residual berikutnya berubah. Daftar akhir tetap merentang subruang yang sama dalam aritmetika eksak, tetapi vektor basis dapat berputar di dalam subruang itu atau berubah tanda. Dekat ketergantungan, perbedaannya lebih penting: menaruh vektor yang hampir redundan terlalu awal dapat membuat residual berikutnya terlihat kecil, sementara memulai dengan arah yang kondisinya lebih baik dapat menyisakan lebih banyak ruang numerik.

Untuk perhitungan kecil dalam pengajaran, loop eksplisit berguna karena setiap proyeksi terlihat. Untuk matriks yang lebih besar atau ill-conditioned, gunakan faktorisasi QR yang telah diuji seperti numpy.linalg.qr, lalu periksa rank atau diagnosis rekonstruksinya. Yang berubah adalah alat numeriknya, bukan tujuan geometrinya.

Arah fitur bukan variabel yang independen secara statistik

Misalkan baris sebuah matriks adalah arah fitur: mungkin pola pengukuran yang dirancang manual, probe yang dipelajari, atau arah untuk memeriksa representasi model. Gram–Schmidt dapat membuat kerangka koordinat ortogonal untuk span-nya. Norm residual memberi tahu praktisi seberapa banyak arah linear baru yang ditambahkan setiap baris relatif terhadap baris yang telah diproses. Ini dapat membantu meninjau fitur atau menemukan duplikat dekat sebelum analisis linear downstream.

Namun, hal itu tidak membuktikan bahwa variabel acak asli independen secara statistik dan tidak menjanjikan prediksi yang lebih baik. Ortogonalitas membandingkan vektor tetap di bawah inner product yang dipilih. Independensi statistik adalah pernyataan tentang distribusi probabilitas gabungan. Bahkan kovarians nol hanya menyingkirkan satu hubungan linear tertentu.

Sebagai contoh tandingan konkret, ambil sampel terpusat

x=(−2,−1,0,1,2),y=(2,−1,−2,−1,2)=x2−2.x=(-2,-1,0,1,2), \qquad y=(2,-1,-2,-1,2)=x^2-2.

Dot product-nya adalah

xTy=(−2)(2)+(−1)(−1)+0(−2)+1(−1)+2(2)=0.x^{\mathsf T}y=(-2)(2)+(-1)(-1)+0(-2)+1(-1)+2(2)=0.

Kolom sampel tidak memiliki tumpang tindih linear, tetapi yy sepenuhnya ditentukan oleh xx melalui aturan nonlinear. Dalam laporan AI, katakan bahwa arah tersebut ortogonal atau bahwa kovarians sampel terpusat bernilai nol berdasarkan konvensi yang dinyatakan. Gunakan “independen” hanya jika ada argumen probabilistik terpisah yang mendukungnya.

Karena itu Gram–Schmidt menjadi jembatan praktis dari gagasan koordinat ortonormal pada pelajaran sebelumnya menuju diagnosis fitur: hapus bagian yang telah dijelaskan, ukur sisanya, normalkan hanya ketika residual bermakna, dan laporkan urutan serta toleransi yang menghasilkan keputusan. Pelajaran berikutnya akan memakai gagasan residual yang sama untuk menjelaskan arah yang ortogonal terhadap seluruh subruang.

Periksa pemahaman Anda

Pertanyaan 1

Untuk vektor masukan a₁,…,aᵢ dan arah satuan yang sudah ada q₁,…,qᵢ₋₁, tuliskan residual rᵢ dan jelaskan mengapa normanya informatif.

Tampilkan solusi langkah demi langkah

Mulailah dengan mengurangi proyeksi pada setiap arah sebelumnya:

ri=ai−∑j=1i−1⟨qj,ai⟩qj.r_i=a_i-\sum_{j=1}^{i-1}\langle q_j,a_i\rangle q_j.

Koefisien ⟨qj,ai⟩\langle q_j,a_i\rangle mengukur komponen sepanjang qjq_j karena qjq_j memiliki panjang satu. Setelah semua komponen itu dihapus, ∥ri∥2\lVert r_i\rVert_2 adalah jarak aia_i ke span arah sebelumnya. Nilai nol berarti tidak ada arah baru yang tersisa; nilai kecil berarti masukan hampir berada di span itu pada skala numerik yang dipilih.

Pertanyaan 2

Jalankan dua langkah pertama Gram–Schmidt untuk a₁=(1, 1) dan a₂=(1, 0). Berikan q₁, proyeksi yang dihapus dari a₂, r₂, dan q₂.

Tampilkan solusi langkah demi langkah

Norm pertama adalah

∥a1∥2=12+12=2,q1=[1/21/2].\lVert a_1\rVert_2=\sqrt{1^2+1^2}=\sqrt2, \qquad q_1=\begin{bmatrix}1/\sqrt2\\1/\sqrt2\end{bmatrix}.

Koefisien proyeksi untuk a2a_2 adalah

q1Ta2=12.q_1^{\mathsf T}a_2=\frac1{\sqrt2}.

Jadi vektor proyeksinya adalah (1/2,1/2)(1/2,1/2) dan

r2=[10]−[1/21/2]=[1/2−1/2].r_2=\begin{bmatrix}1\\0\end{bmatrix} -\begin{bmatrix}1/2\\1/2\end{bmatrix} =\begin{bmatrix}1/2\\-1/2\end{bmatrix}.

Normanya 1/21/\sqrt2, sehingga normalisasi menghasilkan

q2=[1/2−1/2].q_2=\begin{bmatrix}1/\sqrt2\\-1/\sqrt2\end{bmatrix}.

Inner product silang adalah q1Tq2=1/2−1/2=0q_1^{\mathsf T}q_2=1/2-1/2=0, yang memeriksa arah baru tersebut.

Pertanyaan 3

Dalam contoh tiga vektor pada pelajaran ini, mengapa total proyeksi yang dihapus dari a₃ sama dengan (2/3, 1/3, 1/3)? Tunjukkan kedua vektor proyeksi sebelum dijumlahkan.

Tampilkan solusi langkah demi langkah

Kedua koefisiennya adalah

q1Ta3=12,q2Ta3=16.q_1^{\mathsf T}a_3=\frac1{\sqrt2}, \qquad q_2^{\mathsf T}a_3=\frac1{\sqrt6}.

Kalikan setiap koefisien dengan arahnya:

12q1=[1/21/20],16q2=[1/6−1/61/3].\frac1{\sqrt2}q_1 =\begin{bmatrix}1/2\\1/2\\0\end{bmatrix}, \qquad \frac1{\sqrt6}q_2 =\begin{bmatrix}1/6\\-1/6\\1/3\end{bmatrix}.

Menjumlahkan koordinat yang bersesuaian menghasilkan

[1/2+1/61/2−1/60+1/3]=[2/31/31/3].\begin{bmatrix}1/2+1/6\\1/2-1/6\\0+1/3\end{bmatrix} =\begin{bmatrix}2/3\\1/3\\1/3\end{bmatrix}.

Vektor itu adalah bagian dari a3a_3 yang sudah dijelaskan oleh dua arah pertama; menguranginya meninggalkan residual yang dipakai untuk membangun q3q_3.

Pertanyaan 4

Apa yang harus dilakukan implementasi Gram–Schmidt ketika masukan baru tepat merupakan kelipatan masukan sebelumnya, misalnya a₂=2a₁?

Tampilkan solusi langkah demi langkah

Jika a2=2a1a_2=2a_1, arah pertama q1q_1 merentang a2a_2. Proyeksinya adalah

(q1Ta2)q1=2∥a1∥2q1=2a1=a2,(q_1^{\mathsf T}a_2)q_1=2\lVert a_1\rVert_2q_1=2a_1=a_2,

sehingga residualnya r2=0r_2=0. Normanya nol dan ekspresi r2/∥r2∥2r_2/\lVert r_2\rVert_2 tidak terdefinisi. Implementasi harus melaporkan ketergantungan, membuang duplikat, atau menerapkan kebijakan yang didokumentasikan secara eksplisit; jangan normalkan vektor nol atau menyimpan nilai nan secara diam-diam.

Pertanyaan 5

Mengapa dua urutan masukan yang berbeda dapat menghasilkan vektor-q yang berbeda walaupun span-nya sama? Apa yang tetap tidak berubah dalam aritmetika eksak?

Tampilkan solusi langkah demi langkah

Setiap arah baru dibuat ortogonal terhadap arah yang datang sebelumnya. Mengubah urutan mengubah span sebelumnya pada setiap langkah, sehingga proyeksi, residual, dan arah ternormalisasi dapat berubah. Sebuah arah juga dapat membalik tanda tanpa mengubah subruang satu dimensinya.

Untuk masukan yang bebas linear, aritmetika eksak tetap mempertahankan span seluruh daftar: setiap vektor asli dapat direkonstruksi dari arah keluaran dan arah keluaran berada dalam span asli. Vektor basis individual serta ukuran residual antara bergantung pada urutan, sehingga urutan merupakan bagian dari diagnosis numerik.

Pertanyaan 6

Kode menyimpan vektor-q sebagai baris. Pemeriksaan matriks apa yang memverifikasi ortonormalitas, dan kesalahan baris-versus-kolom apa yang mengubah pemeriksaan itu?

Tampilkan solusi langkah demi langkah

Dengan penyimpanan sebagai baris, entri (i,j)(i,j) dari QQTQ Q^{\mathsf T} adalah inner product baris ii dan baris jj. Jadi pemeriksaan yang benar adalah

QQT≈I.Q Q^{\mathsf T}\approx I.

Di NumPy, gunakan np.allclose(Q @ Q.T, np.eye(Q.shape[0]), atol=...) dengan toleransi yang dinyatakan. Jika arah disimpan sebagai kolom, matriks Gram yang sesuai adalah QTQQ^{\mathsf T}Q. Memakai pemeriksaan kolom pada data yang disimpan sebagai baris dapat memeriksa hubungan berpasangan yang salah atau menghasilkan bentuk yang tidak sesuai dengan identitas yang diinginkan.

Pertanyaan 7

Sebuah arah fitur baru memiliki norm residual 0.00000000007 setelah arah sebelumnya dihapus. Apakah itu otomatis berarti fitur tersebut tidak berguna?

Tampilkan solusi langkah demi langkah

Tidak. Nilai tersebut mengatakan bahwa arah baru menyumbangkan sangat sedikit relatif terhadap span sebelumnya pada skala masukan dan urutan saat ini. Apakah sumbangan itu dapat diabaikan bergantung pada noise pengukuran, satuan fitur, sensitivitas downstream, dan toleransi yang dipilih.

Sebagai contoh, rtol=1e-12 mungkin menerima residual dekat 7×10−117\times10^{-11} untuk vektor berskala satu, sedangkan rtol=1e-9 mungkin mengklasifikasikannya sebagai dependen. Tafsiran yang benar adalah keputusan numerik yang didokumentasikan—“di bawah resolusi ini” atau “dipertahankan pada resolusi ini”—bukan klaim universal tentang nilai prediktif.

Pertanyaan 8

Mengapa dot product terpusat nol antara sampel fitur gagal membuktikan independensi statistik? Gunakan x=(−2,−1,0,1,2) dan y=(2,−1,−2,−1,2).

Tampilkan solusi langkah demi langkah

Pertama hitung tumpang tindih linear:

xTy=−4+1+0−1+4=0.x^{\mathsf T}y=-4+1+0-1+4=0.

Karena kedua vektor sampel sudah terpusat, ini juga menghasilkan kovarians empiris nol dengan konvensi bobot sama yang biasa. Namun relasi y=x2−2y=x^2-2 menentukan setiap nilai yy dari xx. Pasangan itu memiliki ketergantungan nonlinear meskipun inner product linearnya nol.

Ortogonalitas dan kovarians nol menggambarkan satu perbandingan linear. Independensi memerlukan pernyataan tentang distribusi gabungan lengkap, sehingga membutuhkan bukti terpisah.

Sumber

  1. Mathematics for Machine Learning book PDF, Section 3.5
  2. NumPy documentation: numpy.linalg.norm
  3. NumPy documentation: numpy.allclose
  4. NumPy documentation: numpy.linalg.qr