علی یک علاقمند به فیزیک است و دوست دارد در حوزه های متفاوتی از فیزیک اطلاعاتی بدست آورد. او به سراغ نظریه ریسمان رفته است (string theory) اما به خاطر سرچ اشتباه درگیر یک سوال در علوم کامپیوتر شده است. از آنجا که او مُصِر است جواب را بداند از شما می‌خواهد در حل این سوال به او کمک کنید.

سوال از این قرار است که شما باید برنامه بنویسید که بتوانند رشته ای(string) را در جمله ای دیگر بیابد.

ورودی🔗

ورودی شامل دو خط است که در خط اول رشته مورد نظر در خط دوم جمله می‌آید.

خروجی🔗

خروجی برنامه‌ی شما باید شامل یک عدد باشد. اگر رشته درون جمله بود عدد یک را چاپ کند در غیر این صورت عدد صفر را چاپ کند.

مثال🔗

ورودی نمونه ۱🔗

string 
string theory is a theoretical framework in particle physics

خروجی نمونه ۱🔗

1

ورودی نمونه ۲🔗

framework 
In cs, a string is traditionally a sequence of characters

خروجی نمونه ۱🔗

0

علی همیشه در آرزوی یافتن راهی برای ارتباط برقرار کردن بین جهان‌های موازی است.او این جهان‌ها را به صورت بردار‌های ۳۰۰ بعدی مدل کرده است. یعنی هر آیتم در یک جهان یک بردار ۳۰۰ بعدی است. بنابراین با زیر هم قرار دادن آیتم‌های یک جهان یک ماتریس n*۳۰۰ تولید می‌شود که توصیف جهان است.

علی توصیف‌های دو جهان را در قالب دو فایل X_train.npy و Y_train.npy را در اختیار دارد.او سعی دارد تا ماتریس انتقالی پیدا کند(برای رفتن از جهان X به جهان Y) که با ضرب جهان اول در ماتریس انتقال به جهان دوم منتقل شود. $XR \approx Y$ علی برای آنکه بتواند ماتریس R را بیابد از توان دوم نرم Frobenius ارور استفاده می‌کند. او قصد دارد با استفاده از الگوریتم Gradient Descent مقدار بهینه این تابع را بیابد. $J ={\frac {1}{n}} ||\mathbf{Y-XR}||_{F}^2$ نرم Frobenius به صورت زیر تعریف می‌شود: $||\mathbf{A}|| _{F} \equiv \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij} |^{2} }$

شما باید به علی کمک کنید. فایل submit.py شامل دو تابع است. تنها کتابخانه مورد استفاده در این پروژه numpy هست. در تابع train_transformation شما ماتریس فضای اول و فضای دوم (X_train , Y_train) و مقدار اولیه برای ماتریس R را دریافت خواهید کرد. همچنین عددی به عنوان تعداد قدم‌های الگوریتم Gradient Dscent و مقدار learning rate به تابع شما پاس داده می‌شود. هدف این تابع آن است تا الگوریتم GD را برای مینیمم کردن J پیاده کنید. دقت کنید حتما از پارامتر‌های train_steps , learning_rate در پیاده سازی خود استفاده کنید. استفاده از هیچ تابع از پیش تعریف شده هم مجاز نیست. مدیر علی در این باره بسیار جدی است!

بعد از پیدا کردن نتیجه برای یک بردار در فضای جدید، شما باید نزدیک ‌ترین بردار به بردار پیدا شده در فضای جدید را بیابید(طبیعتا ماتریس انتقال ما یک ماتریس تقریبست!). در تابع nearest_neighbor شما یک بردار از فضای X با عنوان متغیر ‌v و همه‌ی بردارهای موجود در فضای Y(جهان هدف) را دریافت می‌کنید.همچنین پارامتر k بیان می‌کند که چه تعداد نزدیک‌ترین بردارها در فضای ِY به بردار v بازگردانده شود. هدف آن است شما یک cosine similarity در این تابع پیدا کنید. در نهایت این تابع ایندکس k بردار نزدیک به v از فضای برداری Y را به شما بازمی‌گرداند.(بردار v با همه‌ی بردارهای فضای Y مقایسه می‌شود)

امتیاز نهایی شما به صورت زیر محاسبه می‌شود: $score = 9.09*accuracy-4.082$

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

در نهایت فایل submit.py را ارسال کنید. لینک فایل پروژه را از [اینجا]( این لینک ) دانلود کنید.

• محدودیت زمان: ندارد
• محدودیت حافظه: ندارد

داده‌های این سوال را می‌توانید از [اینجا]( این لینک ) دریافت کنید.

علی پس از استخدام در شرکت بزرگ و معروف "هرمینا بلدان شریف" متوجه شده که تعداد بسیار زیادی ایمیل هرز دریافت می‌کند. به همین دلیل تصمیم گرفته تا سامانه‌ای برای تشخیص ایمیل‌‌های هرز (spam) طراحی بکند. او با جمع‌آوری تمام ایمیل‌هایی که اخیرا دریافت کرده مجموعه داده‌ای با نام ‌train.csv ایجاد کرده. این مجموعه داده دارای دو ستون Text و Class می‌باشد که ستون اول متن ایمیل و ستون دوم کلاس مربوط به آن ایمیل است. کلاس $0$ نشانگر این است که ایمیل مربوطه اسپم نیست و مقدار $1$ نشانگر این است که ایمیل مربوطه اسپم است.

با استفاده از این داده‌ها مدلی طراحی کنید که بتواند ایمیل‌های اسپم را از غیراسپم تشخیص بدهد. پس از آموزش مدل خود بر روی داده‌های آموزش،‌ پیش‌بینی‌های مدل خود بر روی داده تست را در فایلی با نام submission.csv ارسال کنید. این فایل باید دارای یک ستون باشد که ردیف $i$ ام آن پیش‌بینی شما برای ردیف $i$ ام از داده تست می‌باشد (دقت کنید که ستون مورد نظر باید حتما دارای header باشد). پیش‌بینی های شما باید به صورت احتمالاتی و بین صفر و یک باشند. برای ارزیابی مدل شما از سطح زیر ناحیه نمودار ROC استفاده می‌شود. درمورد این نمودار می‌توانید اینجا بیشتر مطالعه کنید.

• محدودیت زمان: ندارد
• محدودیت حافظه: ندارد

داده‌های این سوال را می‌توانید از [اینجا]( این لینک ) دریافت کنید.

علی به سرزمین داده‌ها وارد شده است! در این سرزمین انواع مختلفی از داده‌ها وجود دارد. اکنون انتهای سال داده‌ای است و داده‌ها باید خانه‌های خود را تمیز بکنند. داده‌ها برای انجام داده‌تکانی و تکمیل یک ماموریت مهم از علی کمک خواسته‌اند منتها علی در آخرین سفر خود در یکی از جهان‌های موازی زمین‌گیر شده و نیاز به کمک شما دارد تا این ماموریت مهم را برای او انجام دهید!

داده‌های سرزمین داده‌ها به صورت یک فایل train.csv در اختیار شما قرار می‌گیرند. ماموریت شما این است که پس از آماده‌سازی این داده‌ها برای آموزش،‌ با استفاده از آن‌ها ستون ‌target را در این مجموعه داده پیش‌بینی بکنید. دقت کنید که تمامی ویژگی‌های این مجموعه داده به صورت دسته‌ای هستند،‌ یعنی مقادیر آن‌ها عضوی از یک مجموعه متناهی‌اند (به عنوان مثال اگر مجموعه داده‌ای تک‌ستونی را از سطح تحصیلات افراد یک جامعه نمونه جمع‌آوری کنیم، داده‌ای دسته‌ای داریم که در آن هر ورودی می‌تواند عضوی از مجموعه {زیر دیپلم،‌ دیپلم،‌ لیسانس، فوق‌لیسانس، دکتری} باشد).

برای آموزش یک مدل یادگیری ماشین با استفاده از داده‌های دسته‌ای، باید داده‌ها را به شکل مناسب کدگذاری بکنید که برای این امر می‌توانید از کتابخانه category-encoders در زبان پایتون استفاده کنید. هر یک از ویژگی‌های دسته‌ای که در مجموعه داده این سوال قرار دارند از چهار نوع اسمی، ‌ترتیبی، دودویی و تاریخی‌ هستند که توضیحی از آنها در جدول زیر آمده است. (دقت کنید که علاوه بر کدگذاری این ستون‌ها به شکل مناسب باید خانه‌هایی که دارای مقادیر nan هستند را نیز با روشی مناسب مدیریت بکنید.)

پس از تمیز و کد کردن داده‌ها و ساخت مدل،‌ پیش‌بینی‌های مدل خود بر روی داده تست (test.csv) را در فایلی با نام submission.csv برای ما ارسال کنید. این فایل باید دارای یک ستون باشد که ردیف $i$ ام آن پیش‌بینی شما برای ردیف $i$ ام از داده تست می‌باشد (دقت کنید که ستون باید حتما دارای header باشد). پیش‌بینی های شما باید به صورت احتمالاتی و بین صفر و یک باشند. برای ارزیابی مدل شما از سطح زیر ناحیه نمودار ROC استفاده می‌شود. درمورد این نمودار می‌توانید اینجا بیشتر مطالعه کنید.

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

از آنجا که علی فرد تنبلیست تصمیم می گیرد تا یک مدل احتمالاتی برای تصحیح نوشتار (Auto correct) ایجاد کند. به این ترتیب دیگر نیاز به تمرین ندارد. او برای ساختن مدل خود از متن‌های شکسپیر کمک می گیرد!! متنی که در اختیار شما قرار گرفته حدودا شامل ۶۱۱۶ کلمه‌ی متفاوت از شکسپیر کبیر است.

مدل احتمالاتی تصحیح خودکار کلمات🔗

علی ابتدا همه‌ی کلمات را lower case کرده و کلمات یکتا را جدا می کند. سپس سه تابع زیر را برای ویرایش کلمات پیاده می‌کند.این سه تابع سه روش برای تصحیح یک کلمه هستند: ‍‍‍

• delete_letter: همه‌ی جایگشت کلماتی (با معنی و بی معنی) که با حذف یک حرف از کلمه تشکیل می‌شود را باز میگرداند.
• replace_letter: همه‌ی جایگشت کلماتی (با معنی و بی معنی) که با جایگزین کردن یک حرف از کلمه تشکیل می‌شود را باز میگرداند.
• insert_letter:همه‌ی کلماتی (با معنی و بی معنی) که با اضافه کردن یک حرف به کلمه تشکیل می‌شود را باز میگرداند.

مثلا به ازای ورودی ate به تابع delete_letter خروجی همه‌ی جایگشت‌های حذف یک حرف از کلمه یعنی te,ae,at خواهد بود.

>>> delete_letter('ate')
['at','ae','te']

به ازای ورودی at به تابع replace_letter خروجی همه‌ی جایگشت‌های جایگزینی یکی از حروف هستند. bt,ct,dt,...,zt,aa,ab,ac,...,az

>>> replace_letter('at')
['bt','ct','dt',...,'zt','aa','ab','ac',...,'az']

به ازای ورودی at به تابع insert_letter خروجی همه‌ی جایگشت‌های اضافه شدن یک حرف به این کلمه است. در واقع کلمات جدید به یکی از فرمت‌های xat,axt,atx هستند که x می‌تواند هر یک از حروف الفبا انگلیسی باشد.

دقت کنید خروجی این توابع همه‌ی جایگشت‌ها به جز خود کلمه هستند .با در اختیار داشتن این سه تابع علی می‌تواند به ازای هر کلمه‌ی ورودی همه‌ی کلماتی (با معنی و بی‌معنی) که از طریق اعمال یکی از سه روش بالا به وجود می‌آیند را تولید کند. مثلا در تابع زیر همه‌ی جایگشت‌های یک کلمه که از طریق روش‌های بالا ممکن است تولید شوند، به عنوان خروجی به دست می‌آید.

def edit_one_letter(word):
 """
    Input:
        word: the string/word for which we will generate all possible words that are one edit away.
    Output:
        edit_one_set: a set of words with one possible edit. Please return a set. and not a list.
    """
    edit_one_set = set()
    edit_one_set.update(delete_letter(word))
    edit_one_set.update(replace_letter(word))
    edit_one_set.update(insert_letter(word))
    return edit_one_set

تابع edit_two_letters نیز همه‌ی جایگشت‌های ممکن با استفاده از دقیقا دو مورد از توابع ویرایش متن را خروجی می‌دهد. یعنی خروجی حاصل اعمال دو تا از توابع ویرایش بر کلمه است.

برای تصحیح خودکار یک کلمه، ابتدا همه‌ی کلماتی که می‌توان آن‌ها را با یک ویرایش و یا دو ویرایش از کلمه‌ی ورودی ساخت را مشخص می‌کنیم. سپس کلماتی که در متن شکسپیر وجود ندارند را به عنوان کلمات بی معنی حذف می‌کنیم. در این فرایند استفاده از توابع insert و delete هر یک هزینه برابر ۱ واحد دارد. استفاده از replace اما هزینه برابر ۲ واحد دارد. بنابراین کلمات ساخته شده از کلمه‌ی اصلی هر یک هزینه‌ای دارند(این هزینه عددی بین ۱ تا ۴ خواهد بود!). بعد کلمه‌ای که با کمترین هزینه ویرایش از روی کلمه‌ی اصلی ساخته شده را به عنوان پاسخ صحیح انتخاب می‌کنیم. اگر خروجی چند کلمه با هزینه ویرایش مینیمم خروجی داد، کلمه‌ای را انتخاب می‌کنیم که احتمال حضورش در متن بیشتر است. احتمال حضور یک کلمه یعنی تعداد دفعات حضور کلمه در متن تقسیم بر تعداد کل کلمات. به این روش ایجاد شباهت بین کلمات minimum edit distance می‌گویند.

به شما فایل جملات شکسپیر و یک فایل پروژه تحویل داده می‌شود. در این فایل نمی‌توانید کتابخانه‌ای اضافه کنید. شما باید توابع خواسته شده را تکمیل کنید. دقت کنید فقط جاهایی که از شما خواسته شده را تغییر دهید و در تعاریف توابع پیش‌فرض تغییری ایجاد نکنید وگرنه در فرایند داوری به مشکل خواهید خورد.

فایل پروژه را از [اینجا]( این لینک ) دانلود کنید. در پروژه یک فایل submit.py وجود دارد. ما تابع autoCorrect از این فایل را در داوری صدا می زنیم. این تابع یک کلمه را به عنوان ورودی گرفته و کلمه‌ی با املای درست با شرایط ذکر شده را پس می‌دهد.

>>> autoCorrect('flw')
'flow'

در نهایت فقط فایل submit.py را آپلود کنید.

• محدودیت زمان: ندارد.
• محدودیت حافظه: ندارد.

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

برای راحتی کار شما او بخشی از آن را حذف و تعدیل کرد (راستش احساساتی را انتخاب کرد که براش مهم تر بودن!). او که از پس این کار بسیار دشوار یعنی یافتن دادگان مناسب بر آمده است بسیار خسته است اما سریعا به مدل مناسب نیازمند است؛ برای همین به شما مراجعه کرده است.

دادگان:🔗

همچنان که می دانید به علت حجم بالای دادگان آموزش و آزمون ، لینک دانلود آن از روز قبل در اختیار شما قرار گرفته بود. فایل های آغازین سوال(شامل رمز دادگان آموزش و output.csv) را از [اینجا]( این لینک ) دریافت کنید.

رمز فایل دادگان آزمون (test) نیز دو ساعت قبل از پایان آزمون در اختیار شما قرار خواهد گرفت.

نام فایل های صوتی برای مثال به فرمت زیر است:

1200FS.wav

بخش عددی به معنای id فایل است؛ اولین کارکتر از الفبای انگلیسی مشخص کننده جنسیت

و حرف بعدی نشانگر برچسب‌ِ احساسِ منسوب به این آوا است.

بنابراین مثال بالا متعلق به یک خانم در حالت غمگین است.

ارزیابی:🔗

برای محاسبه کیفیت پاسخ این سوال از log loss استفاده می‌‌کنیم: $L(Y, P) = - \frac{1}{N} \sum_{i=0}^{N-1} \sum_{k=0}^{K-1} y_{i,k} \log p_{i,k}$ $p_{i,0} = 1 - p_{i,1} , y_{i,0} = 1 - y_{i,1}$ اینجا $y_{i,k}$ برابر یک است اگر نمونه $i$ دارای برچسب $k$ است و در غیر این صورت صفر است.

همچنین $p_{i,k}$ بیانگر احتمال آن است که نمونه $i$ دارای برچسب $k$ باشد.

در نهایت امتیاز شما به طریق زیر محاسبه خواهد شد. $exp{(-0.3* ((2*loss)^{0.5}))} * 200$

خروجی:🔗

برای ارسال پاسخ های خود از فایل output.csv استفاده کنید. هر سطر این فایل برابر با یکی از نمونه های آزمون و هر ستون آن (به جز file_id) برابر با یکی از احساس ها است که شما باید احتمال تعلق نمونه ها به هر احساس را پر کنید. ستون file-id (با فرمت int) برابر است با id هر آوا در فایل test بنابراین مراقب باشید که ترتیب نمونه های که احساس آن را پیش بینی می‌کنید درست انتساب یابند. فایل output.csv را با نام output زیپ و ارسال کنید.

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

نحوه آپلود باید به این گونه باشد که برای هر سوال که جواب دادید، یک پوشه به نام آن سوال (مانند problem3) و تمامی کدهای خود (در صورت نیاز requirement.txt) را در آن آپلود کنید.

توجه:🔗

۱- برای سوالات 'نظریه ریسمان'، 'جهان های موازی' و 'آزمون زبان شکسپیر' نیازی به ارسال کد در اینجا نیست.🔗

۲- نیازی به ارسال دیتاست ها نیست.🔗

۳- تنها فرمت قابل قبول برای کدهای ارسالی py. است.🔗

با تشکر فراوان