یادگیری تقویت معکوس در مقیاس جهانی در Google Maps – وبلاگ تحقیق گوگل

ارسال شده توسط مت بارنز، مهندس نرم افزار، تحقیقات گوگل

مسیریابی در Google Maps یکی از مفیدترین و پرکاربردترین ویژگی های ما است. تعیین بهترین مسیر از A تا B مستلزم ایجاد مبادلات پیچیده بین عواملی از جمله زمان تخمینی رسیدن (ETA)، عوارض، مستقیم بودن، شرایط سطح (مانند جاده‌های آسفالت‌شده، آسفالت‌نشده)، و ترجیحات کاربر است که در حالت حمل‌ونقل متفاوت است. و جغرافیای محلی اغلب، طبیعی ترین دیدی که ما به ترجیحات مسافران داریم، با تجزیه و تحلیل الگوهای سفر در دنیای واقعی است.

ترجیحات یادگیری از رفتار تصمیم گیری متوالی مشاهده شده یک کاربرد کلاسیک از یادگیری تقویتی معکوس (IRL) است. با توجه به فرآیند تصمیم مارکوف (MDP) – رسمی کردن شبکه جاده – و مجموعه ای از مسیرهای نمایشی (مسیرهای طی شده)، هدف IRL بازیابی عملکرد پاداش پنهان کاربران است. اگرچه تحقیقات گذشته راه‌حل‌های کلی IRL را به‌طور فزاینده‌ای ایجاد کرده است، اما این راه‌حل‌ها با موفقیت به MDP‌های جهانی مقیاس‌بندی نشده‌اند. مقیاس‌بندی الگوریتم‌های IRL چالش‌برانگیز است زیرا معمولاً به حل یک زیر روال RL نیاز دارند. در هر مرحله به روز رسانی. در نگاه اول، حتی تلاش برای جا دادن یک MDP در مقیاس جهانی در حافظه برای محاسبه یک مرحله گرادیان، به دلیل تعداد زیاد بخش‌های جاده و محدودیت حافظه با پهنای باند بالا، غیرممکن به نظر می‌رسد. هنگام اعمال IRL برای مسیریابی، باید تمام مسیرهای معقول بین مبدا و مقصد هر نمایش را در نظر گرفت. این نشان می دهد که هر تلاشی برای شکستن MDP در مقیاس جهانی به اجزای کوچکتر نمی تواند اجزایی کوچکتر از یک منطقه شهری را در نظر بگیرد.

برای این منظور، در “آموزش تقویت معکوس مقیاس پذیر گسترده در Google Maps”، ما نتیجه یک همکاری چند ساله بین Google Research، Maps و Google DeepMind را برای غلبه بر این محدودیت مقیاس پذیری IRL به اشتراک می گذاریم. ما الگوریتم‌های کلاسیک را در این فضا بازبینی می‌کنیم و پیشرفت‌هایی را در فشرده‌سازی و موازی‌سازی نمودار، همراه با یک الگوریتم جدید IRL به نام برنامه‌ریزی معکوس افق عقب‌نشینی (RHIP) معرفی می‌کنیم که کنترل دقیقی را بر مبادلات عملکرد ارائه می‌دهد. خط‌مشی نهایی RHIP به بهبود نسبی 16 تا 24 درصدی در نرخ تطابق مسیر جهانی دست می‌یابد، یعنی درصد مسیرهای پیموده‌شده شناسایی‌نشده که دقیقاً با مسیر پیشنهادی در Google Maps مطابقت دارند. تا آنجا که ما می دانیم، این بزرگترین نمونه IRL در یک محیط واقعی تا به امروز است.

هنگام استفاده از خط مشی یادگیری تقویت معکوس RHIP، در نرخ تطابق مسیر نسبت به خط پایه موجود، بهبود نقشه های گوگل.

مزایای IRL

یک جزئیات ظریف اما حیاتی در مورد مشکل مسیریابی این است که همینطور است هدف مشروط، به این معنی که هر حالت مقصد یک MDP کمی متفاوت را القا می کند (به طور خاص، مقصد یک حالت پایانی و پاداش صفر است). رویکردهای IRL برای این نوع مشکلات مناسب هستند زیرا تابع پاداش آموخته شده در سراسر MDP ها منتقل می شود و فقط حالت مقصد اصلاح می شود. این برخلاف رویکردهایی است که مستقیماً یک خط مشی را یاد می گیرند، که معمولاً به یک عامل اضافی نیاز دارند اس پارامترها، جایی که اس تعداد ایالت های MDP است.

هنگامی که تابع پاداش از طریق IRL یاد گرفتیم، از یک ترفند قدرتمند زمان استنتاج استفاده می کنیم. ابتدا، پاداش کل نمودار را یک بار در یک تنظیم دسته ای آفلاین ارزیابی می کنیم. این محاسبات به طور کامل بر روی سرورها بدون دسترسی به سفرهای فردی انجام می‌شود و فقط بر روی دسته‌هایی از بخش‌های جاده در نمودار عمل می‌کند. سپس، نتایج را در یک پایگاه داده در حافظه ذخیره می‌کنیم و از یک الگوریتم جستجوی سریع نمودار آنلاین برای یافتن بالاترین مسیر پاداش برای درخواست‌های مسیریابی بین هر مبدأ و مقصدی استفاده می‌کنیم. این امر نیاز به انجام استنتاج آنلاین یک مدل یا خط مشی عمیقاً پارامتری شده را دور می زند و هزینه های سرویس و تأخیر را به شدت بهبود می بخشد.

استقرار مدل پاداش با استفاده از استنتاج دسته ای و برنامه ریزان آنلاین سریع.

برنامه ریزی معکوس افق عقب نشینی

برای مقیاس‌بندی IRL به MDP جهانی، نمودار را فشرده می‌کنیم و MDP جهانی را با استفاده از ترکیبی از متخصصان (MoE) بر اساس مناطق جغرافیایی خرد می‌کنیم. سپس الگوریتم‌های کلاسیک IRL را برای حل MDP‌های محلی، تخمین ضرر و ارسال گرادیان‌ها به MOE اعمال می‌کنیم. نمودار پاداش در سراسر جهان با فشرده سازی مدل نهایی پاداش MoE محاسبه می شود. برای ارائه کنترل بیشتر بر ویژگی‌های عملکرد، یک الگوریتم تعمیم‌یافته IRL به نام برنامه‌ریزی معکوس افق عقب‌نشینی (RHIP) را معرفی می‌کنیم.

آموزش مدل پاداش IRL با استفاده از موازی سازی MoE، فشرده سازی نمودار و RHIP.

RHIP از تمایل مردم به انجام برنامه ریزی محلی گسترده (“من برای یک ساعت آینده چه کار می کنم؟”) و برنامه ریزی تقریبی بلند مدت (“زندگی من در 5 سال آینده چگونه خواهد بود؟” الهام گرفته شده است. برای استفاده از این بینش، RHIP از سیاست‌های تصادفی قوی و در عین حال پرهزینه در منطقه محلی اطراف مسیر نمایش استفاده می‌کند و به برنامه‌ریزان قطعی ارزان‌تر فراتر از برخی افق‌ها روی می‌آورد. تنظیم افق اچ اجازه می دهد تا هزینه های محاسباتی را کنترل کنید، و اغلب امکان کشف نقطه شیرین عملکرد را فراهم می کند. جالب اینجاست که RHIP بسیاری از الگوریتم‌های کلاسیک IRL را تعمیم می‌دهد و بینش جدیدی ارائه می‌دهد که می‌توان آنها را در امتداد یک طیف تصادفی در مقابل قطعی مشاهده کرد (به ویژه برای اچ=∞ به MaxEnt کاهش می یابد، برای اچ=1 به BIRL و برای کاهش می یابد اچ= 0 به MMP کاهش می یابد).

با توجه به تظاهرات از so به سد، (1) RHIP از یک سیاست تصادفی قوی و در عین حال پرهزینه در منطقه محلی اطراف نمایش پیروی می کند (منطقه آبی). (2) فراتر از افق H، RHIP به دنبال یک برنامه ریز قطعی ارزان تر می رود (خطوط قرمز). تنظیم افق کنترل دقیق بر عملکرد و هزینه های محاسباتی را امکان پذیر می کند.

مسیریابی برنده است

خط مشی RHIP به ترتیب 15.9% و 24.1% افزایش نرخ تطابق مسیر جهانی را برای رانندگی و دو چرخ (مانند اسکوتر، موتورسیکلت، موتور سیکلت) نسبت به خط مبنا به خوبی تنظیم شده Maps فراهم می کند. ما به خصوص در مورد مزایای حالت های حمل و نقل پایدارتر هیجان زده هستیم، جایی که عوامل فراتر از زمان سفر نقش مهمی دارند. با تنظیم افق RHIP اچ، می‌توانیم به خط‌مشی دست یابیم که هم دقیق‌تر از سایر خط‌مشی‌های IRL باشد و هم ۷۰٪ سریع‌تر از MaxEnt.

مدل پاداش پارامتر 360 میلیونی ما در آزمایش‌های A/B زنده، برنده‌های بصری را برای کاربران Google Maps فراهم می‌کند. بررسی بخش‌های جاده با تفاوت مطلق بزرگ بین پاداش‌های آموخته‌شده و پاداش‌های پایه می‌تواند به بهبود مسیرهای Google Maps کمک کند. مثلا:

ناتینگهام، انگلستان مسیر ترجیحی (آبی) قبلاً به دلیل وجود یک دروازه بزرگ به عنوان دارایی خصوصی علامت گذاری شده بود، که به سیستم های ما نشان می داد که جاده ممکن است گاهی بسته باشد و برای رانندگان ایده آل نباشد. در نتیجه، Google Maps رانندگان را از یک مسیر انحرافی طولانی‌تر و جایگزین هدایت کرد (قرمز). با این حال، از آنجایی که الگوهای رانندگی در دنیای واقعی نشان می‌دهند که کاربران به طور منظم مسیر مورد نظر را بدون مشکل طی می‌کنند (زیرا دروازه تقریباً هرگز بسته نمی‌شود)، اکنون IRL می‌آموزد که رانندگان را در مسیر دلخواه با قرار دادن یک پاداش مثبت بزرگ در این بخش جاده هدایت کند.

نتیجه

ثابت شده است که افزایش عملکرد از طریق افزایش مقیاس – هم از نظر اندازه مجموعه داده و هم از نظر پیچیدگی مدل – یک روند مداوم در یادگیری ماشین است. دستاوردهای مشابه برای مشکلات یادگیری تقویت معکوس از لحاظ تاریخی، عمدتاً به دلیل چالش‌های مربوط به مدیریت MDPهای با اندازه عملی، مبهم باقی مانده است. با معرفی پیشرفت‌های مقیاس‌پذیری به الگوریتم‌های کلاسیک IRL، اکنون می‌توانیم مدل‌های پاداش را در مورد مشکلات با صدها میلیون حالت، مسیرهای نمایشی و پارامترهای مدل به ترتیب آموزش دهیم. تا آنجا که ما می دانیم، این بزرگترین نمونه IRL در یک محیط واقعی تا به امروز است. برای آشنایی بیشتر با این اثر به مقاله مراجعه کنید.

سپاسگزاریها

این کار یک همکاری بین چندین تیم در Google است. از مشارکت کنندگان این پروژه می توان به متیو ابوگ، الیور لانگ، مت دیدز، جیسون تریدر، دنالی مولیتور، مارکوس ولفمایر، شاون اوبانیون، رایان اپ، رناد هارترت، روی سانگ، توماس شارپ، رمی رابرت، زولتان سگو، بت لوان، بریت اشاره کرد. Larabee و Agnieszka Madurska.

ما همچنین می‌خواهیم از آرنو ایگن ویلیگ، جیکوب مورمن، جاناتان اسپنسر، رمی مونوس، مایکل بلوش و آرون آهوجا برای بحث‌ها و پیشنهادات ارزشمند تشکر کنیم.