METODE PENCARION BLIND SEARCH

Blind Search.

Blind seach adalah pencarian yang tidak mempedulikan hal lain setelah sesuatu yang di carinya ditemukan, blind search hanya mengenal tiga bagian yaitu masalah --> pencarian --> solusi.

model pencarian blind search yang tidak memiliki informasi awal, model pencarian ini memiliki 3 ciri – ciri utama yaitu:
1. Membangkitkan simpul berdasarkan urutan.
2. Kalau ada solusi maka solusi akan ditemukan.
3. Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Contoh : pencarian gelas merah dalam box yang berisi gelas kuning, gelas hijau, gelas biru, dan gelas merah. ketika menemukan gelas biru akan tetap mencari, hingga saat menemukan gelas merah makanya pencarian akan berhenti.

SPEECH RECOGNITION

Pengertian Speech Recognition

Pengenalan suara (voice recognition) dibagi menjadi dua jenis, yaitu speech recognition dan speaker recognition. Speech recognition adalah proses identifikasi yang dilakukan komputer untuk mengenali kata yang diucapkan oleh seseorang tanpa mempedulikan identitas orang terkait dengan melakukan konversi sebuah sinyal akustik, yang ditangkap oleh audio device (perangkat input suara). Pola kerja Pengenalan Ujaran (speech recognition) adalah mencocokkan sinyal akustik yang diterima dengan data yang tersimpan dalam template ataupun database. Proses pencocokan memiliki dua model utama yaitu Model Akustik yang terdiri dari fonem yang memiliki nilai tertentu yang diambil dari sinyal akustik dan Model Bahasa berupa metode yang mengestimasikan satu kata diikuti oleh serangkaian kata lainnya.

Speaker recognition yang merupakan pengenalan identitas yang diklaim oleh seseorang dari suaranya (ciri khusus dapat berupa intonasi suara, tingkat kedalaman suara, dan sebagainya). Implementasi speech recognition misalnya perintah suara untuk menjalankan aplikasi komputer.

Speech Recognition juga merupakan sistem yang digunakan untuk mengenali perintah kata dari suara manusia dan kemudian diterjemahkan menjadi suatu data yang dimengerti oleh komputer. Pada saat ini, sistem ini digunakan untuk menggantikan peranan input dari keyboard dan mouse. Keuntungan dari sistem ini adalah pada kecepatan dan kemudahan dalam penggunaannya. Kata – kata yang ditangkap dan dikenali bisa jadi sebagai hasil akhir, untuk sebuah aplikasi seperti command & control, penginputan data, dan persiapan dokumen. Parameter yang dibandingkan ialah tingkat penekanan suara yang kemudian akan dicocokkan dengan template database yang tersedia. Sedangkan sistem pengenalan suara berdasarkan orang yang berbicara dinamakan speaker recognition. Pada makalah ini hanya akan dibahas mengenai speech recognition karena kompleksitas algoritma yang diimplementasikan lebih sederhana daripada speaker recognition. Algoritma yang akan diimplementasikan pada bahasan mengenai proses speech recognition ini adalah algoritma FFT (Fast Fourier Transform), yaitu algoritma yang cukup efisien dalam pemrosesan sinyal digital (dalam hal ini suara) dalam bentuk diskrit. Algoritma ini mengimplementasikan algoritma Divide and Conquer untuk pemrosesannya. Konsep utama algoritma ini adalah mengubah sinyal suara yang berbasis waktu menjadi berbasis frekuensi dengan membagi masalah menjadi beberapa upa masalah yang lebih kecil. Kemudian, setiap upa masalah diselesaikan dengan cara melakukan pencocokan pola digital suara.

Sejarah Speech Recognition

Teknologi Speech Recognition yang dikembangkan sejak sepuluh tahun lalu menghadapi dua pilihan, yakni menangkap percakapan terputus (kata per kata) atau percakapan tersambung (per kalimat). Komputer sebenarnya lebih mudah memahami suara untuk kata per kata, yang di antara masing-masing kata terdapat jeda, namun kebanyakan orang lebih menyukai jika teknologi ini mampu menangkap sebuah percakapan normal. Biometrik, termasuk di dalamnya speech recognition, secara umum digunakan untuk identifikasi dan verifikasi. Identifikasi ialah mengenali identitas subyek, dilakukan perbandingan kecocokan antara data biometric subyek dalam database berisi record karakter subyek. Sedangkan verifikasi adalah menentukan apakah subyek sesuai dengan apa yang dikatakan terhadap dirinya. Biometrik merupakan suatu metoda untuk mengenali manusia berdasarkan pada satu atau lebih ciri-ciri fisik atau tingkah laku yang unik. Biometric Recognition atau biasa disebut dengan Sistem pengenalan biometric mengacu pada identifikasi secara otomatis terhadap manusia berdasarkan psikological atau karakteristik tingkah laku manusia. Ada beberapa jenis teknologi biometric antara lain suara (speech recognition).

Program Speech Recognition pada generasi awal berusaha untuk menerapkan sebuah aturan gramatikal dan sintaktikal dari sebuah percakapan. Jika kata-kata yang diucapkan masuk ke dalam aturan yang baku, program dapat menentukan kata-kata tersebut. Aksen, dialek, dan gaya berbahasa seseorang sangat mempengaruhi bagaimana sebuah kata atau frase diucapkan. Sistem berbasis aturan ini dianggap tidak berhasil, karena tidak mampu menangani variasi berbahasa. Hal ini juga menjelaskan mengapa program Speech Recognition generasi awal tidak dapat menangani percakapan bersambung, karena Anda harus berbicara kata perkata secara terpisah. Sebagai jalan keluar dari permasalahan ini, program Speech Recognition mutakhir memakai sistem permodelan statistika yang lengkap dan rumit. Sistem ini menggunakan fungsi probabilitas (kemungkinan) dan matematika untuk memutuskan hasil yang paling mendekati. Dua model yang paling banyak digunakan saat ini adalah Hidden Markov Model dan jaringan syaraf (neural networks). Kedua metode melibatkan fungsi matematika yang kompleks, mengambil informasi yang diketahui, memprosesnya di dalam sistem untuk menemukan informasi yang tersembunyi.

Metode Hidden Markov Model mulai diperkenalkan dan dipelajari pada akhir tahun 1960, metode yang berupa model statistik dari rantai Markov ini semakin banyak dipakai pada tahun-tahun terakhir terutama dalam bidang speech recognition, seperti dijelaskan oleh Lawrence R. Rabiner dalam laporannya yang berjudul “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”. Proses dalam dunia nyata secara umum menghasilkan observable output yang dapat dikarakterisasikan sebagai signal. Signal bisa bersifat diskrit (karakter dalam alfabet) maupun kontinu (pengukuran temperatur, alunan musik). Signal bisa bersifat stabil (nilai statistiknya tidak berubah terhadap waktu) maupun nonstabil (nilai signal berubah-ubah terhadap waktu). Dengan melakukan pemodelan terhadap signal secara benar, dapat dilakukan simulasi terhadap sumber dan pelatihan sebanyak mungkin melalui proses simulasi tersebut. Sehingga model dapat diterapkan dalam sistem prediksi, sistem pengenalan, maupun sistem identifikasi. Secara garis besar model signal dapat dikategorikan menjadi 2 golongan yaitu : model deterministik dan model statistikal. Model deterministik menggunakan nilai-nilai properti dari sebuah signal seperti : amplitudo, frekuensi, fase dari gelombang sinus. Sedangkan model statistikal menggunakan nilai-nilai statistik dari sebuah signal seperti: proses Gaussian, proses Poisson, proses Markov, dan proses Hidden Markov.

Suatu model HMM secara umum memiliki unsur-unsur sebagai berikut:

• N, yaitu jumlah state dalam model. Secara umum state saling terhubung satu dengan yang lain, dan suatu state bisa mencapai semua state yang lain dan sebaliknya (disebut model ergodic). Namun hal tersebut tidak mutlak, terdapat kondisi lain dimana suatu state hanya bisa berputar ke diri sendiri dan berpindah ke satu state berikutnya, hal ini bergantung pada implementasi dari model.

• M, yaitu jumlah observation symbol secara unik pada tiap statenya, misalnya: karakter dalam alfabet, dimana state adalah huruf dalam kata.

• State Transition Probability { } -> ij A a

• Observation Symbol Probability pada state j, { } () -> j Bb k

• Initial State Distribution -> i p p

Dengan memberikan nilai pada N, M, A, B, dan p , HMM dapat digunakan sebagai generator untuk menghasilkan urutan observasi. dimana tiap observasi t o adalah salah satu simbol dari V, dan T adalah jumlah observasi dalam suatu sequence.

Skema Utama dan Algoritma Speech Recognition

Untuk mengubah percakapan menjadi teks on-screen atau perintah tertentu, komputer melakukan beberapa langkah yang kompleks. Ketika berbicara, Anda mengeluarkan getaran di udara. Kemudian, analog-to-digital converter (ADC) yang ada di soundcard menerjemahkan gelombang analog ini menjadi data digital yang dapat dimengerti oleh komputer. Untuk melakukan hal tersebut, sistem Speech Recognition melakukan sampling atau digitizing suara dengan cara mengambil ukuran yang paling pas dari gelombang. Sistem menyaring suara yang telah didigitalkan tersebut dan membuang gangguan (noise), dan kadang-kadang memisahkannya ke dalam pita frekuensi yang berbeda. Frekuensi adalah panjang gelombang suara, yang terdengar oleh telinga manusia sebagai tinggi nada (pitch) yang berbeda.

Sistem ini juga menormalkan suara, atau mengaturnya ke dalam tingkat volume yang tetap, terkadang juga mendatarkan suara. Manusia tidak berbicara dalam kecepatan yang sama sehingga suara harus diatur dengan kecepatan yang sama dengan sampel-sampel template suara yang tersimpan dalam komputer. Langkah selanjutnya adalah memecah sinyal menjadi bagian-bagian kecil, dengan durasi seperseratus detik, atau bahkan seperseribu pada kasus bunyi-bunyi konsonan atau mati. Konsonan memberhentikan produksi suara dengan menghalangi aliran gelombang pada bidang vokal, seperti “p” atau “t”.

Program di komputer kemudian mencocokkan bagian-bagian kecil ini dengan fonem yang dikenal dalam bahasa tertentu. Fonem adalah elemen terkecil dalam sebuah bahasa, merepresentasikan suara yang kita hasilkan, dan merangkainya ke dalam bentuk ujaran yang memiliki makna. Tahap berikutnya kelihatan sederhana, tapi pada dasarnya merupakan proses yang paling susah diselesaikan, sekaligus merupakan inti dari sebagian besar penelitian di bidang Speech Recognition. Komputer memeriksa fonem-fonem dalam konteks (hubungan) dengan fonem-fonem lain yang menyertainya. Komputer menjalankan alur (plot) melalui sebuah model statistika yang kompleks, dan membandingkannya dengan koleksi kata, frase, dan kalimat yang telah dikenal. Program Speech Recognition selanjutnya menentukan apa yang mungkin dikatakan oleh pengguna, dan juga mengetikkannya sebagai teks atau mengeluarkannya sebagai perintah pada komputer.

Terdapat 4 langkah utama dalam sistem pengenalan suara:

• Penerimaan data input

• Ekstraksi, yaitu penyimpanan data masukan sekaligus pembuatan database untuk template.

• Pembandingan / pencocokan, yaitu tahap pencocokan data baru dengan data suara (pencocokan tata bahasa) pada template atau database.

• Validasi identitas pengguna.

Gambar 1. Skema Speech Recognition

Secara umum, speech recognizer memproses sinyal suara yang masuk dan menyimpannya dalam bentuk digital. Hasit proses digitalisasi tersebut kemudian dikonversi dalam bentuk spektrum suara yang akan dianalisa dengan membandingkannya dengan template suara pada database sistem.

Gambar 2. Spektrum Suara

Sebelumnya, data suara masukan dipilah-pilah dan diproses satu per satu berdasarkan urutannya. Pemilahan ini dilakukan agar proses analisis dapat dilakukan secara paralel. Proses yang pertama kali dilakukan ialah memproses gelombang kontinu spektrum suara ke dalam bentuk diskrit. Langkah berikutnya ialah proses kalkulasi yang dibagi menjadi dua bagian :

• Transformasi gelombang diskrit menjadi array data.

• Untuk masing-masing elemen pada aiTay data, hitung "ketinggian" gelombang (frekuensi).

Objek permasaiahan yang akan dibagi adalah masukan berukuran n, berupa data diskrit gelombang suara.

Ketika mengkonversi gelombang suara ke dalam bentuk diskrit, gelombang diperlebar dengan cara memperinci berdasarkan waktu. Hal ini dilakukan agar proses algontma seianjutnya (pencocokan) lebih mudah diiakukan. Namun, efek buruknya ialah array of array data yang terbentuk akan lebih banyak.

Gambar 3. Contoh Hasit Konversi Sinyal Diskrit

Dari tiap elemen array data tersebut, dikonversi ke dalam bentuk bilangan biner. Data biner tersebut yang nantinya akan dibandingkan dengan template data suara.

Proses divide and conquer :

• Pilih sebuah angkaN, dimana N merupakan bilangan bulat kelipatan 2.Bilangan ini berfungsi untuk menghitung jumlah elemen transformasi FFT.

• Bagi dua data diskrit secara (dengan menerapkan algoritma divide and conquer) menjadi data diskrit yang lebih kecii berukuran N = N,.N2.

• Objek data dimasukkan ke dalam table (sebagai elemen tabel).

• Untuk setiap eiemen data, dicocokkan dengan data pada template (pada data template juga dilakukan pemrosesan digitaiisasi menjadi data diskrit, dengan cara yang sama dengan proses digitaiisasi data masukan bam yang ingin dicocokkan).

• Setiap upa masalah disatukan kembali dan dianalisis secara keseluruhan, kecocokan dari segi tata bahasa dan apakah data yang diucapkan sesuai dengan kata yang tersedia pada template data.

• Verifikasi data. Jika sesuai, proses iebih lanjut, sesuai dengan aplikasi yang mengimplementasikan algoritma ini.

Implementasi teknologi Speech Recognition

Hardware yang dibutuhkan dalam implementasi Speech Recognition :

• Sound card : Merupakan perangkat yang ditambahkan dalam suatu Komputer yang fungsinya sebagai perangkat input dan output suara untuk mengubah sinyal elektrik, menjadi analog maupun menjadi digital.

• Microphone : Perangkat input suara yang berfungsi untuk mengubah suara yang melewati udara, air dari benda orang menjadi sinyal elektrik.

• Komputer atau Komputer Server : Dalam proses suara digital menterjemahkan gelombang suara menjadi suatu simbol biasanya menjadi suatu nomor biner yang dapat diproses lagi kemudian diidentifikasikan dan dicocokan dengan database yang berisi berkas suara agar dapat dikenali.

Contoh Implementasi teknologi Speech Recognition :

Contoh yang paling sederhana pemanfaatan teknologi Speech Recognition adalah voice dial yang sempat menjadi fitur andalan ponsel-ponsel high-end akhir dekade yang lalu. Sedangkan pengaplikasian mutakhir teknologi ini dapat dijumpai pada layanan call center, kemudian secara otomatis komputer akan memberikan solusinya. Penerapan Speech Recognition juga dapat ditemukan pada beberapa aplikasi komputer yang memungkinkan Anda mengetik dokumen tanpa harus memencet tombol-tombol keyboard. Cukup dengan mendiktekan kalimat-kalimat, kemudian secara otomatis komputer akan mengetikkannya untuk Anda. Banyak software yang dirancang untuk mengetikkan apa yang Anda katakan melalui microphone, seperti iListen untuk komputer Mac, dan software ViaVoice keluaran IBM.

Kesimpulan

Speech recognition merupakan salah satu jenis bimetrik recognition, yaitu proses computer mengenali suara lalu di convert menjadi digital. Pengenalan pola suara adalah salah satu aplikasi yang berkembang saat ini. System ini mengizinkan kita untuk berkomunikasi antara manusia dengan memasukkan data ke computer. Salah satu fungsinya ialah untuk mengontrol industry manufaktur, mengontrol mesin dengan berbicara pada mesin itu.

Algoritma yang di implementasikan untuk masalah pengenalan suara ini adalah algoritma devide and conquer. Proses awalnya ialah menkonversi data spectrum suara ke dalam bentuk digital dan mengubah dalam bentuk diskrit. Dari bentuk diskrit itulah yang kemudian mengaplikasikan algoritma divide and conquer untuk mengoptimalkan waktu pencocokan speech recognition.