טריק החציון

טריק החציון (באנגלית: Median Trick) הוא טכניקה נפוצה לשיפור סיכויי ההצלחה של אלגוריתמים אקראיים. הוא התפתח בשנות ה-80 וה-90, כחלק מהתפשטות השימוש בסטטיסטיקה חישובית, אופטימיזציה ולמידת מכונה.
הרעיון המרכזי הוא להריץ את האלגוריתם האקראי מספר פעמים באופן בלתי תלוי ולקחת את החציון של התוצאות במטרה לצמצם את הסיכוי לשגיאה גדולה, שיכולה לקרות בהרצה בודדת של אלגוריתם מסוג זה. נכונות השיטה היא מסקנה בתורת ההסתברות.

שיטה זו נפוצה בתחומים כמו חישוב מבוזר ולמידת מכונה כאשר יש צורך לקבל תוצאה מדויקת ככל הניתן מתוך מאגרי נתונים רועשים או גדולים.

 ניסוח פורמלי 
נניח כי נתון אלגוריתם מקרי המחזיר תוצאה מספרית  בניסיון לשערך את תוצאת האמת ומתקיים:

, כאשר  קבוע כלשהו.

במילים אחרות, האלגוריתם צודק עד כדי  בהסתברות לפחות .

אז עבור  הרצות, המייצרות את המשערכים 

ועבור  מתקיים:

, כאשר  הוא החציון של כל המשערכים.

כלומר בבחירת החציון של המשערכים הסיכוי לקבל תוצאה קרובה ל- עד כדי  גדל ביחס אקספוננציאלי לכמות ההרצות ().

ניתן גם להראות שכדי להבטיח תוצאה קרובה עד כדי  בהסתברות גבוהה מ- נדרש להריץ את האלגוריתם  פעמים.
כלומר, ניתן לקבוע את כמות ההרצות על מנת לעמוד בדרישה למידת הוודאות.

 הוכחה 
נסמן ב- את המשתנה המקרי שמציין האם האלגוריתם טועה בהרצה ה-,
כלומר  אם ורק אם .

על מנת שהחציון יטעה ביותר מ-, נדרש שלפחות מחצית מההרצות יחזירו ערך עם שגיאה גבוהה מ- ()
ובסך הכל יתקיים: .

הסיכוי לכך יורד אקספוננציאלית ביחס ל-, על פי הנוסחה מהניסוח הפורמלי, ניתן להראות זאת באמצעות מספר אי-שוויונות, שמקורם באותה המשפחה, כגון אי-שוויון צ'רנוף ואי-שוויון הופדינג.

 שימושים 
טריק החציון מופיע בתור כלי סטנדרטי לשיפור מספר רב של אלגוריתמים כדוגמת:

 אלגוריתמים אקראיים – להפחתת הסתברות לטעות, על ידי הרצת האלגוריתם מספר פעמים ולקיחת החציון של התוצאות.

 חישוב מבוזר – לשילוב תוצאות ממספר רכיבים או מחשבים, תוך צמצום השפעת ערכים קיצוניים, מה שעלול להזיק במידה ומשתמשים בממוצע של התוצאות.
 למידת מכונה – לדוגמה באלגוריתמים של רגרסיה וסיווג, כדי לשפר דיוק ולמנוע השפעה של דגימות בעייתיות, במיוחד במצבים של רעש בנתונים או דגימה לא יציבה.
 הערות שוליים 

קטגוריה:אלגוריתמים