tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
התנגשות במרחב הקטן הזה, שאמורה להתרחש בתוך צעדים, תזוהה מיד, מכיוון שההפרש באותו זמן יהיה 0 מודולו p, כך ש-p יחלק את המחלק המשותף המקסימלי .
יש גם סיכוי לכך שההתנגשות תתרחש בו זמנית מודולו כל גורם (חזקת-)ראשוני של n, ואז המחלק המשותף המקסימלי יהיה n, והאלגוריתם נכשל.
גרסה בסיסית של אלגוריתם rho עם הפונקציה: .
אם אזי הוא גורם של אחרת,
אם , האלגוריתם מסתיים בכישלון.
הערה: הסיכויים ש- אינם גבוהים, אך אם בכל זאת האלגוריתם מסתיים כאשר ישנן מספר אפשרויות.
אחת היא לחזור על האלגוריתם עם ערכים התחלתיים שונים.
השנייה היא לחזור על האלגוריתם עם פולינום אחר, בעל מקדם חופשי גבוה מ-1 למשל אם .
בהנחה שהפונקציה מתנהגת כפונקציה אקראית, זמן הריצה המשוער של האלגוריתם הוא צעדים אריתמטיים (של כפל מודולרי) ועל כן הזמן המשוער למציאת גורם לא טריוויאלי של הוא .
הטבלה הבאה מציגה את הלולאה הראשית (שלב 2) באלגוריתם בפירוק המספר :
נמצא ש- הוא אחד הגורמים, למעשה הגורם הקטן ביותר של .
ריצ'רד ברנט פרסם ב-1980 גרסה משופרת של אלגוריתם rho המכונה אלגוריתם פירוק לגורמים מונטה קרלו משופר, המציע שיפור של כ-36 אחוז במקרה הממוצע, ביחס לאלגוריתם המקורי.
במקום להשתמש באלגוריתם מחזוריות של פלויד כפי שעושה האלגוריתם של פולרד, אלגוריתם ברנט משתמש בשיטה שונה הנקראת back-tracking (נסיגה) כדי לאתר את מחזוריות הרצף ולמנוע חזרה מיותרת.
קוד C של אלגוריתם מונטה קרלו של ברנט:
הקלט: הוא המספר המיועד לפירוק, מספר אקראי כלשהו הנמוך מ-, ו- הוא ערך התחלתי כלשהו בדרך כלל 2. הפונקציה אמורה להיות פונקציה אקראית כלשהי מודולו , כמו , המאקרו ABS מייצג ערך מוחלט והפונקציה gcd היא אלגוריתם אוקלידס.
אלגוריתם rho של פולרד מספק איזון הדדי בין זמן הריצה לבין סיכוי ההצלחה.
במקרה הקשה כאשר המספר הוא כפולה של שני גורמים ראשוניים שווים בגודלם בערך, זמן ריצה משוער של צעדים, יניב גורם ראשוני בסיכויים של חצי בהערכה גסה (אף על פי שזוהי הערכה היוריסטית בלבד).
שאלת יעילות האלגוריתם המדויקת היא בעיה פתוחה.
אלגוריתם rho מהיר למדי עבור מספרים עם גורמים ראשוניים קטנים.
למשל במחשב בינוני, יישום מעשי של האלגוריתם בפירוק מספר פרמה השישי (כעשרים ספרות עשרוניות) לוקח כמחצית שנייה.
לעומת זאת לפירוק מספר בגודל זהה, שהוא כפולה של שני מספרים ראשוניים גדולים (לא בהכרח שונים) השווים בגודלם בקירוב, נדרשות כעשר שניות לפחות.
ההישג המשמעותי ביותר של האלגוריתם היה של גרסת ברנט המשופרת, איתה הצליחו ג'ון פולרד וריצ'רד ברנט לפרק את מספר פרמה השמיני בזמן כולל של שעתיים על מחשב מרכזי מדגם UNIVAC.
במתמטיקה, אלגברת קווטרניונים היא אלגברה פשוטה שהממד שלה מעל המרכז (שהוא בהכרח שדה, נאמר F) הוא 4. סוג זה של אלגברה הוא הדוגמה מן הממד הקטן ביותר האפשרי לחוג פשוט או לחוג עם חילוק, שאינו שדה.
את אלגברת הקווטרניונים הראשונה גילה המילטון ב-1843, והיא נקראת על שמו, אלגברת הקווטרניונים של המילטון.
דוגמה אחת לאלגברת קווטרניונים היא אלגברת המטריצות .
זוהי אלגברת הקווטרניונים היחידה שיש בה מחלקי אפס, וכל אלגברת קווטרניונים אחרת היא חוג עם חילוק.
אם Q אלגברת קווטרניונים שמרכזה השדה F, ו- הרחבת שדות, אז המכפלה הטנזורית היא אלגברת קווטרניונים שמרכזה K.
בפרט, אם המכפלה היא אלגברת המטריצות מעל K, אז K נקרא שדה פיצול של האלגברה.
אלגברה פשוטה (מממד סופי) מעל שדה סגור אלגברית מוכרחה להיות אלגברת מטריצות, ולכן הסגור האלגברי של F מפצל כל אלגברת קווטרניונים מעליה.
כל איבר שאינו מרכזי באלגברת קווטרניונים Q יוצר תת-אלגברה מממד 2; אם Q חוג עם חילוק, תת-אלגברה זו היא בהכרח שדה.
בין תת-השדות יש לאלגברה גם תת-שדות ספרביליים מעל המרכז (זוהי מסקנה של משפט קטה (Koethe), שהוכחתו עבור קווטרניונים קלה במיוחד).
כל תת-שדה המכיל את המרכז הוא בהכרח תת-אלגברה מקסימלית.
בפרט, כל תת-שדה K הוא המרַכז של עצמו.
הצגה על ידי יוצרים ויחסים
אם תת-שדה ספרבילי, אז יש אוטומורפיזם לא טריוויאלי של K מעל F.
אם המאפיין של F שונה מ-2, יש ב- K איבר x המקיים , ואז ; אם המאפיין הוא 2, אז יש איבר המקיים , ואז .
לפי משפט סקולם-נתר, יש איבר שהצמדה בו משרה את , היינו לכל .
במאפיין שונה מ-2, , ובמאפיין 2 .
מכיוון ש- מתחלף עם K ועם y,
פירושו של דבר שבמאפיין שאינו 2 ; יוצרים ויחסים אלה מציגים אלגברת קווטרניונים לכל , ומסמנים את האלגברה בקיצור בסימון או
במאפיין 2, ; גם כאן זוהי אלגברת קווטרניונים לכל עם ; את האלגברה הזו מסמנים בסימון .
אלגול או β בפרסאוס הוא הכוכב השני בבהירותו בקבוצת הכוכבים פרסאוס ואחד המשתנים הלוקים הידועים ביותר.
למעשה זו מערכת של שלושה כוכבים, בה בכל יומיים, 20 שעות ו-49 דקות, הכוכב הבהיר ביותר מוסתר חלקית למשך כ-10 שעות על ידי כוכב עמום יותר המקיף אותו וכתוצאה מכך הבהירות הכוללת של המערכת יורדת בכ-30% כך שניתן להבחין בשינוי הבהירות גם בעין.
שמו של הכוכב נגזר מערבית - رأس الغول (ראס אל-ע'ול) שפירושו "ראש השד", שם שמרמז על כך שכבר הערבים הכירו בכך שזהו לא כוכב רגיל.
במיתולוגיה היוונית הכוכב ייצג את ראשה של מדוזה הגורגונה, המוחזק על ידי פרסאוס לאחר שהרג אותה וערף את ראשה.
ככל הנראה כבר בימי קדם היה ידוע שהבהירות של אלגול משתנה במחזוריות קבועה, אך התעוד הראשון בכתב שידוע כיום של תופעה זו נעשה רק בשנת 1667 על ידי האסטרונום האיטלקי ג'מיניאנו מונטאנארי.
בשנת 1783 הציג האסטרונום הבריטי ג'ון גודריק בפני החברה המלכותית תאוריה המסבירה את השינוי המחזורי בבהירות, ולפיה השינוי נגרם מליקוי מאורות על ידי גוף חשוך המקיף את הכוכב ומסתיר את אורו.
ב-1881 מצא האסטרונום אדוארד פיקרינג מאוניברסיטת הרווארד ראיות לכך שאלגול הוא אכן כוכב כפול לוקה, שאומתו בשנת 1889 על ידי מדידות ספקטרוסקופיות שנערכו על ידי הרמן קארל פוגל ושהראו אפקט דופלר מחזורי באור הנפלט מהכוכב המעיד על שינוי מחזורי במהירות הרדיאלית של הכוכב בשל היותו חלק ממערכת כפולה.
זהו גם הכוכב הראשון שזוהה ככוכב כפול ספקטרוסקופי.
ב-1912 התגלה הכוכב השלישי - אלגול C על ידי מדידות ספקטרוסקופיות שהראו על קיומו של כוכב נוסף.
חיזוק לכך נמצא בתנודות מחזוריות במיקומם של הזוג אלגול A ואלגול B שהתגלו בשנות ה-30 של המאה ה-20.
מערכת אלגול נמצאת במרחק של כ-93 שנות אור ובהירותה הנראית הכוללת היא בדרגה 2.12. במחזוריות של יומיים, 20 שעות ו-49 דקות, עקב מעבר אלגול B על פני אלגול A והסתרתו לצופה מכדור הארץ, המערכת נראית עמומה יותר ודרגת הבהירות שלה היא 3.4 למשך כ-10 שעות.
במחצית זמן המחזור בין שני ליקויים, עובר אלגול A על פני אלגול B, המערכת נראית בהירה יותר ודרגת בהירותה היא 2.2, אך השינוי הזה קטן מכדי שניתן יהיה להבחין בו בעין.
אלגול A הוא הכוכב המסיבי והבהיר מבין השלושה.
מסתו כ-3.6 מסות שמש ורדיוסו קצת פחות מ-3 רדיוסי שמש.
עוצמת ההארה שלו היא פי 100 מהשמש באור נראה וכמעט כפול מכך בתוספת התחום העל-סגול.
זהו כוכב הסדרה הראשית בצבע כחול עם טמפרטורת פני שטח של כ-12,500 קלווין.
גילו מוערך בכ-300 מיליוני שנים.
אלגול B הוא תת-ענק כתום עם מסה של כ-0.8 מסות שמש ורדיוס פי 3.5 מהשמש, המקיף את אלגול A במרחק קטן מאוד של 0.062 יחידות אסטרונומיות במסלול כמעט מעגלי לחלוטין ובזמן מחזור של 2.87 ימים.
מכיוון שמסתו של אלגול B קטנה בהרבה משל אלגול A היה צפוי שהוא יהיה בשלב התפתחות מוקדם יותר מאלגול A ולא בשלב הפיכה לענק.
עוצמת ההארה של אלגול B היא רק פי 3.4 מהשמש, כלומר כ-3.5% מעוצמת ההארה של אלגול A ומכיוון שרדיוסו גדול משל אלגול A נוצר מצב הליקוי כאשר הוא עובר על פני אלגול A.
למעשה מישור ההקפה של אלגול B סביב אלגול A נטוי בכ-7.7° ביחס לקו הראיה אל כדור הארץ כך שהוא לא מסתיר לחלוטין את אלגול A בזמן הליקוי.
אלגול C הוא כוכב הסדרה הראשית לבן עם מסה של כ-1.67 מסות שמש ורדיוס פי 1.7 מהשמש.
עוצמת ההארה שלו היא פי 4 מהשמש, כך שגם הוא עמום מאוד ביחס לאלגול A.
אלגול C מקיף את זוג הכוכבים אלגול A ואלגול B במסלול אליפטי למדי ובמרחק ממוצע של כ-2.7 יחידות אסטרונומיות.
זמן ההקפה הוא כ-681 ימים.
אלגוריתם Lemke-Howson, שפותח על ידי C.
Howson בשנת 1964 הוא האלגוריתם הקומבינטורי השימושי ביותר
כיום למציאת שיווי משקל נאש במשחקי Nondegenerate Bitmatrix בשני שחקנים.
האלגוריתם פותר בעיה המהווה מקרה פרטי של בעיית LPC.
פלט: אחד משיווי משקל נאש של המשחק.
נגדיר משחק Bitmatrix בשני שחקנים על ידי מטריצות התועלות ו .
האלגוריתם מוצא שווי משקל נאש אחד ומהווה הוכחה לקיומו של שווי משקל זה.
האלגוריתם עוקב אחר מסלול של זוגות קודקודים ב P X Q עבור ה polytopes P,Q המתחיל בנקודה (0,0) הנקראת Artificial equilibrium ונגמר בנקודת
המסלול עוקב אחר צלעות ב P ו Q לסירוגין תוך שמירה על הקודקוד ב polytope השני קבוע.
מכיוון שהמשחק הוא Nondegenerate קודקוד של
P נתון על ידי m - 1 תוויות.
זריקת תווית L של קודקוד X ב P מוגדרת על ידי מעבר על הצלע הייחודית שיש לה את כל התוויות של X פרט ל L.
הבחירה הראשונית של האלגוריתם תהיה אסטרטגיה טהורה K של שחקן (כל תווית ב M ∪ N) הנקראת missing label.
בסוף הצלע המתאימה הצלע החדשה שנבחרת היא שכפול שכן היא הייתה נוכחת ב polytope השני.
כעת הצלע המשוכפלת נזרקת ב polytope השני ונבחרת צלע חדשה.
אם הצלע שנבחרה היא ה missing label האלגוריתם מסתיים והוא מצא
אחרת חוזר על עצמו על ידי זריקת הצלע המשוכפלת ב polytope השני וכן הלאה...
האלגוריתם מסתיים ומוצא את שיווי משקל נאש מכיוון שב P X Q יש מספר סופי של זוגות קודקודים.
זוג הקודקודים הבא במסלול תמיד ייחודי ולכן לא מבקרים באותו זוג קודקודים פעמיים שכן אז הייתה אפשרות נוספת להמשך מלכתחילה.
מכיוון שמספר הקודקודים ב P X Q אקספוננציאלי ב n ו m זמן הריצה של האלגוריתם אקספוננציאלי.
לא מזמן הוכח שהאלגוריתם שייך למחלקת הסיבוכיות PPAD_(מחלקת_סיבוכיות).
קיימים מספר שיפורים של האלגוריתם המנצלים יוריסטיקות שונות על מנת לשפר את זמן הריצה בפועל:
"אלגוריה על השפעת הממשל הטוב והרע" הוא שמה של סדרת פרסקאות מאת הצייר האיטלקי, בן תקופת הרנסאנס אמברוג'יו לורנצטי (Ambrogio Lorenzetti).
הפרסקות, המכסים שלושה קירות ב"פאלאצו פובליקו" (Palazzo Pubblico) בעיר סיינה צוירו בין השנים 1337–1340. הם מהווים אחת מיצירות האמנות החילוניות החשובות ביותר של תקופת הפרוטו-רנסאנס באיטליה.
חשיבות נוספת היא בהצגה של אחד מתיאורי הנוף הריאליסטים הראשונים של עיר רנסאנסית ושל האזור הכפרי שבצידה.
הפרסקאות מצוירים על קירות "היכל התשעה" ("Sala dei Nove") הידוע גם כ"היכל השלום" ("Sala della Pace"), חלל ששימש כמקום הפגישות והכינוסים של שליטי העיר סיינה, שהם אלו שהזמינו את הפרסקו.
משמעותה של אלגוריה בציור מובעת בעימות בין הממשל הרע לבין הממשל החילוני הנאור, המתוארים על גבי שני קירות מנוגדים.
"הממשל הטוב" מתואר כהיכל משפט ובמרכזו דמות של גבר השופט את האנשים לחסד ולשבט.
התיאור מאזכר את תיאור יום הדין האחרון באמנות הנוצרית.
לצידו של השופט, היושב על גבי ספסל יושבות האנשות של מידות טובות כגון שלום, המתוארת כאישה בלונדינית הלבושה בגד לבן.
לצד תיאור המשפט מופיעה האנשה נוספת של מידת הצדק, בדמותה של אישה היושבת על כס.
מעליה מופיע דמות מרחפת המהווה האנשה של מידת החוכמה.
דמותה של "צדק" מאזכרת את האיקונוגרפיה של דמות מריה "מלכת השמיים", שהוא אחד מן התארים של מרים, אם ישו.
דמות זו שימשה כפטרוניתה של העיר סיינה.
ה"ממשל הרע" מתואר באופן הפוך לממשל הטוב.
במרכז תיאור השליט כדמות שטנית בעלת קרניים.
הפרסקו מציין כי שליט זה הוא "טירן", כלומר שליט עריץ.
הדמות עטויה גלימה מוזהבת ומחזיקה בידה גביע מוזהב.
מתחתיה מצוירות 6 מידות רעות: אכזריות, רמאות, זיוף ורוגז, חוסר הרמוניה ורשעות.
לרגליה מתוארת עז, המסמלת תאוה.
אלגברת המנה - הכללה של חבורת המנה וחוג המנה למבנה אלגברי כללי.
משמשת בין היתר להכללת משפטי האיזומורפיזם באלגברה אוניברסלית.
יהי מבנה אלגברי עם n פעולות, ויהא יחס שקילות על אברי A כך שלכל פעולה , אם מתקיים עבור i=1...k ,מתקיים גם:
יחס השקילות משרה מבנה אלגברי חדש שנקרא אלגברת מנה שאבריו הם מחלקות השקילות המתאימות עם הפעולות:
דוגמה -הכללה של משפט האיזומורפיזם הראשון:
יהיו A ו-B מבנים אלגבריים ויהא F אפימורפיזם מ-A על-B,אזי:
כש- Φ יחס השקילות המוגדר על אברי A כך: אם ורק אם .
תחילה נוכיח ש-Φ משרה אלגברת מנה:
תהי פעולה k-ארית, ויהיו (לפי Φ) עבור i=1...k (זאת אומרת עבור i=1...k).
נגדיר הומומורפיזם מ-A/Φ ל-B כך:
הוא חח"ע כי צמצמנו את כל הערכים השווים למחלקות שקילות (איברים בודדים),ועל בירושה מ-F.
במתמטיקה, אלגברת מלצב היא אלגברה לא אסוציאטיבית, המתקבלת מאלגברה אלטרנטיבית באותו אופן שבו אפשר לקבל אלגברת לי מכל אלגברה אסוציאטיבית.
לפיכך, כל אלגברת לי היא אלגברת מלצב, ואפשר להכליל מרכיבים משמעותיים בתורת המבנה של הסוג הראשון, אל המבנה הכללי יותר.
מאידך, כמעט כל אלגברת מלצב פשוטה היא אלגברת לי.
האלגברות נקראות על-שם אנטולי מלצב, שהגדיר והחל לחקור אותן ב-1955.
ככל אלגברה לא אסוציאטיבית, אלגברת מלצב היא מרחב וקטורי M מעל שדה, עם תבנית ביליניארית .
התבנית נדרשת לקיים את האקסיומות הבאות:
אלגברות לי מוגדרות על ידי החלפת האקסיומה השנייה בזהות יעקובי , שהיא בבירור חזקה יותר.
את האקסיומה השנייה אפשר לכתוב כ- .
בפרט, כל איבר מהצורה שייך ל- .
אם אלגברה אלטרנטיבית, הפעולה מגדירה עליה מבנה של אלגברת מלצב.
אלגברה לא אסוציאטיבית שכל תת-אלגברה שלה הנוצרת על ידי שני איברים היא אלגברת לי, נקראת אלגברת לי בינארית.
במאפיין שונה מ-2, אפשר לתאר תכונה זו באמצעות אקסיומות: ו- .
כל אלגברת לי היא אלגברת מלצב, וכל אלגברת מלצב היא אלגברת לי בינארית (כפי שאלגברה אלטרנטיבית עם שני יוצרים היא אסוציאטיבית).
במאפיין שונה מ-2, אלגבראות מלצב פשוטות מתחלקות לשני סוגים: אלגבראות לי פשוטות, או (כאשר המאפיין שונה מ-3) החלק הטהור באלגברת קיילי פשוטה ביחס לפעולת הקומוטטור.
האלגברה האחרונה היא אלגברה 7-ממדית מעל השדה; שתי אלגבראות כאלה איזומורפיות אם ורק אם אלגבראות הקיילי המתאימות הן איזומורפיות.
במאפיין 0, המבנה של אלגבראות מלצב נחקר לעומק - מוגדרת עליהם תבנית עקבה (trace form), כלומר סימטרית ואסוציאטיבית, על ידי , כאשר הוא אופרטור ההכפלה מימין ב-x.
האלגברה פשוטה למחצה אם ורק אם התבנית רגולרית (בדומה לקריטריון המתאים באלגבראות לי בעזרת תבנית קילינג).
במקרה זה, האלגברה מתפרקת לסכום ישר של אלגבראות 7-ממדיות לעיל.
הרדיקל הפתיר של אלגברת מלצב מתלכד עם החלק המאונך של ביחס לתבנית K, ועל כן A פתירה אם ורק אם .
בנוסף, ניתן להגדיר תורת מודולים מעל אלגבראות מלצב, וללמוד בעזרתה הצגות של האלגבראות.
בתחום זה תוצאות דומות לתורת ההצגות של אלגבראות לי, במיוחד במחקר אלגבראות ניליות.
אלגוריתם k-מרכזים (k-means) הוא שיטה פופולרית עבור ניתוח אשכולות (Clustering) בכריית נתונים.
מטרתו לחלק את התצפיות ל-k אשכולות לפי מרכזי כובד (k-means).
כל תצפית משויכת לאחד מ"מרכזי הכובד".
על ידי בחירה נכונה של מרכזי כובד ניתן לאתר את הקבוצות השונות.
נדרשות תצפיות רבות על מנת להשתמש במודל ותוספת של תצפיות חדשות עשויה לחייב חישוב חוזר.
מדובר באלגוריתם היוריסטי שמשתמשים בו כדי לבצע חישובים שמובילים להתכנסות לפתרון מקומי (שאינו בהכרח הפתרון הטוב ביותר).
זהו מודל סטטיסטי שאינו מתבסס על ידע מוקדם על הנתונים אלא רק על תצפיות בפועל.
שיטה זו דומה לאלגוריתם EM המניח התפלגות הדוגמאות מכמה התפלגויות גאוסיניות.
מודל זה נוטה למצוא אשכולות בעלי מרחבי מידה הניתנים להשוואה.
בעוד שמנגנון ציפייה מביא למקסום ומאפשר לאשכולות להיות בעלי צורות שונות.
מודל זה לא ליניארי, ולכן הוא מאפשר להתמודד עם כל סוגי ההתפלגויות האפשריות.
האלגוריתם משמש לעיתים קרובות כשלב מקדים לאלגוריתמים אחרים, למשל כאשר רוצים למצוא נקודות התחלתיות.
האלגוריתם עובד בהינתן קבוצה של תצפיות , כאשר כל תצפית היא וקטור ממשי היכול להיות בעל מספר ממדים.
מטרת המודל היא לחלק את n התצפיות לk אשכולות, על מנת למזער את סכום המרחקים בין התצפיות בתוך האשכול.
האלגוריתם מאפשר להתמודד עם נתונים ללא התפלגות מוגדרת או ללא סיווג (קלספיקציה) וגם עם מצבים שבהם בתצפית מסוימת חסרות חלק מהמדידות של המשתנים.
האלגוריתם מאפשר לבצע למידה בלתי מונחית (Unsupervised learning) של סיווגים שונים של הנתונים.
את המונח K-means טבע ג'יימס מקווין בשנת 1967, אף על פי שמקורות הרעיון היו קודם לכן אצל הוגו שטיינהאוס בשנת 1957.
האלגוריתם הבסיסי הוצע לראשונה על ידי סטוארט לויד בשנת 1957 כטכניקה של Pulse-code modulation אף על פי שהוא לא פרסם זאת מחוץ למעבדות בל עד שנת 1982.
פורגי (E.W Forgy) את אותה השיטה, ולכן היא נקראת לעיתים גם לויד-פורגי.
נגדיר קבוצה ראשונית של k מרכזים ואז האלגוריתם ינוע לסירוגין בין שני שלבים הבאים:
נחשב לכל תצפית באשכול את המרכז הקרוב אליה לפי המרחק האוקלידי מהמרכזים שנבחרו, זה באופן אינטואיטיבי מרכז הכובד "הקרוב ביותר" (מבחינה מתמטית, זה אומר שמתקיימת חלוקת תצפיות לפי דיאגרמת וורונוי שנוצרת על פי המרכזים) למעשה נוודא שכל מקיים כך שלכל יותאם רק אחד גם אם יותר מאחד מתאים.
נחשב את המרכזים מחדש על פי המרחק האוקלידי מהנקודות שהוקצו אליהם (למעשה פורמלית נעדכן כל מרכז על פי הכלל הבא:האלגוריתם מתכנס כאשר בשלב העדכון הערכים מפסיקים להשתנות ומתקבל ערך קבוע.
אין ערובה לכך שפתרון אופטימלי ימצא באמצעות אלגוריתם זה.
שימוש בפונקציית מרחק שונה אחרת מאשר מרחק אוקלידי עלולה לגרום לאלגוריתם לא להתכנס.
שתי שיטות האתחול הנפוצות בשימוש הן פורגי (Forgy) וחלוקה אקראית.
שיטת פורגי בוחרת באופן אקראי k תצפיות ומשתמשת בהן בתור המרכזים הראשוניים.
בשיטת החלוקה האקראית ניתן קטגוריה רנדומלית לכל תצפית ואז נמשיך ישירות לשלב העדכון בו ייקבעו המרכזים ההתחלתיים.
שיטת החלוקה האקראית בדרך כלל עדיפה לאלגוריתמים: K-means, K-harmonic ו-Fuzzy K-means בעוד לאלגוריתם הסטנדרטי שיטת פרוג'י עדיפה.
כמות מינימלית של נקודות לאשכול.
מרחק מרבי בין שתי הנקודות המרוחקות ביותר מאותו אשכול.
ערך התכנסות שאם שלב העדכון לא עובר אותו אז האלגוריתם מפסיק לעבוד.
לאלגוריתם מספר יתרונות: הוא אינו מושפע מתצפיות חריגות (בניגוד לרגרסיה), זמן העיבוד לסווג דוגמה חדשה הוא קצר ביותר, והוא מאפשר לבצע למידה בלתי מונחית (Unsupervised learning).
יתרון נוסף המתבטא באחסון המודל הוא שאחרי שהוגדרו האשכולות ניתן לעבוד ללא נתוני המקור.
חסרונותיו הם בצורך בעיבוד מוקדם ולעיתים מרובה, הוא מושפע מבחירה של גבולות המשתנים, והוא אינו מאפשר לטפל בנתונים שאינם מספריים.
האלגוריתם תמיד ימצא פתרון כלשהו ולעיתים הפתרון אינו יציב או מייצג.
R (שפת תכנות) - מכילה מספר מימושים וגרסאות של האלגוריתם
Scikit-learn - חבילה של שפת התכנות פייתון המשמשת ללמידת מכונה.
מכילה גם היא מספר מימושים וגרסאות של האלגוריתם.
באלגברה מופשטת, אלגברת לי היא פתירה אם סדרת הנגזרת שלה מתאפסת החל ממקום מסוים.
לאלגברות לי פתירות יש תפקיד חשוב בתורת המבנה של אלגברות לי, והן קשורות גם לאלגברות נילפוטנטיות ופשוטות למחצה.
סדרת הנגזרת של היא הסדרה המוגדרת על ידי .
במילים אחרות, הסדרה היא .
נקראת פתירה אם סדרת הנגזרת שלה מתאפסת החל ממקום מסוים, כלומר קיים כך ש-.
כל אלגברת לי אבלית היא פתירה.
כל אלגברת לי נילפוטנטית היא פתירה.
כל תמונה אפימורפית ואלגברת מנה של אלגברת לי פתירה הם פתירים.
אם אידיאל של אלגברת לי , כך ש-, פתירים, אז פתירה.
סכום של שני אידיאלים פתירים הוא פתיר, לפי משפט האיזומורפיזם השני.
לפי משפט לי, בכל תת-אלגברת לי פתירה של אלגברת האנדומורפיזמים ניתן להציג את כל איברי האלגברה כמטריצות משולשיות עליונות.
הרדיקל של אלגברת לי נתונה הוא האידיאל הפתיר המקסימלי שלה.
אידיאל כזה קיים ויחיד לפי התכונה החמישית לעיל, ומסומן על ידי .
אפיון נוסף שלו הוא הסכום של כל האידיאלים הפתירים.
אלגברת לי בעלת רדיקל טריוויאלי נקראת אלגברת לי פשוטה למחצה.
במילים אחרות, זוהי אלגברת לי ללא אידיאלים פתירים.
אלגברות מסוג זה מהוות מוקד מרכזי במיון של אלגברות לי, ויש להן מיון מלא.
באלגברה מופשטת, אלגברת לי פשוטה למחצה היא אלגברת לי בעלת רדיקל טריוויאלי.
אלגברות לי פשוטות למחצה הן מהאובייקטים החשובים ביותר בתחום, ויש להן מיון מלא.
תנאי שקול לפשוטה למחצה נתון על ידי תבנית קילינג.
הרדיקל של הוא האידיאל הפתיר המקסימלי המוכל ב-.
אידיאל כזה קיים ויחיד, מפני שסכום של שני אידיאלים פתירים הוא שוב פתיר.
נקראת פשוטה למחצה אם הרדיקל שלה טריוויאלי: .
התנאים הבאים להיותה של פשוטה למחצה שקולים:
כל אידיאל אבלי שלה טריוויאלי.
כל אידיאל פתיר שלה טריוויאלי.
כסכום של אלגברות לי פשוטות
לעיתים מגדירים אלגברת לי פשוטה למחצה כסכום ישר של אלגברות לי פשוטות.
משפט: כל אלגברת לי פשוטה למחצה היא סכום ישר של אידיאלים פשוטים שלה.
צורה זו הוא יחידה עד כדי שינוי סדר המחוברים.
כמסקנה ממשפט זה, נובע כי כל אלגברת לי פשוטה למחצה מקיימת , וכל אידיאל או תמונה אפימורפית שלה פשוטה למחצה.
גם נובע כי כל אידיאל של הוא סכום של אידיאלים פשוטים של .
תכונה חשובה נוספת היא שהנגזרות של אלגברת לי פשוטה למחצה מתלכדות עם העתקות הצמוד שלה, כלומר כל נגזרת היא מהצורה .
באלגברה מופשטת, אלגברת קליפורד (Clifford algebra) של מרחב וקטורי ותבנית ריבועית היא האלגברה החופשית ביותר בה הפעלת התבנית על איבר שקולה להעלאתו בריבוע.
מקרה פרטי שלה הוא אלגברה חיצונית (Exterior algebra), המתקבל בבחירת תבנית האפס.
כאשר הממד זוגי, אלגברת קליפורד היא אלגברה פשוטה מרכזית.
אלגברת קליפורד היא האינווריאנט השני של חוג ויט, והבניה שלה מגדירה הומומורפיזם אל חבורת בראואר.
היא נקראת על שמו של ויליאם קינגדן קליפורד, מתמטיקאי אנגלי שעסק בעיקר בגאומטריה.
יהי מרחב וקטורי מעל שדה ממאפיין שאינו 2 (מעתה ואילך).
אלגברת הטנזורים (Tensor algebra) מעל היא האלגברה החופשית , עם פעולת המכפלה הטנזורית (ביחס לשדה ).
אלגברת קליפורד של מרחב וקטורי ותבנית ריבועית היא , כלומר האלגברה החופשית ביותר בה הפעלת התבנית על כל איבר והעלאתו בריבוע מזוהים כאותו איבר.
אם בסיס ל-, לאלגברת קליפורד הבסיס - .
לאלגברת קליפורד הצגה - .
עבור תת-קבוצה , אם נסמן , אז , כאשר הסכום הוא על תת-קבוצות בסדר עולות.
שני איברים כנ"ל מקיימים .
אלגברת קליפורד היא אלגברה פשוטה אם n זוגי (ופשוטה כאלגברה עם אינוולוציה - תמיד).
המרכז של אלגברת קליפורד בממד זוגי הוא , ו- בממד אי זוגי.
בפרט, אלגברת קליפורד מממד זוגי מהווה אלגברה פשוטה מרכזית מעל השדה .
אלגברת קליפורד היא אלגברה עם אינוולוציה המוגדרת על הבסיס - .
עבור מרחב וקטורי חד־ממדי ותבנית ריבועית , אלגברת קליפורד היא .
אם מרחב וקטורי דו-ממדי, ו- הצורה האלכסונית, אז - אלגברת קווטרניונים מעל .
כל אלגברת קליפורד מממד זוגי היא מכפלה טנזורית של אלגברות קווטרניונים.
אם תבניות ריבועיות מסדר זוגי, אז , כאשר היא הדיסקרימיננטה.
אלגברת קליפורד קשורה אלגברה חיצונית (Exterior algebra).
ראשית, אלגברה חיצונית היא מקרה פרטי של אלגברת קליפורד, כאשר בוחרים את התבניות הריבועית האפסה - .
אז מקבלים , וזו בדיוק התכונה (היחידה) שמתקיימת באלגברה חיצונית.
כאשר , יש איזומורפיזם של מרחבים וקטוריים בין האלגברה החיצונית לאלגברת קליפורד, שאינו משמר את פעולת הכפל (פעולת הכפל ב- עשירה יותר).
אלגברת קליפורד מהווה קוונטיזציה של האלגברה החיצונית ביחס לתבנית הריבועית.
לפי בנייתה, לאלגברת קליפורד תכונה אוניברסלית, כלומר היא האלגברה הכללית ביותר המקיימת .
בניסוח מדויק, בהינתן אלגברה בה מתקיים (כאשר משוכן ב-A על ידי הומומורפיזם ), אז קיים הומומורפיזם אחד ויחיד , כך שהדיאגרמה הבאה קומוטטיבית:
במילים, זוהי האלגברה הכללית ביותר בעלת התכונה - כל אלגברה אחרת בעלת התכונה הזו היא תמונה של אלברת קליפורד.
אלגברת קליפורד היא אלגברה -מדורגת.
הוא משמר את , ולכן לפי התכונה האוניברסלית, הוא משרה מיפוי המהווה אינוולוציה שריבועה הוא הזהות.
לכן, אפשר לפרק לסכום ישר , כאשר הוא קבוצת האיברים שנשארים במקום תחת ההומורפיזם, הנקרא לעיתים גם החלק הזוגי.
מתקיים , ולכן זהו דירוג של האלגברה.
ניתן להוכיח כי בעצמה איזומורפית לאלגברת קליפורד.
במקרה שדה המספרים המרוכבים, ניתן להראות מפורשות כי יש תבניות ריבועיות כך ש-, כאשר מרחב וקטורי מממד .
אלגברת קליפורד מהווה אינווריאנט של חוג ויט לחבורת בראואר.
ביתר פירוט, לפי הדוגמה האחרונה לעיל, המיפוי של המחלקה של ב- (האידיאל של חוג ויט הנוצר מתבניות מסדר 4, או בשקילות מתבניות פיסטר מסדר 2), לחבורת בראואר מוגדר היטב ומהווה הומומורפיזם חוגים, זאת משום שבנוסחא בדוגמה 4 לעיל הדיסקרימיננטה אדישה לתבניות מ-.
לפי משפט, מההומומורפיזם הנ"ל נובע איזומורפיזם , לתת החבורה של חבורת בראואר מפיתול 2.
טענה זו היא בסיסית וחשובה בחקר המנות של שרשרת האידיאלים בחוג ויט - .
בנושא זה ראו גם תורת K של חוגים.
אלגוטק מערכות היא חברה בת של תאגיד פיליפס ועוסקת בפיתוח מערכות מידע ועיבוד בתחום ההדמיה הרפואית.
חברת האם, פיליפס, היא מהגדולות בשוק העולמי בנושא מכשירי הדמיה ומערכות מידע.
מרכז המחקר והפיתוח של החברה ממוקם ברעננה, ישראל, בו היא מפתחת פלטפורמה המאפשרת למוסדות רפואיים ניהול דיגיטלי כולל של קריאה ועיבוד תמונות רדיולוגיות ממכשירי הדמיה מגוונים, כמו CT, MRI ורנטגן, וכן ניהול של תמונות רפואיות אחרות מתחומים עתירי הדמיה כמו קרדיולוגיה, גינקולוגיה, אנדוסקופיה, רפואת עיניים, רפואת עור, פתולוגיה ופלסטיקה.
אלגוטק הוקמה בדצמבר 1992 על ידי מנשה בנימין, יחד עם דוד מובשוביץ ואהוד בן-ראובן, וחברת אלסינט.
בנימין ניהל את החברה עד לרכישתה על ידי פיליפס.
בעת הקמת החברה החזיקו עובדיה ומייסדיה בכ-75% ממניותיה, בעוד אלסינט החזיקה ביתרת המניות.
אלגוטק הייתה בין חברות ההיי-טק הראשונות ברעננה, ופעלה ממשרדים קטנים בין המוסכים של אזור התעשייה של רעננה.
בשלביה הראשונים ממונה באופן עצמאי, ללא עזרת משקיעים חיצוניים והתבססה על הכנסות ופיתוחים עבור חברת אלסינט.
ב-1998 נמכרה אלסינט, החברה עברה לפעילות עסקית עצמאית, וגייסה 6 מיליון דולר לפי שווי של 25 מיליון דולר, מקרנות הון הסיכון סטאר ונצ'רס וג'אפקו.
המוצר העיקרי של החברה באותה עת היה מערכת PACS, לניהול ואחסון תמונות הדמיה (picture-archiving-and-communications systems) אותו הפיצה באמצעות הסכמי OEM עם חברות טכנולוגיה רפואית בהן פיקר, טושיבה, שימאדזו, אלקטה אונקולוג'י סיסטמס, אקליפסיס וחברות נוספות.
בנוסף החלה לשווק את מוצריה ישירות ללקוחות.
ב-2001 הגיעו הכנסות החברה לכ-5 מיליון דולר.
ביוני 2002 חתמה אלגוטק על הסכם שיווק והפצה למוצר ה-PACS שלה עם חטיבת הרפואה של תאגיד איסטמן-קודאק.
במסגרת ההסכם הייתה איסטמן-קודאק אחראית על הטמעת, מסחור וייצור המערכת מול הלקוחות.
בנובמבר 2003 רכשה קודאק את החברה תמורת 42.5 מיליון דולר במזומן.
לאחר הרכישה הפכה אלגוטק לחברה בת בבעלות מלאה של קבוצת ההדמיה הרפואית של התאגיד.
בשנת 2007 קודאק החליטה לצאת כליל מפעילות בתחום הרפואי ומכרה אותה, כולל אלגוטק, לתאגיד ההשקעות הקנדי Onex.
פעילות זו החלה לפעול תחת שם חדש Carestream.
באוגוסט 2019 רכש תאגיד פיליפס את פעילות מערכות המידע הרפואית של Carestream, כולל אלגוטק שמוזגה בספטמבר 2021 לתוך פעילות "פיליפס ישראל" (המחזיקה מאז 2001 פעילות ענפה בישראל ומעסיקה כ-1,500 עובדים).
פלטפורמת הדימות של אלגוטק מספקת פתרונות למספר רב של צרכים כמו ניהול מערך הדימות, האיבחון (פיענוח), העיבוד, הדיווח, ההפצה, והארכוב של בדיקות רדיולוגיה וקרדיולוגיה לסוגים רבים של מרכזים רפואיים.
ניהול זה מתאפשר באמצעות שילוב של טכנולוגיות מגוונות הכוללות תקשורת מסוגים שונים, דחיסה והזרמת מדיה, טכנולוגיות אחסון ואיחזור מידע, וירטואליזציה, טכנולוגיות ענן, טכנולוגיות Web, טכנולוגיות מובייל, אלגוריתמיקה לעיבוד תמונות במספר ממדים, CAD (computer assisted diagnosis), טכנולוגיות זיהוי דיבור, עיבוד שפה טבעית, וניתוח "ביג דאטה".
מוצרי החברה מאפשרים לרופאים גישה מהירה לבדיקות הדמיה ומידע רפואי נלווה מכל מקום באמצעות אמצעי מחשוב ניידים ונייחים.
כל המוצרים מאושרים על ידי מנהל המזון והתרופות האמריקני (FDA).
נתח השוק של מוצרי אלגוטק בישראל הוא כ-70%, וכולל את כללית שירותי בריאות והמרכז הרפואי ע"ש שיבא בתל השומר.
באנליזה נומרית, אלגוריתם QR הוא אלגוריתם למציאת ערכים עצמיים ווקטורים עצמיים של מטריצה.
סיבוכיות האלגוריתם עבור מטריצה בגודל היא .
קיים אנלוג לאלגוריתם עבור פירוק לערכים סינגולאריים.
האלגוריתם פותח באופן עצמאי בסוף שנות החמישים על ידי מדען המחשב הבריטי ג'ון פרנסיס ועל ידי המתמטיקאית הרוסיה ורה קובלנובסקיה.
תהא מטריצה A שעבורה רוצים לחשב את הערכים העצמיים, ונגדיר A0:=A.
בצעד ה-k (כאשר k מתחיל מ-0) מחשבים פירוק QR של Ak=QkRk כאשר Qk היא מטריצה אורתוגונלית (כלומר QT = Q−1) ו-Rk היא מטריצה משולשת עליונה.
אחר כך מגדירים Ak+1 = RkQk.
לכן כל המטריצות Ak הן מטריצות דומות ויש להן ערכים עצמיים דומים.
אלגוריתם QR יציב נומרית הודות להתבססות על התמרות אורתוגונליות דומות.
לאלגוריתם QR קדם אלגוריתם LR שהתבסס על פירוק LU ולא על פירוק QR.
פירוק QR הוא יותר יציב ולכן אלגוריתם LR כמעט ואינו נמצא בשימוש כיום.
אלגוריתם אהו-קוראסיק הוא אלגוריתם לחיפוש מחרוזות שהומצא על ידי אלפרד אהו ומרגרט קוראסיק.
זהו אלגוריתם להתאמת מילון, המאתר פריטים מתוך סט סופי של מחרוזות ("מילון") בתוך טקסט הקלט.
האלגוריתם מתאים את כל המחרוזות בו זמנית.
הסיבוכיות של האלגוריתם ליניארית באורך של המחרוזות בתוספת אורך הטקסט לחיפוש ומספר ההתאמות בפלט.
היות שמוצאים את כל ההתאמות, ייתכן מספר ריבועי של התאמות אם כל תת-מחרוזת מתאימה (למשל מילון = a, aa, aaa, aaaa ומחרוזת קלט aaaa).
באופן לא פורמלי, האלגוריתם בונה אוטומט סופי המזכיר trie עם מעברים נוספים בין צמתים פנימיים שונים.
מעברים נוספים אלו מאפשרים מעבר מהיר בין התאמת מחרוזת שנכשלה (למשל, חיפוש אחר cat ב-trie שאינו מכיל cat, אבל מכיל את המילה cart, וכך נכשל בצומת שהרישא שלו היא ca), לענפים אחרים של ה-trie שלהם רישא משותפת (למשל, במקרה הקודם, ענף של המילה attribute עשויה להיות המעבר לרוחב הטוב ביותר).
דבר זה מאפשר לאוטומט מעבר בין התאמות של מחרוזות מבלי לחזור על עקבותיו.
כאשר מילון המחרוזות ידוע מראש (לדוגמה, מסד נתונים של וירוסי מחשב), בניית האוטומט יכולה להתבצע פעם אחת offline והאוטומט נשמר לשימוש מאוחר יותר.
במקרה זה, זמן הריצה ליניארי באורך הקלט בתוספת מספר ההתאמות.
אלגוריתם Aho–Corasick להתאמת מחרוזות היווה את הבסיס המקורי של הפקודה fgrep ב-Unix.
בדוגמה זו, נעסוק במילון המכיל את המילים הבאות: {a,ab,bab,bc,bca,c,caa}.
הגרף להלן הוא מבנה הנתונים הנבנה על ידי Aho–Corasick מהמילון הנתון, כאשר כל שורה בטבלה מייצגת צומת ב-trie, ועמודה מייצגת את הרצף (הייחודי) של התווים מהשורש לצומת.
למבנה הנתונים יש צומת אחד עבור כל קידומת של כל מחרוזת במילון.
נסמן צומת שנמצא במילון בכחול, ואת יתר הצמתים באפור.
ניצור קשת "בן" מכוונת בצבע שחור מכל צומת לצומת ששמו מתקבל על ידי שרשור תו אחד.
לכן תהיה קשת שחורה מ-(bc) ל-(bca).
ניצור קשת "סיפא" מכוונת בצבע כחול מכל צומת לצומת שהוא הסיפא ממש הארוכה ביותר האפשרית שלו בגרף.
הארוכה ביותר מהן שנמצאת בגרף היא (a).
לכן תהיה קשת כחולה מ- (caa) ל-(a).
ניתן לחשב את כל הקשתות הכחולות בזמן ליניארי באופן רקורסיבי על ידי מעבר על הקשתות הכחולות של האב, עד שמגיעים לצומת שלו בן שמתאים לאות של צומת המטרה.
ניצור קשת "סיפא של מילון" בצבע ירוק מכל צומת לצומת הבא במילון שניתן להגיע אליו על ידי מעבר על קשתות כחולות.
לדוגמה, יש קשת ירוקה מ- (bca) ל-(a) כי (a) הוא הצומת הראשון במילון (כלומר צומת כחול) שניתן להגיע אליו על ידי מעבר על קשתות כחולות ל-(ca) ומשם ל-(a).
ניתן לחשב קשתות ירוקות בזמן ליניארי באופן רקורסיבי על ידי מעבר על קשתות כחולות עד שמצא צומת כחול, ושמירת מידע זה (memoizing).
בכל שלב מתקדמים מהצומת הנוכחי על ידי מציאת בן מתאים,
ואם אין כזה, על ידי מציאת בן של הסיפא, ואם
זה לא עובד, על ידי מציאת בן של הסיפא של הסיפא, וכן הלאה, ומסיימים לבסוף בשורש אם אף צומת מתאים לא נמצא קודם לכן.
כאשר האלגוריתם מגיע לצומת, הוא מדפיס את כל ערכי המילון המסתיימים במיקום התו הנוכחי בטקסט הקלט.
דבר זה מתבצע על ידי הדפסה של כל צומת שניתן להגיע אליו בעזרת "חיצי סיפא של מילון", כאשר מתחילים בצומת זה, וממשיכים עד שמגיעים לצומת שאין לו קשתות סיפא של מילון.
בנוסף, הצומת עצמו מודפס, אם הוא ערך במילון.
ביצוע על מחרוזת הקלט abccab מניב את הצעדים הבאים:
אלגואסס (בספרדית: Alguazas) היא עיירה הנמצאת בספרד וממוקמת בקהילה האוטונומית והפרובינציה מורסיה.
נקודת ציון חשובה של העיר היא מנזר אונופריוס שנבנה בתחילת המאה ה-16 ופועל מאז.
אַלְגוֹרָבּ (מערבית: الغراب "אל-ע'וּראבּ" - העורב) או δ בעורב הוא הכוכב השלישי בבהירותו בקבוצת הכוכבים עורב עם בהירות נראית מדרגה 2.94. במרחק זוויתי של כ-2.6 מעלות מדרום-דרום-מערב לכוכב נמצאת הערפילית הפלנטרית NGC 4361 ובמרחק זוויתי של כ-5.5 מעלות מצפון-צפון-מזרח לו נמצאת גלקסיית הסומבררו.
אלגורב הוא תת-ענק לבן-כחלחל מסוג ספקטרלי A0 IV (לפעמים מסווג גם ככוכב הסדרה הראשית כחול מסוג ספקטרלי B9.5 V) שנמצא במרחק של כ-87 שנות אור ממערכת השמש.
מסתו כ-2.6 מסות שמש, רדיוסו כ-2.4 רדיוסי שמש וטמפרטורת פניו כ-10,500 קלווין.
הוא מאיר בעוצמה של פי 40 מעוצמת ההארה של השמש באור נראה, אך מכיוון שטמפרטורת פניו גבוהה מזו של השמש, חלק משמעותי מקרינתו היא בתחום העל-סגול כך שעוצמת ההארה הכוללת שלו היא יותר מפי 50 מעוצמת ההארה של השמש.
גילו של אלגורב מוערך בכ-200 מיליון שנים והוא נמצא ככל הנראה לקראת סיומו של שלב ההיתוך של מימן להליום בליבתו, והוא צפוי להתנפח ולהתקרר עד שיהפוך לענק אדום.
במרחק זוויתי של כ-24 שניות קשת מאלגורב יש כוכב נוסף עמום בהרבה שנקרא אלגורב B, שנראה שיש לו תנועה עצמית ומהירות רדיאלית דומות לאלו של אלגורב, ולכן הם ככל הנראה קשורים זה לזה.
אם הם אכן קשורים, הם מקיפים זה את זה במרחק של כ-650 יחידות אסטרונומיות ובזמן הקפה של לפחות 9,400 שנים.
אלגורב B הוא כוכב הסדרה הראשית כתום מסוג ספקטרלי K0 V עם מסה של כ-80% ממסת השמש ורדיוס של כ-75% מרדיוס השמש.
טמפרטורת פניו כ-5,000 קלווין והוא מאיר בעוצמה של עשירית מעוצמת ההארה של השמש באור נראה, אך רוב קרינתו היא בתחום התת-אדום כך שעוצמת הארתו הכוללת היא כשליש מעוצמת ההארה של השמש.
אלגורב B פולט יותר קרינה תת-אדומה מהצפוי לכוכב מסוגו, ככל הנראה תוצאה של מעטפת אבק שמקיפה אותו, בולעת חלק מהאור הנראה ופולטת קרינה תת-אדומה.
קיומה של המעטפת מצביע על כך שככל הנראה זהו כוכב צעיר שעוד לא הספיק לאסוף את כל החומר שבסביבתו.
גילו מוערך ב-40–90 מיליון שנים, בין רבע לחצי מגילו של אלגורב ומשערים שהוא נמצא בסדרה הראשית זמן קצר יחסית ובעבר הוא היה כוכב T בשור.
לא ברור ממה נובע הפרש הגילאים בין הכוכבים ואיך ייתכן שהם נוצרו באותה סביבה בהפרש זמנים כה גדול.
אלגוריתם KMP הוא אלגוריתם בתחום מדעי המחשב להתאמת תבניות הפועל בזמן ליניארי במקרה הגרוע.
האלגוריתם התגלה בשנת 1970 על ידי דונלד קנות' ווואן פראת', ובאופן בלתי תלוי על ידי ג'יימס מוריס.
השלושה פרסמו יחדיו את האלגוריתם בכתב העת SIAM בשנת 1977.
מטרתו של האלגוריתם היא למצוא מופעים של מחרוזת P (תבנית, pattern) בתוך מחרוזת T (טקסט), כאשר .
בעוד האלגוריתם הנאיבי לביצוע פעולה זו פועל בזמן בזמן הגרוע, אלגוריתם KMP עובד בזמן בזמן גרוע.
האלגוריתם הנאיבי להתאמת מחרוזות, יחפש עבור כל מיקום בטקסט האם הוא התחלה של המחרוזת.
אלגוריתם זה עובד בזמן .
אלגוריתם KMP משתמש בטרנזיטיביות של התאמת מחרוזות על מנת לחסוך השוואות מיותרות.
בכל פעם שהאלגוריתם יתקל בנקודת חוסר התאמה בטקסט, הוא יחזור להתאים את הרישא הארוכה ביותר של התבנית המתאימה לסיפא הארוכה ביותר של הטקסט בנקודה בו נתקלנו בחוסר התאמה.
על מנת להתאים בין הרישא הארוכה ביותר לסיפא הארוכה ביותר, נבנה טבלה ייעודית ונוכל להציץ בה בזמן קבוע.
כאשר ניתקל בתבנית ABCABCD ובטקסט ABCABCABCABCABCABCD, נקודת אי ההתאמה הראשונה תהיה באינדקס 6.
ניתן לשים לב, שהאלגוריתם הנאיבי יתחיל לחפש מהאינדקס הבא (1), למרות שניתן לדלג מידית לאינדקס 3. KMP יודע לדלג לאינדקס 3, מכיוון שלאחר שהתאמנו את A באינדקס 0, B באינדקס 1 ו-C באינדקס 2, ברור שלא נוכל להתאים את A באינדקסים 1 או 2.
בנוסף, לאחר שנתחיל את הבדיקה מחדש באינדקס 3, אין טעם לבדוק ששלושת התווים הראשונים זהים, מכיוון שווידאנו זאת כבר קודם, כלומר המחרוזת שהותאמה עד כה היא ABCABC, ומחרוזת זו נגמרת ב-ABC.
לכן, יש סיפא באורך 3 (ABC) שמתאימה לרישא באורך 3 (גם כן, ABC), ולכן ניתן לחסוך את ההתאמה של שלושת התווים הראשונים.
על ידי התאמת הרישא לסיפא, אנחנו הלכה למעשה מוודאים שלא ייווצר מצב בו אנו מדלגים על התאמה.
אם קיימת סיפא שמתאימה לרישא, אז אי אפשר לדלג על כל אזור אי ההתאמה, אבל בתוך הדילוג אנחנו כבר יודעים שהרישא שווה לסיפא, ולכן אין צורך לבדוק אותה.
אם לא קיימת רישא שמתאימה לסיפא, אזי בכל מקום אליו נקפוץ בטווח שכרגע בדקנו לא תמצא התאמה, ולכן ניתן לדלג ישירות על כל החלק המאומת.
מהגדרה זאת ניתן לקבל את ההרגשה שהאלגוריתם פועל בזמן ליניארי, בהנחה שפעולות הבדיקה על הרישא והסיפא פועלות בזמן קבוע.
אורך תבנית - m, אורך טקסט - n
בנה טבלת סיפות A עבור התבנית P
אם j=m, דווח על התאמה באינדקס i-j
קלט - T באורך n
צור מערך A בגודל n עם אפסים
שים באיבר הראשון במערך -1
נוכיח שכל התאמה אפשרית במחרוזת נמצאת על ידי האלגוריתם, בהנחה שהטבלה הנוצרת נכונה.
תהא התאמה באינדקס k, כלומר .
על מנת שתימצא התאמה באינדקס k, צריך להתחיל את הלולאה הפנימית עם ערכי i ,j המקיימים .
נשים לב שההפרש בין i ל-j משתנה בשתי אפשרויות -
קל לראות שבדיוק אחד מהמקרים האלה מתרחש בכל פעם.
במקרה הראשון, ההפרש גדל בדיוק ב-1, ולכן לא נדלג על שום התאמה.
במקרה השני, ההפרש גדל בדיוק ב- וגם j לא שווה 0. נניח בשלילה שקיים אינדקס התאמה k המקיים , זאת אומרת ש.
בנוסף, מכיוון שהאלגוריתם הגיע לאינדקס j, מתקיים .
לכן, מתקיים , כלומר אורך הרישא הארוכה ביותר שמתאימה לסיפא הארוכה ביותר באינדקס j היא לכל הפחות , ולפי הגדרת הטבלה בסתירה להנחת השלילה.
ההוכחה שהאלגוריתם לא מחזיר התאמות שאינן נכונות פשוט למדי - מכיוון שהאלגוריתם משתמש בטרנזיטיביות של שוויון תווים, אזי אם התאמנו כבר סיפא אין צורך לבדוק מחדש את הרישא, ועל מנת שהאלגוריתם יודיע על התאמה יש לבדוק את כל האיברים שאחרי הרישא איבר-איבר, וזהו האלגוריתם הנאיבי.
נרצה להוכיח שבהינתן מחרוזת האלגוריתם מוציא את טבלת הסיפות הנכונה, ו-(-1) במקום הראשון.
הערה - קל לראות .
נניח שהאלגוריתם עובד עבור ערכים קטנים מ-i, נוכיח שהוא עובד עבור i -
מקרה ראשון - אם מתקיים וגם הוא אינדקס שהסיפא הארוכה ביותר הנגמרת אצלו המתאימה לרישא הארוכה ביותר זהה לסיפא באינדקס .
הערה - לפי ההגדרה, מקיים את זה.
נניח שמתקיים , זאת אומרת .
אבל אם נוריד את התו האחרון מהסיפא והתו האחרון מהרישא, אזי יש לנו התאמה באורך לכל הפחות באינדקס , בסתירה להנחה שהאלגוריתם צודק עבור ערכים קטנים מ-i ובפרט .
במקרה זה, מכיוון שלפי הגדרה וגם הוא חסם עליון לאורך הסיפא המקסימלית, אזי מתקיים בוודאות .
מקרה שלישי - אם מתקיים .
במקרה זה, התו החדש שנוסף אינו המשך של הרישא הקודמת, ולכן נחפש רישא קצרה יותר.
מכיוון שהרישא הקודמת שווה לסיפא הקודמת, אזי הסיפא הארוכה ביותר המתאימה לרישא הארוכה ביותר ברישא הקודמת, היא גם סיפא של הסיפא הקודמת.
מההנחה שהאלגוריתם פועל עבור קלטים קטנים, מתקיים שאורך הסיפא החדשה המתקבלת הוא המקסימלי, ולכן כל לא יכול להיות אורך הסיפא שאינה כוללת את התו האחרון.
כלומר - גם אם האלגוריתם לא ימצא בשלב זה את אורך הסיפא הוא יתחיל באיטרציה הבאה עם , ולכן האלגוריתם תמיד יגיע בסופו של דבר למקרה הראשון או השני.
נוכיח שלא קיים כך ש-k הוא האורך של הסיפא הארוכה ביותר הנגמרת ב- ומתאימה לרישא.
אם זה אכן היה מתקיים, אז לפי הגדרה , אבל מכיוון ש- הוא אורך הסיפא הארוכה ביותר המתאימה ל-, וגם לפי הטרנזיטיביות הסיפא הנגמרת ב- זהה לסיפא הנגמרת ב-, אז למעשה , וזאת אומרת שאורך הסיפא המקסימלית הנגמרת ב- היא לפחות k, בסתירה לכך שהנחנו שהאלגוריתם צודק עבור קלטים קטנים.
זאת גם למעשה ההוכחה ש-הוא חסם עליון לאורך הסיפא, שהרי עבור כלשהו.
זמן הריצה הכולל של האלגוריתם הוא , כאשר הזמן הדרוש לבניית טבלה של התבנית הוא וזמן החיפוש הדרוש הוא .
כאשר אנחנו מבצעים את החיפוש עצמו, בכל איטרציה של כל אחת מהלולאות יש לפחות קידום אחד של i, כלומר לא קיימת איטרציה בה i לא קודם.
בנוסף, כל איטרציה של הלולאות מפעילות פעולות, ולכן בסך הכל יש לכל היותר פעולות.
נסמן מונה C1 הסופר כמה פעמים עודפות האלגוריתם ביקר בתא בודד, ומונה C2 הסופר כמה פעמים האלגוריתם ביקר פעם בודדת.
מתקיים מכיוון שיש n+1 תאים בטבלה.
כפי שצוין קודם, מתקיים , וגם אם ורק אם קיימת איטרציה אחת בדיוק (כלומר C2 מקודם).
בנוסף, מתקיים לפי הגדרת הרישא.
לכן, ניתן לכתוב , כלומר במקרה הגרוע יש לולאה יורדת.
נחבר את התנאים - על מנת שיתקיים צריך שיתקיים (לפי התנאי הראשון), ועל מנת שנוכל לקדם את C1, צריך שיתקיים .
בסך הכל, על מנת לקדם את C1 יש לקדם את C2, ולכן מתקיים , ומספר האיטרציות הכולל קטן מ-, או , כנדרש.
אלגה (בקזחית: Алға; ברוסית: Алга́) היא עיר במחוז אקטובה שבמערב קזחסטן.
לפי אומדן רשמי מתאריך 1 בינואר 2023, התגוררו בעיר 22,740 בני אדם.
על שם העיירה, נקרא מכתש במאדים בשם אלגה.
אלגה נמצאת כ-1,019 קילומטרים מעיר הבירה אסטנה וכ-45 קילומטרים מבירת המחוז אקטובה.
העיירה נמצאת על גדות נהר האילק .
העיירה ממוקמת ליד כביש A27. התחבורה הציבורית העיקרית של התושבים באלגה הם מיניבוסים קטנים.
ב-10 בפברואר 1934 התקבלה אלגה ככפר עבודה, וב-1961 הוכרזה אלגה כעיירה.
בתקופה הסובייטית, פעל בעיירה מפעל כימי שבו יצרו דשן.
הוא נסגר ונהרס מאחר שגרם לנזק סביבתי חמור.
בעיירה ישנם בתי ספר, בית יתומים, בריכת שחייה, מכללה תעשייתית-טכנית ובית ספר לנוער שבו נלמד רק ספורט.
אלגוסק היא חברת תוכנה לניהול מדיניות אבטחת רשת, המכונה גם ניהול מדיניות חומת אש (firewall), באחסון ענן, ברשתות תקשורת מקומיות, במרכזי נתונים, ובפלטפורמות היברידיות.
מוצרי אלגוסק מאבטחים קישוריות של יישומים באמצעות אוטומציה, ניהול ואכיפת מדיניות האבטחה בין חומות אש, נתבים, רשתות וירטואליות פרטיות,SDN ומערכות אבטחת המידע המשויכות אליהם.
ארגונים משתמשים במוצרי אלגוסק לניהול תצורת מערכות האבטחה שלהם, לזיהוי נקודות תורפה, בחינת ואימות המערכות כנגד מדיניות האבטחה שלהן, הפחתת עלויות הניהול, ולווידוא עמידה בתקנות כגון PCI-DSS ו-Sarbanes-Oxley.
טכנולוגיית הליבה של אלגוסק פותחה בשנת 2001 על ידי אבישי וול וצוות החוקרים שלו במעבדות בל בארצות הברית, בה עבד כפוסט-דוקטורנט.
לאחר שחזר לישראל וול שיתף פעולה עם יובל בר-און כדי להקים את אלגוסק בשנת 2004. בר-און עבד קודם בחברת קומברס ולאחר מכן ברד תקשורת מחשבים, והיה ממייסדי חברת "אקטליס נטוורקס" ב-1999.
בעת הקמתה מיקמה אלגוסק את המטה שלה ברסטון, וירג'יניה.
בשנת 2010 העבירה את המטה ומשרד המכירות שלה בצפון אמריקה לרוזוו, ג'ורג'יה (אזור אטלנטה).
בשנת 2012 אלגוסק העבירה את המטה שלה לרידגפילג פארק, ניו ג'רזי.
בנוסף למשרד בניו ג'רזי, יש לאלגוסק משרדי מכירות בלונדון ובסינגפור, ומרכז מחקר ופיתוח בפתח תקווה, ישראל.
בשנת 2010 הכריז מנכ"ל החברה יובל בר-און על יעד העסקה שוויוני בחברה של 50% גברים ו-50% נשים.
באותה עת מצבת הנשים בחברה כבר הייתה כ-40%.
בינואר 2018, גייסה אלגוסק 36 מיליון דולר מ"קלארידג' ישראל", קרן ההשקעות של משפחת ברונפמן, כדי לתמוך בהתרחבותה הגלובלית שלה.
זו הייתה ההשקעה החיצונית הראשונה בחברה, שעד אז כל המימון לפעילותה הסתמך על ההון העצמי של המייסדים והכנסות מלקוחות.
בפברואר 2020, אלגוסק חתמה הסכם אסטרטגי עם חברת סיסקו.
בדצמבר 2022, רכשה אלגוסק את החברה אמריקאית Prevasio, העוסקת בפיתוח פלטפורמה להגנה על יישומים במערכת הענן.
אלגוסק מספקת את מוצריה הן כמודולים עצמאיים והן באמצעות חבילה משולבת, AlgoSec Security Management Suite, הכוללת:
AlgoSec Firewall Analyzer: אוטומציה של ביקורת וניתוח של חומות אש, נתבים, VPN ומכשירי אבטחה אחרים.
AlgoSec FireFlow: אוטומציה של זרימת עבודה של ניהול שינויים באבטחה.
AlgoSec Cloud: אוטומציה של מדיניות אבטחה ושינוי ניהול בסביבה ההיברידית והמולטי-ענן.
לקוחות אלגוסק כוללים ארגונים בתחום הקמעונאות, בריאות, פיננסיים, טלקום, חינוך, ממשלה, אנרגיה ושירותים, תחבורה, ייצור, ספקי שירותים מנוהלים, מבקרים ויועצים ברחבי העולם.
ספקי אבטחת רשת אחרים מספקים ניהול פעולות, ביקורת ושינוי אוטומציה של מוצרי אלגוסק.
שותפי הטכנולוגיה של אלגוסק כוללים את צ'ק פוינט, סיסקו, F5, פורטינט, ג'וניפר נטוורקס, פאלו אלטו נטוורקס, Amazon Web Services, מיקרוסופט, VMWare, IBM QRadar, Splunk, CA, HP וServiceNow.
אלגואזאורוס (שם מדעי: Algoasaurus; מילולית: "לטאת מפרץ אלגואה") הוא סוג של דינוזאור זאורופוד שחי במשך הקרטיקון התחתון באפריקה שלפני 140 עד 125 מיליון שנה מזמננו.
זאורופוד זה השתייך לקבוצה אאוזאורופודה, והיה בעל דמיון מסוים לטיטאנוזאורים, אף שלא היה קרוב אליהם כלל.
הוא התגלה בתצורת קירקווד שבכף התקווה הטובה, דרום אפריקה.
חלק מהחוקרים רואים בסוג זה טקסון בטל (nomen dubien).
הדינוזאור התגלה בידי החוקר הסקוטי-דרום אפריקאי רוברט ברום ב-1904 משרידים מקוטעים של חוליות, עצם ירך וקטעי פרקי אצבעות, אף שהיו עוד כמה עצמות שלא נאספו שהשתייכו לסוג זה.
אלה לא זוהו ונהרסו בידי עובדים כדי לייצר מהם לבנים.
האלגואזאורוס לא היו דומה לאף זאורופוד והוא נחשב לאחד מהפרימיטיבים שבזאורופודים.
ככל הנראה פרט בוגר הגיע לאורך 9 מטרים, גובה של 3 מטרים ומשקל ממוצע של 10 טון בקירוב.
הוא היה בעל צוואר ארוך שעזר לו להגיע לצמרות עצים כדי להיזון מהעלים שבצמרות.
כמו כן היה בעל זנב ארוך מייצב.
במתמטיקה, אלגברת לייבניץ היא אלגברה לא אסוציאטיבית, המהווה הכללה של אלגברת לי.
מרחב וקטורי L עם פעולת כפל הוא אלגברת לייבניץ שמאלית אם כל פעולת כפל משמאל היא נגזרת (אלגברה); ואלגברת לייבניץ ימנית אם כל פעולת כפל מימין היא נגזרת.
כל אלגברת לי היא אלגברת לייבניץ שמאלית וימנית (זוהי זהות יעקובי).
אלגברת לייבניץ שמאלית או ימנית היא אלגברת לי אם פעולת הכפל שלה היא אנטי-סימטרית.
תהי L אלגברת לייבניץ שמאלית.
המרחב הנפרש על ידי ריבועים הוא גרעין לייבניץ, .
הגרעין שווה לאפס אם ורק אם האלגברה היא אלגברת לי.
גרעין לייבניץ הוא תמיד אידיאל דו-צדדי.
המנה מעל אידיאל זה היא המנה המקסימלית של L שהיא אלגברת לי.
אידיאל הוא פתיר אם העלאתו בריבוע מסתיימת באפס.
האידיאל הפתיר המקסימלי הוא הרדיקל של האלגברה.
האלגברה פשוטה למחצה אם הרדיקל שווה לגרעין לייבניץ.
בממד סופי ומעל שדה סגור אלגברית ממאפיין 0, אפשר לפרק כל אלגברת לייבניץ כסכום ישר .
ההעתקה השולחת כל איבר a לפעולת הכפל משמאל ב-a היא שיכון , כאשר הוא המרכז השמאלי, ו- היא אלגברת לי של הנגזרות.
אם L אלגברת לי ו-M מודול שמאלי מעליה, אז האלגברה שהפעולה בה מוגדרת לפי היא אלגברת לייבניץ שמאלית, הנקראת מכפלה ישרה-לרביע (hemi-semidirect product) של L ו-M.
אלגוריתם ID3 הוא אלגוריתם חמדן שמייצר עץ החלטה מקבוצת דוגמאות נתונה.
האלגוריתם פותח על ידי המתמטיקאי רוס קווינלן (Ross Quinlan).
האלגוריתם משמש בלמידת מכונה ובעיבוד שפות טבעיות.
אלגוריתם ID3 מתחיל עם קבוצת הדוגמאות המקורית , ומגדיר אותה להיות שורש העץ.
בכל איטרציה של האלגוריתם, הוא מסתכל על עלה של העץ הנוכחי, שמייצג קבוצת דוגמאות .
האלגוריתם עובר על כל הפיצ'רים של הקבוצה שאינם בשימוש, ומחשב את האנטרופיה של פיצ'ר זה או רווח המידע שלו, כלומר המידה בה השימוש בפיצ'ר יקטין את האנטרופיה.
לאחר מכן האלגוריתם בוחר את הפיצ'ר בעל ערך האנטרופיה הקטן ביותר (או רווח המידע הגדול ביותר), ומחלק את קבוצה ל-2 תת-קבוצות או יותר.
בהתבסס על חלוקה זו הוא מוסיף את הבנים של הצומת שמייצג את .
לדוגמה, אם היא קבוצת אנשים, ניתן לפצל אותה לתת-קבוצות של אנשים שהגיל שלהם נמוך מ-50, בין 50 ל-100, או גבוה מ-100.
האלגוריתם ממשיך לרוץ באופן רקורסיבי על כל אחד מהעלים החדשים, תוך התחשבות רק בפיצ'רים שלא נבחרו קודם לכן.
הפיצול הרקורסיבי נפסק באחד מהמקרים הבאים:
כל הדוגמאות בעלה שייכים לאותה המחלקה.
במקרה זה הצומת הופך לעלה של העץ הסופי, ומתויג לפי המחלקה של הדוגמאות בו.
אין עוד תכונות לבחירה, אבל הדוגמאות עדיין לא שייכות לאותה המחלקה.
במקרה זה הצומת הופך לעלה של העץ הסופי ומתויג לפי המחלקה השכיחה של הדוגמאות בו.
זה קורה כאשר לא נמצאה דוגמה בקבוצת האב, אשר תואמת לערך ספציפי של התכונה שנבחרה לשמש לפיצול.
זה יכול לקרות, למשל, אם האלגוריתם פיצל קבוצת אנשים לפי מחלקות גיל, אחת המחלקות הייתה של אנשים שגילם גבוה מ-100, אך בקבוצת האב אין אנשים שגילם גבוה מ-100. במקרה זה הצומת הופך לעלה ומתויג לפי המחלקה השכיחה של הדוגמאות בצומת האב.
AdaBoost (קיצור של Adaptive Boosting – "בוסטינג אדפטיבי") הוא מטא-אלגוריתם בתחום לימוד מכונה המיועד לשיפור דיוק הסיווג על ידי שילוב של מסווגים חלשים למסווג חזק.
אלגוריתם זה פותח בשנת 1995 על ידי הישראלי יואב פרוינד ורוברט שפיר, אשר עבור עבודתם זו זכו בפרס גדל בשנת 2003.
AdaBoost עובד בשילוב עם מגוון אלגוריתמי למידה בסיסיים, ומפיק מסווג סופי באמצעות סכימה משוקללת של תוצאות "מסווגים חלשים" מרובים.
לרוב הוא מוצג עבור בעיות סיווג בינאריות, אך הוא הורחב גם לטיפול בריבוי קטגוריות ולמשימות אחרות.
השם "בוסטינג אדפטיבי" נובע מיכולתו של האלגוריתם להתאים את עצמו לשגיאות: כל מסווג חלש נוסף מתמקד במקרים שבהם המסווגים הקודמים טעו.
במקרים מסוימים, AdaBoost נמצא כפחות רגיש לבעיית התאמת יתר (overfitting) בהשוואה לאלגוריתמי למידה אחרים, אך הוא עלול להיות רגיש לנוכחות רעש וחריגות בנתונים.
למרות שבדרך כלל נעשה שימוש ב-AdaBoost לשילוב של לומדי בסיס חלשים (כגון גזעי החלטה), הוכח כי הוא משלב ביעילות גם לומדים בסיס חזקים (כגון עצי החלטה עמוקים יותר), ומייצר מודל מדויק עוד יותר.
הרעיון של Boosting (הגברה) בלמידת מכונה צמח מתוך שאלה תאורטית במסגרת מודל הלמידה PAC שהציג לסלי וליאנט ב-1988.
רוברט שפיר הציע ב-1989 אלגוריתם Boosting פולינומי ראשון שהוכיח עקרונית כי התשובה חיובית, וב-1990 הציג יואב פרוינד שיפור יעיל יותר לאלגוריתם זה.
עם זאת, הגישות המוקדמות הללו סבלו מקשיים פרקטיים, והיו מורכבות ליישום ולאימון.
בשנת 1995 פיתחו פרוינד ושפיר את AdaBoost (קיצור של "Adaptive Boosting"), אלגוריתם Boosting פשוט יחסית שהצליח להתגבר על רבות מהבעיות המעשיות של קודמיו.
האלגוריתם הוצג לראשונה בכנס COLT באותה שנה, ומאוחר יותר פורסם במאמר מקיף ב-1997.
AdaBoost היה לאחד האלגוריתמים הראשונים בתחום ה-Ensemble learning שזכה לתשומת לב רחבה בשל פשטותו, יעילותו ותוצאותיו הטובות.
תרומתם של פרוינד ושפיר זכתה כאמור להכרה בדמות פרס גדל בשנת 2003 על הישגיהם בתחום Boosting, ומהר מאוד שולב האלגוריתם במגוון רחב של יישומים בלמידת מכונה.
פשטות ושקיפות – האלגוריתם קל למימוש ומבוסס על רעיון ישיר של שיפור איטרטיבי של הביצועים.
הוא אינו דורש כוונון רב של פרמטרים (מלבד מספר הסבבים) וניתן להשתמש בו עם מגוון סוגי מסווגים חלשים לפי צורכי הבעיה.
התוצר – אוסף מסווגים עם משקלות – גם ניתן לפרשנות מסוימת; למשל, ניתן להבין אילו מאפיינים (דרך המסווגים החלשים) תרמו יותר להחלטה הסופית.
שיפור דיוק – האלגוריתם לרוב משיג דיוק גבוה יותר מאשר כל מסווג חלש בנפרד, ולעיתים אף משתווה לביצועי מסווגים מתקדמים בהרבה.
בשילוב עם עצי החלטה קטנים האלגוריתם ידוע כאחד המסווגים הטובים ביותר ללא צורך בהתאמה מרובה.
הוא מתאים את עצמו לדאטה על ידי התמקדות בדוגמאות קשות, ובכך מצמצם את הטעות הכוללת באופן יעיל.
התאמה אדפטיבית וחסינות מסוימת – היכולת להתרכז בדוגמאות שקשה לסווגן בכל שלב מקנה ל-AdaBoost יתרון בהתמודדות עם מקרים מורכבים ועם בעיות של חוסר איזון בנתונים.
דוגמאות מהמיעוט שתויגו לא נכון יקבלו משקל גבוה ויזכו להתייחסות בסבבים הבאים, וכך האלגוריתם יכול באופן אדפטיבי להתמודד גם עם מערכי נתונים לא מאוזנים שבהם אחת הקטגוריות נדירה.
עמידות מסוימת להתאמת יתר (Overfitting) – במחקרים אמפיריים נמצא של-AdaBoost נטייה מופחתת להתאמת יתר בהשוואה לאלגוריתמים חזקים אחרים, במיוחד במצבים של נתונים נקיים מרעש.
במילים אחרות, כל עוד לא קיימות שגיאות תווית רבות או חריגות קיצוניות, AdaBoost מסוגל ללמוד את הנתונים באופן הדוק מבלי להתאים את עצמו יתר על המידה.
רגישות לרעש וחריגות – אחת המגבלות הבולטות של AdaBoost היא הרגישות שלו לדוגמאות בעייתיות בנתוני האימון.
מכיוון שהאלגוריתם מגדיל בהדרגה את המשקל של דוגמאות שקשה לסווגן, דוגמאות עם תווית שגויה או נתונים חריגים (Outliers) עלולות לקבל משקל הולך וגדל ולהשפיע לרעה על המודל הסופי.
במצב של רעש כבד, AdaBoost עלול "להתאמץ" יותר מדי להתאים את עצמו לחריגים ובכך לפגוע בביצועי ההכללה.
אלגוריתמים חלופיים כמו Random Forest נחשבים חסינים יותר לרעש בהקשר זה.
צורך בלומד חלש "טוב מספיק" – AdaBoost דורש שכל מסווג חלש יהיה מעט טוב מניחוש (שגיאה נמוכה מ-50%).
במקרים שבהם הלומד החלש לא מסוגל להגיע לביצועים כאלה, האלגוריתם עלול להיכשל או לא לתרום לשיפור (למשל, אם לומד חלש מחזיר ביצועים גרועים, המשקל שלו עלול לצאת שלילי או שהאלגוריתם יעצור).
לכן AdaBoost מתאים בעיקר ללומדים חלשים בעלי יכולת אבחנה מינימלית.
במצבים של מידע דל מאוד או מאפיינים שלא נושאים אות שימושי, ייתכן ש-Boosting לא יביא לתועלת.
חישוביות וזמן ריצה – בניגוד לשיטות כמו Bagging (דוגמת יער אקראי) שבהן מודלים שונים ניתנים לאימון במקביל, ב-AdaBoost האימון הוא סדרתי (סבבים תלויים זה בזה).
משמעות הדבר היא שמשך האימון עשוי להיות ארוך, במיוחד אם נדרשים סבבים רבים או אם הלומד החלש עצמו איטי.
עבור מערכי נתונים גדולים מאוד, AdaBoost עלול להיות כבד חישובית לעומת שיטות קביצה (ensemble) מקבילות אחרות.
בנוסף, עם התקדמות האלגוריתם והוספת מסווגים, גם זמן הסיווג (בעת שימוש במודל) מתארך, שכן יש לבצע חיזוי של כל המסווגים החלשים ולשלבם.
האלגוריתם AdaBoost הוא שיטה גמישה ורב-שימושית הנמצאת במגוון יישומים בתחומי עיבוד נתונים, ראייה ממוחשבת, אבטחת מידע ועוד.
להלן מספר תחומים בולטים בהם נעשה בו שימוש:
אחד היישומים הידועים ביותר של שיטת הבוסטינג הוא במסגרת מערכת זיהוי הפנים של Viola-Jones.
אלגוריתם זה, שפותח בשנת 2001, השתמש בטכניקת למידה מגבירה כדי לבחור מאפייני תמונה פשוטים (כגון Haar features) ולשלבם לרצף של מסווגים חזקים המאורגנים במבנה מדורג (cascade), מה שאפשר זיהוי מהיר של פנים בתמונות.
המנגנון שימש הן לבחירת התכונות המבדילות ביותר והן להרכבתן למסווג סופי יעיל, ובכך אפשר זיהוי פנים בזמן אמת – פריצת דרך בתחום הראייה הממוחשבת.
מעבר לזיהוי פנים, טכניקות מבוססות הגברת מסווגים יושמו גם בזיהוי עצמים כללי, מעקב אחר אובייקטים בווידאו ושיפור איכות תמונה.
עיבוד שפה טבעית וסינון ספאם
בתחום עיבוד שפה הטבעית משלבים לעיתים Boosting במשימות סיווג טקסט.
דוגמה נפוצה היא מסנני דואר זבל, שבהם האלגוריתם מאומן על מאפייני טקסט כגון מילות מפתח, תדירויות ושדות מטא-דאטה של ההודעה כדי להבחין בין דואר לגיטימי לספאם.
שילוב של רבים מהמאפיינים הללו באמצעות שיטת ההגברה משפר את יכולת הזיהוי של ספאם בהשוואה לכל כלל בודד.
גם במשימות כמו ניתוח סנטימנט (קביעת עמדה חיובית/שלילית מטקסט) נעשה שימוש באלגוריתם ככלי המשלב מאות חלוקות פשוטות (למשל נוכחות מילים מסוימות) לכדי מסווג סופי חזק.
היכולת של שיטת ההגברה האדפטיבית להתאים את עצמה לדוגמאות קשות לסיווג (כגון ביטויים אירוניים או נדירים) מועילה במיוחד בתחומים אלו.
בתחום אבטחת המידע והפיננסים האלגוריתם מיושם במערכות זיהוי הונאות וזיהוי אנומליות.
למשל, בזיהוי הונאות בכרטיסי אשראי פותחו מערכות המשלבות מספר מסווגים חלשים (הבוחנים דפוסי רכישה, מיקום, סכומים וכדומה) כדי לאתר עסקאות חשודות.
שיטת ההעצמה מתאימה במיוחד למשימה זו, משום שהיא יכולה להגביר את הרגישות למקרים חריגים (כגון עסקאות הונאה נדירות) תוך שמירה על שיעור התרעות שווא נמוך.
באופן דומה, גם בזיהוי פריצות לרשת או תנועה זדונית (Intrusion Detection) נעשה שימוש באלגוריתמים מבוססי למידת חיזוק, בהם המערכת לומדת דפוסי תעבורה תקינים ברשת ומזהה סטיות מהם המעידות על פעילות זדונית.
שילוב של גלאים חלשים שונים (כגון בדיקת כתובות IP, חריגות בפרוטוקול ורצפי פקודות חשודים) באמצעות שיטת הבוסטינג מאפשר לקבל מנגנון איתור רב-שכבתי בעל דיוק גבוה.
גם בתחום הרפואי נעשה שימוש נרחב באלגוריתם למשל במערכות אבחון רפואי מבוססות למידת מכונה.
במחקרים שונים יושמה הטכניקה לשילוב מספר בדיקות או סימפטומים פשוטים (כל אחד בעל כוח ניבוי חלש) לכדי החלטה אינטגרטיבית לגבי נוכחות מחלה או סיכון רפואי.
לדוגמה, בניתוח צילומי רנטגן או MRI לזיהוי נגעים, שיטת הלמידה מסוגלת לשלב מאפייני תמונה רבים כדי לזהות ממצאים חריגים בצורה מדויקת יותר.
דוגמה נוספת היא חיזוי התפרצות מחלות באמצעות שילוב של מדדים קליניים, תוצאות מעבדה וסימנים חיוניים – כל אחד מהם בפני עצמו אינו מספיק, אך שילובם באמצעות מודל ההעצמה מספק חיזוי אמין.