3/4
Problem 2: Complexity (10 points)
When designing algorithms, it's useful to be able to do quick back of the envelope calculations to see how much time or space an
algorithm needs. Hopefully, you'll start to get more intuition for this by being exposed to different types of problems.
a.
Suppose we have an image of a human face consisting of
n × n
pixels. In our simplified setting, a face consists of
two eyes, two ears, one nose, and one mouth, each represented as an arbitrary axis-aligned rectangle (i.e. the axes
of the rectangle are aligned with the axes of the image). As we'd like to handle Picasso portraits too, there are no
constraints on the location or size of the rectangles. How many possible faces (choice of its component rectangles)
are there? In general, we only care about asymptotic complexity, so give your answer in the form of
O(n
c
)
or
O(c
n
)
for some integer
c
.
b.
Suppose we have a staircase with
n
steps (we start on the ground, so we need
n
total steps to reach the top). We
can take as many steps forward at a time, but we will never step backwards. How many ways are there to reach the
top? Give your answer as a function of
n
. For example, if
n = 3
, then the answer is
4
. The four options are the
following: (1) take one step, take one step, take one step (2) take two steps, take one step (3) take one step, take
two steps (4) take three steps.
Problem 3: Ethical Issue Spotting (10 points)
One of the goals of this course is to teach you how to tackle real-world problems with tools from AI. But real-world problems have real-
world consequences. Along with technical skills, an important skill every practitioner of AI needs to develop is an awareness of the
ethical issues associated with AI. The purpose of this exercise is to practice spotting potential ethical concerns in applications of AI -
even seemingly innocuous ones.
In this question, you will explore the ethics of four different real-world scenarios using the ethics guidelines produced by a machine
learning research venue, the NeurIPS conference. The
NeurIPS Ethical Guidelines
list sixteen non-exhaustive concerns under Potential
Negative Social Impacts and General Ethical Conduct (the numbered lists). For each scenario, you will write a potential negative
impacts statement. To do so, you will first determine if the algorithm / dataset / technique could have a potential negative social impact
or violate general ethical conduct (again, the sixteen numbered items taken from the
NeurIPS Ethical Guidelines
page). If the scenario
does violate ethical conduct or has potential negative social impacts, list one concern it violates and justify why you think that concern
applies to the scenario. If you do
not
think the scenario has an ethical concern, explain how you came to that decision. Unlike earlier
problems in the homework there are many possible good answers. If you can justify your answer, then you should feel confident that
you have answered the question well.
Each of the scenarios is drawn from a real AI research paper. The ethics of AI research closely mirror the potential real-world
consequences of deploying AI, and the lessons you’ll draw from this exercise will certainly be applicable to deploying AI at scale. As a
note, you are
not
required to read the original papers, but we have linked to them in case they might be useful. Furthermore, you are
welcome to respond to anything in the linked article that's not mentioned in the written scenario, but the scenarios as described here
should provide enough detail to find at least one concern.
What we expect:
A 2-5 sentence paragraph for each of the scenarios where you either A. identify at least one ethical concern from the
NeurIPS Ethical Guidelines
and justify why you think it applies, or B. state that you don’t think a concern exists and justify why that’s the
case. Chosen scenarios may have anywhere from zero to multiple concerns that match, but you are only required to pick one concern
(if it exists) and justify your decision accordingly. We have also included a citation in the example solution below, but you are not
required to add citations to your response.
Example Scenario
: You work for a U.S. hospital that has recently implemented a new intervention program that enrolls at-risk patients in
programs to help address their chronic medical issues proactively before the patients end up in the hospital. The intervention program
automatically identifies at-risk patients by predicting patients’ risk scores, which are measured in terms of healthcare costs. However, you
notice that for a given risk score tier, the Black patients are considerably sicker when enrolled than white patients, even though their
assigned illness risk score is identical. You manually re-assign patients’ risk scores based on their current symptoms and notice that the
percentage of Black patients who would be enrolled has increased from 17% to over 45%
[1]
.
Example Solution
: This algorithm has likely encoded, contains, or potentially exacerbates bias against people of a certain race or
ethnicity since the algorithm predicts healthcare costs. Because access to medical care in the U.S. is unequal, Black patients tend to
have lower healthcare costs than their white counterparts
[2]
. Thus the algorithm will incorrectly predict that they are at lower risk.
a.
[2 points] An investment firm develops a simple machine learning model to predict whether an individual is likely to
default on a loan from a variety of factors, including location, age, credit score, and public record. After looking
through their results, you find that the model predicts mainly based on location and that the model mainly accepts
loans from urban centers and denies loans from rural applicants
[3]
. Furthermore, looking at the gender and
ethnicity of the applicants, you find that the model has a significantly higher false positive rate for Black and male
applicants than for other groups. In a false positive prediction, a model misclassifies someone who does not
default as likely to default.
