پیش‌بینی ترافیک با روشهای پیشرفته شبکه عصبی گرافی در گوگل

گوگل دیپ‌مایند توانسته است مزایای هوش‌مصنوعی را به لطفا شبکه های عصبی گرافی به میلیاردها نفر در سراسر جهان ارائه دهد. کاربرد مهمی که در این پست به آن پرداخته خواهد شد گوگل مپ و استفاده گراف در حل چالش تخمین زمان رسیدن کاربران به مقصد است!

مساله ی گوگل مپ

مردم برای پیش‌بینی دقیق ترافیک و زمان رسیدن به مقصد (مساله ی ETA یا estimated times of arrival) به گوگل مپ اعتماد می‌کنند. تخمین زمان نقشه ها نظیر گوگل مپ ابزاری حیاتی  است. برای مثال وقتی که میخواهید به دوستان و خانواده اطلاع دهید که کی می‌رسید، یا مثلا میخواهید زمان راه افتادن را برای حضور در یک جلسه مهم تنظیم کنید، یا انتخاب مسیر به دور از ترافیک که شما را زودتر به مقصد میرساند!

این کاربرد برای کسب و کارهایی همچون شرکت‌هایی نظیر تپسی و اسنپ و …نیز مفید هستند چرا که اساس قیت گذاری را تشکیل میدهند.

محققان دیپ‌مایند با تیم گوگل مپ در شهرهایی همچون برلین، جاکارتا، سائوپائولو، سیدنی، توکیو و واشینگتن دی‌سی همکاری کرده‌اند تا با استفاده از روش‌های پیشرفته یادگیری ماشین از جمله شبکه‌های عصبی گرافی (Graph Neural Networks)، دقت ETA به صورت بلادرنگ تا ۵۰ درصد افزایش یابد، همانطور که در نمودار زیر نشان داده شده است:

گوگل مپ چگونه زمان رسیدن به مقصد را تخمین میزند؟

برای محاسبه زمان رسیدن به مقصد(ETA)، گوگل مپ از داده‌های ترافیک زنده برای بخش‌های جاده در سراسر جهان استفاده می‌کند. این داده‌ها، تصویر دقیقی از ترافیک فعلی را به گوگل مپ ارائه می‌دهد، اما ترافیکی که راننده ممکن است در ۱۰، ۲۰ یا حتی ۵۰ دقیقه دیگر از آن باشد در نظر گرفته نمی‌شود. برای پیش‌بینی دقیق ترافیک در آینده، گوگل مپ با استفاده از یادگیری ماشین، شرایط ترافیک زنده را با الگوهای ترافیک قدیمی برای جاده‌های سراسر جهان ترکیب می‌کند. این فرآیند به دلیل عواملی همچون تغییرات زمانی در ساعت شلوغی وجود دارد که می‌تواند از یک روز به روز دیگر و یا از یک ماه به ماه دیگر تفاوت داشته باشد (مثلا ترافیک اوایل هفته با اواخر هفته یا اسفند با فروردین قابل مقایسه نیست!). همچنین عواملی مانند کیفیت جاده، سرعت مجاز، تصادفات و بسته شدن جاده‌ها نیز می‌توانند به پیچیدگی این مدل پیش‌بینی اضافه شوند.

دیپ‌مایند با همکاری گوگل مپ، به بهبود دقت زمان رسیدن به مقصد در سراسر جهان کمک کرد. در حالی که دقت پیش‌بینی زمان رسیدن به مقصد در گوگل مپ برای بیش از ۹۷٪ از سفرها به صورت دقیق بوده است، با همکاری دیپ مایند و روش شبکه های عصبی گرافی دقت افزایش یافته است (گاهی اوقات به بیش از ۵۰٪ در شهرهایی مانند تایچونگ.).

برای انجام این کار به طور جهانی، از یک معماری یادگیری ماشین عمومی به نام شبکه‌های عصبی گرافی استفاده شده که به گوگل امکان استدلال فضایی-زمانی را با در نظر گرفتن حساسیت‌های یادگیری ارائه می‌دهد تا ساختار اتصال شبکه‌های جاده‌ای واقعی دنیا را مدل کنند. در ادامه نحوه کار آن را توضیح خواهیم داد:

تقسیم بندی مسیر و جاده های جهان به Supersegmentها

شبکه‌های جاده‌ای به “ابر بخش‌ها” یا “Supersegmentها” تقسیم شده‌اند. مبنای اصلی این بخش ها حجم ترافیک هر بخش از جاده بوده است. در حال حاضر، سیستم پیش‌بینی ترافیک Google Maps از دو مؤلفه زیر تشکیل شده است: (1) یک تحلیلگر مسیر که حجم اطلاعات ترافیکی بسیار زیادیرا  پردازش می‌کند تا ابر بخش‌ها را ایجاد کند و (2) یک مدل شبکه عصبی گرافی که با هدف‌های چندگانه بهینه شده است و زمان سفر را برای هر ابر بخش پیش‌بینی می‌کند.

در مسیر معماری‌های جدید یادگیری ماشین برای پیش‌بینی ترافیک

بزرگترین چالشی که هنگام ایجاد یک سیستم یادگیری ماشین برای تخمین زمان سفر با استفاده از Supersegmentها باید حل شود، یک چالش معماری است. چگونه نمونه هایی با اندازه پویا از بخش های متصل را با دقت دلخواه به گونه ای نشان دهیم که یک مدل واحد بتواند به موفقیت برسد؟

ایده‌ی اولیه برای حل این مساله با رویکردی ساده شروع شد که از سیستم ترافیک موجود به حد امکان استفاده کرد. هر Supersegment یک مجموعه از بخش‌های جاده را پوشش می‌دهد، جایی که هر بخش دارای طولی خاص و ویژگی سرعت مربوطه است. در ابتدا، یک مدل شبکه عصبی کاملاً متصل یا Fully conected برای هر Supersegment آموزش داده شد. این نتایج اولیه واعظانه بودند و نشان دادند که استفاده از شبکه‌های عصبی برای پیش‌بینی زمان سفر، پتانسیل خوبی دارند. با این حال، به دلیل اندازه پویای Supersegmentها، برای هر یک از آن‌ها باید یک مدل شبکه عصبی جداگانه آموزش داده شود. برای پیاده‌سازی این در مقیاس بزرگ، میلیون‌ها از این مدل‌ها را باید آموزش داد که با چالش پایه‌ای ساختار زیرساخت مواجه خواهد شد که قطعا منطقی نیست!

این موضوع باعث شد تا گوگلی ها به دنبال مدل‌هایی با قابلیت کنترل توالی‌های با اندازه متغیر، مانند شبکه‌های عصبی بازگشتی(RNN)، بگردند! در نهایت با در نظر گرفتن تمام چالشها تصمیم گرفتند از شبکه‌های عصبی گرافی استفاده کنند. در مدل سازی ترافیک، ما به این موضوع علاقه‌مند هستیم که چگونه خودروها از طریق یک شبکه از جاده‌ها جریان پیدا می‌کنند و شبکه‌های عصبی گراف می‌توانند دینامیک شبکه و انتشار اطلاعات را به خوبی مدل کنند.

مدل ارائه شده شبکه جاده‌ای محلی را به عنوان یک گراف تلقی می‌کند، به طوری که هر بخش مسیر جاده با یک گره در گراف مطابقت دارد و بین بخش‌های متوالی روی همان جاده یا از طریق یک تقاطع یالهای این گراف ایجاد می‌شود. در یک شبکه عصبی گراف، الگوریتم message passing اجرا می‌شود که در آن پیام‌ها و تأثیر آنها بر روی حالت‌های لبه و گره توسط شبکه‌های عصبی یادگیری می‌شوند. از این نظر، Supersegmentها زیرگراف‌های جاده هستند که به نسبت چگالی ترافیک به صورت تصادفی نمونه‌برداری شده‌اند. به عبارت دیگر، می‌توان با استفاده از این زیرگراف‌های نمونه‌برداری شده یک مدل واحد را آموزش داد و در مقیاس بزرگ استفاده کرد.

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

در یک شبکه عصبی گرافی، گره‌های مجاور پیام‌ها را به یکدیگر منتقل می‌کنند. با حفظ این ساختار، یک محدودکننده محلی برای گره‌ها اعمال می‌شود که باعث می‌شود گره‌ها به سادگی بتوانند به گره‌های مجاورشان اعتماد کنند (که تنها یک مرحله message passing را نیاز دارد). این مکانیسم‌ها به شبکه‌های عصبی گرافی اجازه می‌دهند تا از ساختار ارتباطات در شبکه جاده به شکل بهتری استفاده کنند. آزمایشات نشان داده که با اضافه کردن جاده‌های مجاوری که قسمتی از جاده اصلی نیستند، مدل توانایی پیش‌بینی بیشتری خواهد داشت. به عنوان مثال، فکر کنید که چگونه شلوغی در یک کوچه می‌تواند بر روی ترافیک در یک جاده بزرگتر متنهی به آن کوچه تاثیر بگذارد. با در نظر گرفتن چندین تقاطع توسط این شبکه عصبی، این مدل توانایی پیش‌بینی تاخیر در پیچ‌ها، تاخیرهای ناشی از ادغام و زمان کلی پیمایش در ترافیک توقف و حرکت را به دست می‌آورد. قابلیت شبکه‌های عصبی گرافی برای تعمیم در فضاهای ترکیبی، دلیل قدرت روش این مدلسازی است. هر Supersegment که ممکن است طول و پیچیدگی مختلفی داشته باشد(از مسیرهای دو گره ای ساده تا مسیرهای بلند و طولانی حاوی صدها گره) با این حال می‌تواند توسط همان مدل شبکه عصبی گرافی که قبلا آموزش دیده پردازش شود.

از تحقیق پایه تا مدل‌های یادگیری ماشینی آماده استفاده در صنعت

ساختن مدل هایی با توانایی عمومی‌سازی بیشتر از طریق استفاده از توابع خطا سفارشی شده

در حالی که هدف نهایی سیستم مدلسازی مققان دیپ مایند کاهش خطاها در تخمینات سفر بوده، مشاهده شده که استفاده از ترکیب خطاهای چندگانه (با وزن مناسب) توانایی مدل برای عمومی‌سازی را به طرز چشمگیری افزایش می‌دهد. به طور خاص، یک هدف چند خطایی با استفاده از یک عامل منظم‌کننده بر روی وزن های مدل، خطاهای L_2 و L_1 برای زمان‌های عبور جهانی، همچنین خطاهای فردی Huber و منفی-لاگاریتمی (NLL) برای هر گره در گراف تعریف شده است. با ترکیب این خطاها، مدل قابل هدایت شده است و از بیش­برازش روی داده­های آموزشی جلوگیری شده است. در حالی که اندازه‌گیری‌های کیفیت در دوره آموزش تغییر نکرد، بهبودهای مشاهده شده در دوره آموزش روی مجموعه‌های آزمون و آزمایشات پایان به پایان منجر شد.

در حال حاضر، بررسی در جریان است که آیا تکنیک MetaGradient نیز می‌تواند برای تغییر ترکیب خطای چندگانه در دوره آموزش به کار گرفته شود؛ با استفاده از کاهش خطاهای تخمین سفر به عنوان معیار هدایت. این کار، تحت الهام از تلاش‌های MetaGradient در یادگیری تقویتی صورت گرفته و آزمایشات اولیه نشان‌دهنده نتایج قابل اطمینانی هستند.

منبع این مقاله پست Traffic prediction with advanced Graph Neural Networks از بلاگ deepmind است.

https://www.deepmind.com/blog/traffic-prediction-with-advanced-graph-neural-networks