Discrete Mathematics and Artificial Intelligence
Originally Written on:- June 13th, 2019.
Discrete mathematics is
the study of mathematical structures that
are fundamentally discrete rather
than continuous. In contrast
to real numbers that
have the property of varying "smoothly", the objects studied in
discrete mathematics – such as integers, graphs, and statements in logic –
do not vary smoothly in this way, but have distinct, separated
values. Discrete mathematics therefore excludes topics in "continuous
mathematics" such as calculus or Euclidean geometry.
Discrete objects can often be enumerated by
integers. More formally, discrete mathematics has been characterized as the
branch of mathematics dealing with countable sets (finite
sets or sets with the same cardinality as
the natural numbers). However, there is no exact definition of the term
"discrete mathematics." Indeed, discrete
mathematics is described less by what is included than by what is excluded:
continuously varying quantities and related notions.
We will be applying Discrete mathematics in the
subway to solve a crime in the NYC subway. We need to apply Discrete
Mathematics in a real world scenario and what better way than a subway system.
The New York City Subway is a rapid transit system owned by the City of New York and leased to the New York City Transit Authority.
The New York City Subway is the largest rapid transit system in
the world by number of stations, with 472 stations in operation. Stations
are located throughout the boroughs of Manhattan, Brooklyn, Queens,
and the Bronx.
The lines are:-
The map of the subway system is given:-
For the story ahead we, will focus on only three areas of NYC that is:- Manhattan, Queens and the Bronx. A few stations will be key here:-
1) Chambers
Street/city hall IRT Lexington Line and Chambers Street( world trade centre)
2) 183rd Street,
Bronx
3) 61st street
Woodside Queens
4) 59th street
Lexington Avenue.
The 4 big red dots are the stations of our interest
Trains in the NYC Subway
The 1, C, G, L, M, R,
and W trains
are fully local and make all stops. The 2, 3, 4, 5, A, B, D, E, F, N,
and Q trains
have portions of express and local
service. J, Z, 6,
and 7 trains
vary by day or time of day.
We will deal with the 4, A and 7 express
train for now.
7 express train- 34th street
Hudson yards to Main Street Flushing, map below.
4 train- Woodlawn to New lots avenue, map below.
A train- Inwood 207th street to Far
Rockaway, Brooklyn, map below.
So what does This have to do with artificial
Intelligence
AIM:-
The Aim of this post is not how to show you the all
the traditional methods that are included in discrete mathematics. But we will
be dealing with a problem or to be more specific a murder mystery which we will
be solving using discrete mathematics along with the various
methodologies available with AI .
We are going to take a ride with Bob who is a
detective of the Police department in New York City and has been assigned with
the duty of determining a killer within a limited time frame. The
only resources available at his disposal are discrete mathematics and
Artificial Intelligence.
*For the sake of simplicity, we assume that Bob has
a laptop and wifi connection with him..xd”*
Introduction:-
Our story begins in New York City on a late Friday night. Bob was at his
desk going through his computer and the files to check if any remainder work
was left for the night, if not it was already time for his duty to be called
off. A sense of satisfaction rushed through him as he saw that there was no
more that was left to be done on that day and finally it was time to go home.
It was a Friday and the rest of the department had left for the fourth of July
weekend. He rushed into his Sergeant’s office who was to discharge him off his
duty. Skipping multiple stairs in excitement he couldn’t wait to leave. It was
a pretty boring day and Bob could already smell the barbeque in the air.
On entering the cubicle he saw that the Sergeant was much
too engrossed in his own thoughts to give any immediate response to Bob’s
remonstrance. The supervisor leaned upon his computer, his untasted sandwich
lay before him as he stared at his desktop screen “Look at this”. Now, at this
point Bob was getting a little frustrated because it was time for him to leave
and the supervisor was making him look into something once again.
Apparently, a murder had taken place in the tunnel of the NYC subway in
the middle of Chambers Street and Fulton Street. It was reported by a train
operator .The rest of the department was already off duty, so automatically,
the responsibility fell on Bob . “The mayor wants us to determine the killer by
tonight because we need to get the trains running on time tomorrow and have to
avoid confusion and delay during the rush hours. The deadline is 5:30 am”.
So , not only Bob had to figure out who the killer was but now he
has a time limit…!!
1:00 am
Bob received the assignment and immediately hurried down to the
Chambers Street Station to the crime scene which was a few blocks away from the
PD. He had put on a full blown safety suit just in case to protect himself from
the filth and the rats which populate the NYC subway. He head down to the
station on the north end and with a sigh of unwillingness and disgust he
proceeded to walk into the dark tunnels, while constantly being aware of any
trains that might pass him, by a few inches. A stench filled the tunnel.
He noticed lights flashing down the tunnel. “Not an another train”,
sighed Bob. He hopped and skipped over the train tracks hoping to avoid the
rats, the ongoing trains and the electrified third rail. His flashlight
provided little to the eye. It was the MTA. “Thank God..!!, I don’t have to be
alone in here all night”. The victim lay motionless at the side of the tracks,
the MTA surrounded him. Bob immediately took pictures of the corpse from
all angles and the crime scene. The metro card was still in the man’s wallet
and Bob took possession of both . He punched it in a special display to see
where the man got on from. There were many stations in between like 59th street
Lexington avenue, Chambers Street and finally Fulton Street. But It was
the Bronx which was the origin." So let’s head to the Bronx, 183rd Street,
maybe there is more information over there".
Meanwhile he asked for the camera footage from both the Chambers Street and Fulton Street from the MTA.
He uses the shortest path algorithm to get to the Bronx, to save time.
He uses Dijkstras’ Algorithm. Fortunately, we have the resources to figure that
out. I have found this one resource by a man named Tyler Green who has
worked on Graphing the entire NYC subway system. You can this out. here. I have used his
resource for the entire story.
Look at my Github for details.
The shortest path would be to walk towards city hall for 5 minutes
and catch the 4 train to 183rd street. Total time:- 32 +8= 40 mins.
2: 30 am:
Bob reaches the 183rd street station at Bronx around 2
and immediately asks for the video footage of the station for the whole day to
check for any suspicious activity. He also notices that on this very day, the
payphones employed at the station, was used very frequently. More than the
amount of usage in the normal days.
Out of pure instinct he decides to check on the payphones. “ Maybe there
is a link to the phone calls and the murder”. He takes out the quarters from
all the phones and makes an estimate of the number of calls that were made.
There were 3 payphones and so he used the power of combinatorics to figure out
the number of possible combinations of phone calls. Combinations because he
doesn’t know from which payphone the call was made from and at what time. He
eliminates the time of murder and begins to compute. Around 200 calls were made
from 3 payphones, after elimination.
Now, the math and Machine learning
So distribute:- r calls to n number of payphones
n-r+1Cr . So, 3+200-1C200= 20,301 number of combinations.
He calls the phone operator to give him the list of 50 calls.
There is no time to scan through 200 calls of 5 hours of total duration. So he
uses ML to figure it out.
Bob takes out the phone book from the wallet that was recovered
from the crime scene and uses all of it as training data to the call records in
order to find at least one possible combination from the 20,301 combinations to
check which one matches closely with the content of the wallet and
the content of the call records. Bingo..!!!. There is one. Turns out there was
a person who had called from the Bronx station to a man in Queens, 61st Street
station, informing him that a package was to be delivered by person
A to person B. But at the same time, he had also warned that a person C might
be on him so as to intercept the package. With a stern warning about
person C , the 4 minute call ended. He noted the timestamp of the call.
So, Bob basically created a determination model based off of the
combinations.
2:50 am and Off to Queens
Again Bob uses the shortest path Algorithm to find out the shortest path
to Queens. Now it is the 4 Train to 59st Lexington Avenue and
from there walk towards Queensboro plaza and take the 7 express to 61st street
woodside. Total time:-35+5 = 40 mins(the 4 , W and 7 train).
3: 45 am:-
Bob gets off the train at Queens and immediately asks for the video footage of the station as usual. He notices that there was indeed a man who paced around on the platform and never caught a train for almost 2 hours and then suddenly hurried into a Manhattan bound train as if almost he saw somebody and wanted to chase this person. Also the time at which the Queens Bound train was to arrive exceeded. Now, Bob has the video footage from all four of the stations. He has to determine first that if indeed this is person C and whether or not he was the killer.
He used set theory in his analysis :-
Case 1:- He assumed that if person C is the killer then he must
have gotten into the tunnel and murdered his victim.
Or,
Case 2:- He murdered him in a subway car on the train and hurled him out from the
car inside the tunnel while the train was still on the run.
Or,
Case 3:- He injured him in one of the subway cars/or in some other way and then
dragged his unconscious body through the tunnel and murdered him there so that
no one would find him and and appeared on the same/other end.
It only stands to reason that he cannot appear on both chambers and
Fulton street simultaneously as it is mathematically impossible. He used rules
of inference logic(constructive dilemma here ) to figure this out. These are the
only ways a corpse can end up in a subway tunnel since there were no other
exits.
For case 1:-
P(1)= he should be appearing in Queens station and
P(2)= he should be appearing at Fulton station.
Or,
P(1)= he should be appearing in Queens station and
P(3)= he should be appearing at Chambers street station.
Back in his office:- 4:30 am from Queens
In both cases p(1 U 2)= he appears in at least two station as well as
p(1 U 3). He now has two sets of numbers. He can now tweak his previous
determination system and add feature analysis on the video footage from all the
three stations. He begins processing through all the frames and uses object
detection (YOLO). The features being P(1), P(2), P(3) and all the two
values of p being the number of combinations he has to run it on.
Turns out there was such a guy who reappears at Fulton street but since there was nobody in the station, nobody saw him walk from the tunnel and appear into the station. His intuition was right all along and his methods of applying ML, DL and discrete maths proved to be effective.
5:15 am
It was already sunrise and Bob called in his supervisor finally and
asked for someone to hunt down this person C and check through all their
databases for known criminal records. He provided his supervisor with all
necessary details.
But who got killed, was it person A or person B at the hands of person
C.
Whoever it may be, he got up from Bronx and ended up on the A train
Line. So, he must have taken the first shortest path, changed trains and ended
up in the A line from Fulton street and the person C had taken the second
shortest path from 61st to Fulton and did the heinous murder of
person A or B and somehow he knew…!!
3 days later...
All 4 train, A train, 7 trains were searched for investigating purposes
and some evidence was found. The two got into a confrontation from Lexington
avenue to chambers street, the final report concluded.
Comments
Post a Comment